Here are the review problems from Thursday’s class.

I’ve written up brief summaries of the solutions (note: these are a rush job and should not be taken as the level of exposition that would be appropriate on homework or a test). The solutions are in white text below; select with the mouse to view. This is so that you can read one solution at a time without having the rest spoiled for you. The solutions to #18, 26, and 27 are absent for now due to constraints on my time.

1. Given a k-combination from {1,…,n}, its complement is an (n-k)-combination. This is a one-to-one correspondence.
2. Both sides count the subsets of an n-element set (LHS sorts them by size).
3. LHS counts k-combinations from {1,…,n+1}. RHS breaks them down into those that don’t contain the element n+1 and those that do.
4. LHS counts ways to choose k special people from a pool of n, then make r of those people extra-special. RHS counts ways to choose the r extra-special people first, then choose the k-r people who are just special. Result is the same.
5. LHS counts ways to choose 2 people among n boys and n girls. First term of RHS counts number of opposite-sex pairs. Second term of RHS counts number of same-sex pairs.
6. LHS counts ways to choose 2 muffins from a box of n chocolate, n bran, and n blueberry muffins. First term of RHS counts the pairs consisting of two different types. Second term of RHS counts pairs consisting of same type.
7. LHS counts ways to choose 3 people among n boys and n girls. First term of RHS counts number of same-sex trios. Second term of RHS counts number of mixed-sex trios.
8. Both sides count anagrams of a (2n)-letter string with n different letters each repeated twice. LHS counts based on choosing positions for each pair of identical letters. RHS counts based on division rule.
9. RHS counts ways to choose n people among n boys and n girls. LHS breaks the possibilities down by the number of girls. If k girls are included, then k boys are excluded. We can choose the included girls and the excluded boys in $\binom nk\binom nk$ ways.
10. LHS counts ways to choose a committee of 1 or more people from a pool of n and appoint a committee chair from within the committee. RHS counts ways to choose the committee chair first and then choose any subset of the remaining people to fill out the committee. Alternative solution: Both sides count the total number of elements in all subsets of {1,…,n}; LHS counts one subset at a time, while RHS counts the number of subsets each element appears in.
11. RHS counts the number of ways to choose an (n+1)-element subset of {1,2,…,n+k+1}. The largest element in such a set must be n+j+1 for some j from 0 to k. On the LHS, $\binom{n+j}n$ counts the number of ways to fill out an (n+1)-element subset whose largest element is n+j+1.
12. We choose 1 letter to appear twice, then 3 other letters, then an arrangement of those letters. The number of ways to do this is $26\cdot\binom{25}3\cdot\frac{5!}2$. Alternatively, we choose two positions for the repeated letter to appear in, and four letters in the order of their appearance; the number of ways to do this is $\binom 52\cdot 26\cdot 25\cdot 24\cdot 23$, which is equal to the first answer.
13. Any nonempty subset of the digits {1,…,9} can be arranged in exactly one way to make a positive integer with digits in strictly increasing order. There are $\binom 91+\binom 92+\cdots+\binom 99$ or $2^9-1$ ways to choose that subset.
14. Put the “rejects” in a (k+1)th box. Now we have k+1 possible destinations for each object, so $(k+1)^n$ possible distributions.
15. Per Bayes, the probability is (1)/(1 + 52/54) = 27/53.
16. The number of different “combinations with repetition” of 3 digits from the set {0,…,9} is $\binom{3+10-1}3$, which is 220. One of these (000) can’t occur; the other 219 can occur. By Pigeonhole, we need 219+1 = 220 3-digit numbers to ensure that some two have the same combination of digits.
17. We can take the first flush for granted. Then there are $\binom 85$ ways for the second hand to be a flush of the same suit as the first flush, and there are $3\binom{13}5$ ways for the second hand to be a flush of a different suit. These flushes are all equally probable, so the probability that the two hands are same-suit flushes given that they are both flushes is $\frac{\binom 85}{\binom 85+3\binom{13}5}$.
18. No, they don’t.
19. (9/9999)(1)+(90/9999)(2)+(900/9999)(3)+(9000/9999)(4) = 4321/1111
20. Each element of {1,…,n} has probability 1/2 of being included. The cardinality of the subset is the number of “successes”; its expected value is n/2.
21. (a) The waiting time for the first head is geometrically distributed, with expected value 2. Once that head appears, the waiting time for the next tail is also 2. When that tail comes, it must have been preceded by a head. By linearity, the total waiting time is 2+2=4. (b) Let X be the waiting time for two heads in a row. On average, it takes 2 flips for the first head to appear, and 1 more flip to see if the result is HH or HT. If it’s HH, we’re done. If it’s HT, we’ve flipped 3 coins and we’re no closer to finishing than when we started. So E(X) = (1/2)(3) + (1/2)(3+E(X)). Solve to get E(X) = 6.
22. This problem is too good to spoil here, but here’s a hint: the bets are fair, so the expected value of your money at any time in the future must be equal to the $1 you started with.
23. Also too good to spoil, but I’m willing to discuss it at office hours.
24. (a) 2n+1 ways. Draw a picture of the possible “roads” and it should be clear. (b) 63, I think. If $a_{i,j}$ is the number of paths from (0,0) to (i,j), then $a_{i,j}=a_{i-1,j}+a_{i,j-1}+a_{i-1,j-1}$ for $i,j\ge 1$ and the initial conditions are $a_{i,0}=a_{0,j}=0$ for $i,j\ge 0$.
25. Each n-letter string ends in either a consonant, or a consonant followed by a vowel. What comes before can be any valid string of length n-1 or n-2 (resp.). Thus $a_n = 21a_{n-1}+(21)(5)a_{n-2}$. Initial conditions are $a_0=1$ and $a_1=26$.