18.440 Problem Set 1

Due in class Monday September 3; late work will not be accepted. You can discuss problems with anyone, but you should write solutions entirely on your own.

1. (20 points) We’re going to be very interested in understanding exactly how big the binomial coefficients \binom{n}{k} can be. One way to get such results is “analytically,” by doing something with formulas like

\binom{n}{k} = \frac{n!}{k!(n − k)!}

For example, you can write out all the factorials in this formula and then arrange the factors in increasing order in the numerator and denominator, getting (if k > (n − k))

\binom{n}{k} = \frac{1 · 2 ⋯ (n − 1) · n}{1 · 1 · 2 · 2 ⋯ (k − 1) · k} = \frac{1}{1} \frac{2}{1} \frac{3}{2} \frac{4}{2} ⋯ \frac{n − 1}{k − 1} \frac{n}{k}

Now every one of the n factors in this last product is at most 2 (this requires some thought!), so it follows that

\binom{n}{k} ≤ 2^{n}.

Another way to proceed is “combinatorially,” by comparing two different counting problems. For example, \binom{n}{k} is equal to the number of subsets of \{1, …, n\} having exactly k elements, and 2^{n} is the total number of subsets of {1, …, n}; so it follows that

\binom{n}{k} ≤ 2^{n}.

Here’s the problem: find both an analytic and a combinatorial proof (ten points for each) of the inequality

\binom{2n}{n} ≥ 2^{n}.

2. (20 points) Find (and prove) a simple closed formula for the sum of “trinomial coefficients”

∑_{n_{1}+n_{2}+n_{3}=n} \binom{n}{n_{1}, n_{2}, n_{3}}

3. (20 points) I’ll give a lot of problems referring to a standard deck of 52 playing cards. If this is too unfamiliar to somebody, please email me.

a) How many possible four-card hands can be made from a deck of 52 cards?

b) How many four card hands contain exactly one card from each suit?

4. (20 points) Are most binomial coefficients even or odd? (I know that the question isn’t well-posed. Try to make it precise in some way, and try at least to guess an answer, giving some evidence or justification.)