\documentclass{article}
\input{18440-preamble}

\begin{document}
\pset{1}{Dan Ports}{2003/09/08}{drkp@mit.edu}

\begin{ppart}{Problem 1}
\paragraph{Analytic proof}
Using the definition of binomial coefficients, we expand $\binom{2n}{n}$:
\[ \binom{2n}{n} = \frac{(2n)!}{n!(2n-n)!} = \prod_{i=0}^{n-1} \frac{2n-i}{n-i}\]
Next, observe that (for $0 \le i \le n-1$), $\frac{2n-i}{n-i} \ge 2$. The $i=0$ case reduces to $\frac{2n}{n} = 2$, and the terms of the product are monotonically increasing:
\[ \frac{2n-(i+1)}{n-(i+1)} - \frac{2n-i}{n-i} = \frac{(2n-i-1)(n-i) - (2n-i)(n-i-1)}{(n-i-1)(n-i)} = \frac{n}{(n-i-1)(n-i)} > 0 \]
Therefore each term is at least $2$. There are $n$ terms, each at least $2$, so we have shown that $\binom{2n}{n} \ge 2^n$.
\paragraph{Combinatorial proof}
We will prove the inequality by identifying a set with $2^n$ elements that is a subset of a set with $\binom{2n}{n}$ elements. Consider the set of possible $n$-digit strings made up of the characters $A$ and $B$. There are $2^n$ such strings. Now consider the problem of choosing $n$ elements from the set $\{A_1,A_2,\ldots,A_n,B_1,B_2,\ldots,B_n\}$. Since there are $2n$ total elements, there are $\binom{2n}{n}$ possible choices. Each $n$-digit string from the first set can be represented uniquely as a set of elements from the second set: for each character in the string, the element corresponding to that character and that position in the string is chosen (e.g. the string $ABAA$ becomes the set ${A_1,B_2,A_3,A_4}$). Thus the set of $n$-strings ($2^n$ total) is contained within the set of $n$-combinations of the $2n$ set ($\binom{2n}{n}$ total). So we have proven $2^n \le \binom{2n}{n}$.
\end{ppart}

\begin{ppart}{Problem 2}
\paragraph{}
We will use a combinatorial argument to show that $\sum_{n_1+n_2+n_3=n}\binom{n}{n_1,n_2,n_3} = 3^n$. First, note that for any such $n_1,n_2,n_3$, $\binom{n}{n_1,n_2,n_3}$ is the number of ways to partition $n$ elements into three distinct sets of size $n_1$, $n_2$, and $n_3$. Next, consider the problem of partitioning $n$ elements into three distinct sets of any size (including size zero). The possible set sizes are the possible values of $n_1$, $n_2$, and $n_3$ that add up to $n$, and so the total number of partitions is the sum over all these values: $\sum_{n_1+n_2+n_3=n}\binom{n}{n_1,n_2,n_3}$. But we can also compute the total number of such partitions by assigning a value between $1$ and $3$ to each of the $n$ elements, corresponding to the set they are placed in. This creates $3^n$ partitions. Thus we have shown that $\sum_{n_1+n_2+n_3=n}\binom{n}{n_1,n_2,n_3} = 3^n$.
\end{ppart}

\begin{ppart}{Problem 3}
\paragraph{Part a}
Choosing $4$ cards from $52$, there are $\binom{52}{4} = \frac{52!}{4!(52-4)!} = 270725$ possible hands.
\paragraph{Part b}
There are $13$ cards in each suit, so the total number of hands (ignoring ordering) with one card from each suit is $13^4 = 28561$.

\end{ppart}
\paragraph{}

\begin{ppart}{Problem 4}
\paragraph{}
First, consider a binomial coefficient $\binom{n}{k} = \frac{n!}{k!(n-k)!}$. Define the function $p_2(x)$ to be the number of times $x$ is divisible by $2$. We know that $p_2(n!) \ge p_2(k!)+p_2((n-k)!)$, since the binomial coefficients are integers. When $p_2(n!) > p_2(k!)+p_2((n-k)!)$, $\binom{n}{k}$ is divisible by $2$. Otherwise, when $p_2(n!) = p_2(k!)+p_2((n-k)!)$, all factors of $2$ cancel and $\binom{n}{k}$ is odd. 
\paragraph{}
\paragraph{}
A printout of some testing in Matlab is attached. This script makes use of the recurrence
\[ \binom{n}{r}=\binom{n-1}{r-1}+\binom{n-1}{r} \]
(Ross, p.8), along with the base cases $\binom{0}{0} = 1$, $\binom{n}{0} = 1$, and $\binom{n}{n} = 1$. All computations are performed modulo 2. The result is a Sierpinski triangle. Computed to the first hundred rows, we find 3799 even numbers and 1225 odds: 75.62\% of the numbers are even. So we conclude that most binomial coefficents are even. 
\end{ppart}


\end{document}