PineWiki
1. Presidents and vice presidents
Show that, for all nāā,
![\[
\sum_{k=0}^{n} k(k-1) {n \choose k} = n(n-1)2^{n-2}.
\]](/pinewiki/CS202/Assignments/HW05?action=AttachFile&do=get&target=latex_f69bd677a2970b0ab2f0f1aa3bfcdb1b55db62f3_p1.png "\[
\sum_{k=0}^{n} k(k-1) {n \choose k} = n(n-1)2^{n-2}.
\]")
Hint: What does each side of the equation count?
2. Mystery chocolates
A box of n chocolates contains m in flavors that you don't like. Assuming that you choose r of the chocolates to eat uniformly at random, what is the probability that at least one of them is a flavor that you don't like?
3. Monochrome sets
Suppose we have a set S of n elements, and we assign each element one of r colors. Call a subset A of S monochrome if every element of A is assigned the same color. Given n, r, and k, show that there exists a coloring of S in which at most 
subsets A of size k are monochrome.
Hint: On average, how many subsets are monochrome in a random coloring?