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?

1.1. Solution

1.1.1. Method 1: combinatorial proof

Here we follow the suggestion in the hint.

On the left-hand side, we consider for each k all subsets of size k of an n-element set, and for each such subset have k(k-1) possibilities. This occurs, for example, if we choose from each of the subsets two marked nodes in order without replacement. So the left-hand side counts all the ways to choose a subset of a set of n elements with two of the nodes marked with distinguishable marks.

On the right-hand side, we can imagine choosing one marked element (n choices), a second distinct element with a distinct mark (n-1) choices, and then a subset of the remaining n-2 elements. This also gives us a subset of a set of n elements with two of the nodes marked with distinguishable marks.

Since both sides count the same thing, the two quantities must be equal.

1.1.2. Method 2: algebraic proof

We can also solve the problem just by symbol manipulation:

$\begin{eqnarray*} \sum_{k=0}^{n} k(k-1){n \choose k} &=& \sum_{k=2}^{n} k(k-1){n \choose k} \\ &=& \sum_{k=2}^{n} k(k-1)\frac{n!}{k! (n-k)!} \\ &=& \sum_{k=2}^{n} k(k-1)\frac{n(n-1)(n-2)!}{k(k-1)(k-2)! (n-k)!} \\ &=& \sum_{k=2}^{n} n(n-1)\frac{(n-2)!}{(k-2)!(n-k)!} \\ &=& \sum_{k=2}^{n} n(n-1){n-2 \choose k-2} \\ &=& n(n-1)\sum_{k=0}^{n-2} {n-2 \choose k} \\ &=& n(n-1) 2^{n-2}. \end{eqnarray*}$

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?

2.1. Solution

There are several ways to do this. The easiest ways first compute the probability that we get no bad chocolates, and then subtract this from 1.

First method: Suppose we are choosing a subset of r chocolates all at once, with each subset having a probability of exactly $1/{n \choose r}$ of being chosen. Since there are ${n-m \choose r}$ subsets that are all likable, the probability we don't get an all-likable subset is $1-{n-m \choose r}/{n \choose r} = 1 - \frac{(n-m)_r}{(n)_r}$ . (Note we get the same result if we assume all ordered sequences of r chocolates are equally likely: now we have (n-m)_r all-good sequences out of (n)_r total sequences, so we again get 1-(n-m)_r/(n)_r.)

Second method: Suppose we choose chocolates one at a time, and compute the probability that we get no bad chocolates. For i in 1..r, let A_i be the event that the i-th chocolate is good. Then Pr[A₁∧A₂∧...A_r] = ∏[i=1..r] Pr[A_i|A₁∧...∧A_i-1]. We can compute the probability that the i-th chocolate is good conditioned on the previous chocolates being good by observing that there are n-m-i+1 good chocolates left out of n-i+1 remaining chocolates. So we have Pr[A₁∧...∧A_n] = ∏[i=1..r] (n-m-i+1)/(n-i+1) = (∏[i=1..r] (n-m-i+1))/(∏[i=1..r] (n-i+1)) = (n-m)_r/(n)_r. So again we get a probability of 1-(n-m)_r/(n)_r of choosing at least one bad chocolate.

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?

3.1. Solution

Suppose we assign each element each color with probability 1/r. Then for each fixed color, the probability that every element in a subset A of size k has that color is (1/r)^k. So summing over all colors gives r(1/r)^k = r^1-k.

Let X_A be the indicator variable for the event that A is monochrome; we've just shown that E[X_A] = r^1-k. Now compute the total expected number of monochrome k-subsets by summing over all A: E[total monochrome k-subsets] = E[∑ I_A] = ∑ E[I_A] = ${n \choose k}r^{1-k}$ . Since we get this value on average for a random coloring, there must be some specific coloring that is no bigger.