Note: You are looking at a static copy of the former PineWiki site, used for class notes by James Aspnes from 2003 to 2012. Many mathematical formulas are broken, and there are likely to be other bugs as well. These will most likely not be fixed. You may be able to find more up-to-date versions of some of these notes at http://www.cs.yale.edu/homes/aspnes/#classes.

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}.$

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 ${n \choose k}r^{1-k}$ subsets A of size k are monochrome.

Hint: On average, how many subsets are monochrome in a random coloring?