\documentclass{article}
\input{preamble.tex}
\title{Day 21}
\date{June 21,2012}
\newcommand{\df}{\textbf}
\begin{document}
\maketitle
\section{Counting Proofs}
We have already seen some interesting properties of numbers witnessed by counting. For example:
\[
{n\choose k} = \frac{n!}{ k! (n-k)! }
\]
The left is, by definition, the number of ways that we can choose $k$ objects from a set of size $n$. The right, however, is just some numbers, which incidentally count the same thing. The proof of this equality was showing that both expressions counted the same set. That is, they both count the number of ways we can choose $k$ objects from $n$. An interesting corollary of this fact is that $\frac{n!}{k!(n-k)!}$ is an integer. It's no immediately clear that it is, but because it counts a set of objects, it must be an integer.
As you would probably guess, this is not the only such proof which is interesting. There are many combinatorial identities. To prove them, we can usually use several methods. Sometimes we can use arithmetic and identities already proved; the above is a particular important one because it allows us to actually do arithmetic with binomial coefficents. Another way we can prove combinatorial identites, often enough is induction. We have already seen, for instance, a proof that $2^n$ counts the subsets of a set of size $n$ by induction.
What we are interested in, however, is combinatorial proofs, as in the one above.
\subsection{Some Examples of Combinatorial Proofs}
\begin{eg}
We have already seen many examples of combinatorial proofs, in a way. Recall we counted the number of ways to permute the English alphabet such that between x and y there are exactly 5 letters. We did this several different ways
\begin{tabular}{>{\bfseries}r p{3in} l}
Step 1 & Decide if $x$ or $y$ comes first & 2 ways \\
Step 2 & Arrange the remaining letters; the first five go between $x$ and $y$ & 24! ways \\
Step 3 & Pick a spot in the alphabet for the beginning of the $x$,$y$ block. The other letters go around this position in the order chosen & 20 ways
\end{tabular}
This makes the total $2\cdot 20 \cdot 24!$.
But, we could could have equally well counted this a different way:
\begin{tabular}{>{\bfseries}r p{3in} l}
Step 1 & Decide if $x$ or $y$ comes first & 2 ways \\
Step 2 & Arrange the remaining letters; the first 5 go between $x$ and $y$ & 24! ways \\
Step 3 & Decide how many of the remaining 19 letters go before and after this $x$, $y$ block by breaking them into two groups & ${19 + 2 - 1} \choose 19$
\end{tabular}
Note, it is fairly easy to see these are equal from looking at it, but they do represent different processes of counting. This proves therefore that
\[
2\cdot 20 \cdot 24! = 2\cdot 24! \cdot {20 \choose 19}
\]
There is no arithmetic or algebraic arguement needed. THey are equal because they both count the number of ways to permute the alphabet so there is exactly five letters between x and y.
\end{eg}
In the above example, we very much ``stumbled into'' the counting proof. That is to say, we were counting some set and we just realized that there were multiple ways to count it. This is a nice technique (it allows you to check your work, to count it two different ways and verify they are the same arithmetically the same). However, these combinatorial proofs are often, as described above, used to prove the equality of two things.
\begin{thm}[Pascal's Formula]
If $n>0$
\[
{n \choose k} = {{n-1}\choose k} + {{n-1}\choose {k-1}}
\]
\end{thm}
\begin{proof}
One can easily verify this arithmetically, but this is not the point, as these binomial coefficents are not defined arithmetically. It's much more elegant to, instead, get the above by counting. So, we need to describe some set, and then show that both of the above formulas count our set. Often in practice we identify what one of the things counts (the `simpler' thing) and then try to count the same set using the other side. In the above case, the left hand side easily counts the number of ways to choose $k$ things from a collections of size $n$.
We will be even more specific, since it does not hurt us to be. We will count the number of ways to choose $k$ numbers from $[n]$. Clearly, the left hand side counts this. We need only show that the right hand side does as well.
So, we need to count this set a different way. So, we will do it by doing cases on whether $1$ is in the subset.
\begin{tabular}{>{\bfseries}r p{3in} l}
Case 1 & $1$ is in subset & \\ \hline
Step 1 & Pick, of the remaining $n-1$ elements, $k-1$ things to accompany $1$ & ${n-1} \choose {k-1}$ ways \\
\hline \hline
Case 2 & $1$ is not in the subset \\ \hline
\qquad Step 1 & Pick, of the remaining $n-1$ elements, $k$ things to go in the subset & ${n-1}\choose k$ ways
\end{tabular}
This makes the total (summing across cases) exactly the right hand side.
\end{proof}
This theorem is especially cool, since now knowing $0 \choose 0 = 1$, we can generate all non-boundary examples of combinations recursive, in what is called \df{Pascal's Triangle}
\begin{center}
\begin{tabular}{c c c c c c c}
& & & 1 & & & \\
& & 1 & & 1 & & \\
& 1 & & 2 & & 1 & \\
1 & & 3 & & 3 & & 1 \\
& & & $\vdots$
\end{tabular}
\end{center}
\begin{thm}[Chairperson's Identity]
\[
n\cdot {{n-1} \choose {k-1}} = k \cdot {n\choose k}
\]
\end{thm}
\begin{proof}
This is a little more daunting, as neither side looks simple. We note, however that the right hand side choose $k$ objects, and then seems to select one of those object.
So, after observing this, we choose to count the set of all $k$ person committees that can be formed out of a popular of $n$ people with a special chairperson. So, the right hand side does the follow:
\begin{tabular}{>{\bfseries}r p{3in} l}
Step 1 & Select $k$ people to be on the comittee & $n\choose k$ ways \\
Step 2 & Select someone to wear the chairperson hat from these $k$ & $k$ ways
\end{tabular}
This makes the total the right hand side.
To count the same thing using the left hand side, we do:
\begin{tabular}{>{\bfseries}r p{3in} l}
Step 1 & Make someone wear the chairperson hat from the population & $n$ ways \\
Step 2 & Build a comittee around them & ${n-1} \choose {k-1}$ ways
\end{tabular}
This makes the total the left hand side.
\end{proof}
\begin{thm}
\[
\sum_{i=1}^n i\cdot{n\choose i} = n\cdot 2^{n-1}
\]
\end{thm}
\begin{proof}
The right hand side is overwhelmingly simpler, so we first try to count using that. Note, that $n$ chooses an object from a set of size $n$, and $2^{n-1}$ seems to make a subset. Therefore, the set we choose to count is the number of comittees that we can form from $n$ people with a chairperson.
\begin{tabular}{>{\bfseries}r p{3in} l}
Step 1 & Choose chairperson & $n$ ways \\
Step 2 & Pick the remaining comittee & $2^{n-1}$ ways
\end{tabular}
So, we wish to count this in a different ways. Note, the sum on the left hand side suggests that we should so cases. From the form, it looks as thought the cases should be done on the size of the comittee being formed.
\begin{center}
\begin{tabular}{>{\bfseries}r p{3in} l}
Case 1 & The comittee has one person \\ \hline
Step 1 & Choose the comittee & $n\choose 1$ ways \\
Step 2 & Choose the chairperson among those people & $1$ way \\ \hline \hline
Case 2 & The comittee has two people \\ \hline
Step 1 & Choose the comittee & $n\choose 21$ ways \\
Step 2 & Choose the chairperson among those people & $2$ ways \\ \hline \hline
& $\vdots$ \\
Case n & The comittee has $n$ people \\ \hline
Step 1 & Choose the comittee & $n\choose n$ ways \\
Step 2 & Choose the chairperson among those people & $n$ ways \\ \hline \hline
\end{tabular}
\end{center}
We sum across the cases, giving us the right hand side.
Since we counted the same set using both the left hand side of the above and the right hand side they are equal.
\end{proof}
\begin{thm}
\[
\sum_{i=0}^n {{n-i}\choose k} = {{n+1}\choose {k+1}}
\]
\end{thm}
\begin{proof}
It is plain one thing that the right hand side counts: the number of ways to choose subset of of size $k+1$ from a universe of size $n+1$. But instead, here we will look at the left hand side as binary sequences (sequences of $0$'s and $1$'s) and the right hand side is the the number of binary sequences of length $0$ with $k+1$ many $1$'s.
For the left hand side, we do cases of where the first $1$ appears (I am thinking of $i$ as the number of $0$'s that appear before the first $1$).
In the case when there are no $0$'s before the first $1$, we know our sequence begins with a $1$, and then there are $k$ other positions we must put $1$ in the remaining $n$ spots. So the total is ${n\choose k}$. If there is one $0$ before $1$, we know the sequence begins $01$, and then there are $k$ other positions where we must put $1$ in the remaining $n-1$ spots. Continuing in this fashion, we have that the total number of ways for each $i$ is ${ {n-i} \choose k}$. Summing across all the possible number of $0$'s before the first $1$, we get the left hand side.
\end{proof}
\end{document}