Massachusetts Institute of Technology Handout 41 6.042J/18.062J: Mathematics for Computer Science October 30, 1998 Professors Nancy Lynch and Srini Devadas

Notes for Recitation 8 (10/30/98)

1 Binomial coefficients

In lecture, we saw the binomial coefficients

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

These represent the number of ways to choose r elements from a set of n elements, where the order does not matter. Here we see more properties of binomial coefficients.

Binomial coefficients are related to Pascal’s triangle.^{1}

Pascal’s Triangle

1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 …

Define T_{n,r} as the r-th entry in the n-th row, where n ≥ 0 and 0 ≤ r ≤ n (so we count rows and entries starting from the 0-th.) Then, the inductive definition of T_{n,r} is as follows: for any n ≥ 0,

T_{n,r} = \{ \begin{matrix}1 & If r = 0 \\ 1 & If r = n \\ T_{n−1,r} + T_{n−1,r−1} & If 1 ≤ r ≤ n − 1 . \end{matrix}

We now show that binomial coefficients satisfy a similar inductive property.

1A curiosity: Pascal’s triangle is called “Tartaglia’s triangle” in Italy.

Lemma 1.1 For 1 ≤ r ≤ n − 1,

\binom{n}{r} = \binom{n − 1}{r} + \binom{n − 1}{r − 1}

Proof. [Combinatorial] \binom{n}{r} is the number of subsets of size r chosen from a set of size n. Fix some element x in a set S of size n. There are \binom{n−1}{r} subsets of S with r elements which contain x and there are \binom{n−1}{r−1} subsets of S with r elements which do not contain x. Therefore, the total number of subsets of S with r elements is \binom{n−1}{r} + \binom{n−1}{r−1}.

Proof. [Algebraic]

\binom{n − 1}{r} + \binom{n − 1}{r − 1} = \frac{(n − 1)!}{(n − r − 1)!r!} + \frac{(n − 1)!}{(n − r)!(r − 1)!}
= (n − r)(n − 1)!(n − r − 1)!r! + \frac{(n − 1)!}{(n − r)!(r − 1)!}
= \frac{((n − r) + r)(n − 1)!}{(n − r)!r!}
= \frac{n!}{(n − r)!r!} .

It is now easy to prove by induction that T_{n,r} is equal to \binom{n}{r}.

Theorem 1.2 T_{n,r} = \binom{n}{r}.

Proof. By induction on n.

Base Case. For n = 0, the only case to consider is r = 0, for which we have \binom{0}{0} = 1 = T_{0,0}.

Inductive Step. Assume that for all 0 ≤ r ≤ n − 1 it holds T_{n−1,r} = \binom{n−1}{r}. We want to prove that for all 0 ≤ r ≤ n it holds T_{n,r} = \binom{n}{r}. We consider three cases.

1. If r = 0, then T_{n,0} = 1 = \binom{n}{0}.

2. If r = n, then T_{n,n} = 1 = \binom{n}{n}.

3. If 1 ≤ r ≤ n − 1, then we have

T_{n,r} = T_{n−1,r} + T_{n−1,r−1} by definition of T_{n,r}
= \binom{n−1}{r} + \binom{n−1}{r−1}  using the inductive hypothesis
= \binom{n}{r}  by Lemma 1.1

Recall that for 0 ≤ r ≤ n,

\binom{n}{r} = \binom{n}{n − r}.

The next theorem gives the ratio between successive binomial coefficients (same n, successive r):

Theorem 1.3 Suppose 1 ≤ r ≤ n. Then

\binom{n}{r} = \frac{(n − r + 1)}{r}\binom{n}{r − 1}.

Proof. [Combinatorial] Consider the number of ways of choosing a committee of r members out of n people, and also choose a chairman for the committee. There are \binom{n}{r} ways of choosing the committee, and for each such committee there are r choices for the chair. Alternatively, there are \binom{n}{r−1} ways of choosing all the members but the chair, and then n − r + 1 ways to choose the chair among the remaining people. It follows that

r\binom{n}{r} = (n − r + 1)\binom{n}{r − 1}

Proof. [Algebraic]

\binom{n}{r}/\binom{n}{r − 1} = \frac{n!}{r!(n − r)!} × \frac{(r − 1)!(n − (r − 1))!}{n!}
= (n − r + 1)/r.

Note that the ratio between successive binomial coefficients is > 1, which means the successive coefficients are increasing, as long as r < \frac{n+1}{2}. Also, the ratio is < 1, which means the coefficient are decreasing, when r > \frac{n+1}{2}. This says that the coefficients increase, reach the maximum, then decrease, i.e., they are unimodal. Here is another equation about binomial coefficients.

Theorem 1.4 Suppose 0 ≤ r ≤ m, n. Then

\binom{m + n}{r} = ∑_{k=0}^{r} \binom{m}{r − k}\binom{n}{k}

Proof. Suppose there are m red balls and n blue balls, all distinct. There are \binom{m+n}{r} ways to choose r balls from the two sets combined. This is the LHS of the identity. Now decompose this collection of choices based on how many of the chosen balls are blue and how many are red. For any k, 0 ≤ k ≤ r, there are \binom{m}{r−k} ways to choose r − k red balls, and \binom{n}{k} ways to choose k blue balls. By the product rule, that makes \binom{m}{r−k}\binom{n}{k} ways to choose r balls such that k of them are blue. Adding up these numbers for all k we have that this is ∑_{k=0}^{r} \binom{m}{r−k}\binom{n}{k} which is the RHS.

2 Applications of the Binomial Theorem

Recall that the Binomial Theorem states that

(x + y)^{n} = ∑_{r=0}^{n} \binom{n}{r}x^{r}y^{n−r}

The Binomial Theorem has a couple of immediate corollaries.

Corollary 2.1 ∑_{r=0}^{n} \binom{n}{r} = 2^{n}.

Proof. Set x = y = 1 in the Binomial Theorem.

2^{n} = (1 + 1)^{n} = ∑_{r=0}^{n} \binom{n}{r}1^{r}1^{n−r} = ∑_{r=0}^{n} \binom{n}{r} .

There is also a combinatorial proof: ∑_{r=0}^{n} \binom{n}{r} is equal to the total number of subsets of a set of n elements, and we know that there are 2^{n} subsets.

Corollary 2.2 ∑_{r=0}^{n}(−1)^{r}\binom{n}{r} = 0.

Proof. Set x = −1 and y = 1 in the Binomial Theorem.

0 = ((−1) + 1)^{n} = ∑_{r=0}^{n} \binom{n}{r}(−1)^{r}1^{n−r} = ∑_{r=0}^{n}(−1)^{r}\binom{n}{r} .

Corollary 2.2 can be used to give a combinatorial proof of the Inclusion-Exclusion formula.

Theorem 2.3 (Inclusion-Exclusion)

|A_{1} ∪ … ∪ A_{n}| = ∑_{k=1}^{n}(−1)^{k+1} ( ∑_{S⊆{1,... ,n},|S|=k} | ⋂_{i∈S} A_{i}|) .

Proof. [Combinatorial] For any element x ∈ A_{1} ∪ … ∪ A_{n}, we will compute the contribution of x to the RHS of the inclusion-exclusion formula.

Let m be the number of sets among A_{1}, …, A_{n} to whom x belongs. Then, since x belongs to m sets, x contributes m to the RHS when k = 1; also, since x belongs to \binom{m}{2} intersections of pairs of sets, x will contribute −\binom{m}{2} to the RHS when k = 2. In general, for k ≤ m, x belongs to \binom{m}{k} intersections of k sets. Furthermore, x will give no contribution when k > m, since x belongs to no intersection of m + 1 sets or more. Overall the contribution given by x is

∑_{k=1}^{m}(−1)^{k+1}\binom{m}{k}  (1)

Since we know that

∑_{k=0}^{m}(−1)^{k+1}\binom{m}{k} = − (∑_{k=0}^{m}(−1)^{k}\binom{m}{k}) = 0 ,  (2)

we can subtract the LHS of (2) from (1) and we conclude that the contribution given by x is

−(−1)^{0+1}\binom{m}{0} = 1

So, each element of A_{1} ∪ ⋯ ∪ A_{n} contributes 1 to the inclusion-exclusion formula, which means that the inclusion-exclusion formula correctly computes the cardinality of A_{1} ∪ ⋯ ∪ A_{n}.

Proof. [By Boring Induction] We have already seen that for any two sets A and B it holds

|A ∪ B| = |A| + |B| − |A ∩ B| .

We will use this fact to prove the correctness of the Inclusion-Exclusion formula by induction on n.

Base Case. For n = 1 the Inclusion-Exclusion formula is just |A_{1}| = |A_{1}|. Inductive Step. Assume that

|A_{1} ∪ … ∪ A_{n−1}| = ∑_{k=1}^{n−1}(−1)^{k+1} ( ∑_{S⊆{1,... ,n−1},|S|=k} | ⋂_{i∈S} A_{i}|) .

and consider an n-th set A_{n}. Using Inclusion-Exclusion for two sets, we have

|A_{1} ∪ ⋯ ∪ A_{n}| = |(A_{1} ∪ … ∪ A_{n−1}) ∪ A_{n}|
= |A_{1} ∪ … ∪ A_{n−1}| + |A_{n}| − |(A_{1} ∪ … ∪ A_{n−1}) ∩ A_{n}|
= |A_{1} ∪ … ∪ A_{n−1}| + |A_{n}| − |(A_{1} ∩ A_{n}) ∪ … ∪ (A_{n−1} ∩ A_{n})|

Using the inductive hypothesis we can compute unions of n − 1 sets.

|A_{1} ∪ … ∪ A_{n−1}| = ∑_{k=1}^{n−1}(−1)^{k+1} (  ∑_{S⊆{1,... ,n−1},|S|=k} | ⋂_{i∈S} A_{i}|)
= ∑_{k=1}^{n−1}(−1)^{k+1} (  ∑_{S⊆{1,... ,n},|S|=k,n∉S} | ⋂_{i∈S} A_{i}|)
|(A_{1} ∩ A_{n}) ∪ … ∪ (A_{n−1} ∩ A_{n})| = ∑_{k=1}^{n−1}(−1)^{k+1} (  ∑_{S⊆{1,... ,n−1},|S|=k} | ⋂_{i∈S}(A_{i} ∩ A_{n})|)
= ∑_{k=1}^{n−1}(−1)^{k+1} (  ∑_{S⊆{1,... ,n−1},|S|=k} | ⋂_{i∈S∪{n}} A_{i}|)
= − ∑_{k=2}^{n}(−1)^{k+1} (  ∑_{S⊆{1,... ,n},|S|=k,n∈S} | ⋂_{i∈S} A_{i}|)

Putting the pieces together, we have that

|A_{1} ∪ ⋯ ∪ A_{n}| = ∑_{k=1}^{n−1}(−1)^{k+1} (  ∑_{S⊆{1,... ,n},|S|=k,n∉S} | ⋂_{i∈S} A_{i}|)

+|A_{n}|

+ ∑_{k=2}^{n}(−1)^{k+1} ( ∑_{S⊆{1,... ,n},|S|=k,n∈S} | ⋂_{i∈S} A_{i}|)

= ∑_{k=1}^{n}(−1)^{k+1} (  ∑_{S⊆{1,... ,n},|S|=k} | ⋂_{i∈S} A_{i}|)

3 Derangements

A derangement is a permutation of 1, 2, …, n where i is not in the i^{th} position. E.g. the number of ways of addressing n envelopes to n people so that all the envelopes are mailed to wrong addresses. Let us represent the number of derangements on n elements as !n.

Theorem 3.1

!n = n! ∑_{k=0}^{n} \frac{(−1)^{k}}{k!}

Proof. Let A_{1} be the set of permutations where the element 1 is mapped to position 1. Similarly let A_{i} for i = 1, …, n be the set of permutations of 1, …, n where i is mapped to the i^{th} position. Then the set of permutations that are not derangements is

A_{1} ∪ … ∪ A_{n}

and the number of such permutations is

|A_{1} ∪ … ∪ A_{n}| = ∑_{k=1}^{n}(−1)^{k+1} ( ∑_{S⊆{1,... ,n},|S|=k} | ⋂_{i∈S} A_{i}|)

In order to evaluate the Inclusion-Exclusion formula, we note that for any set S ⊂ {1, …, n} such that |S| = k we have

| ⋂_{i∈S} A_{i}| = (n − k)!

since a permutation in ⋂_{i∈S} A_{i} is a permutation that fixes the elements of S and permutes in an arbitrary way the other n − k elements. There are (n − k)! ways to choose such a permutation. Considering that for any k there are \binom{n}{k} sets S of size k, the sum evaluates to

∑_{k=1}^{n}(−1)^{k+1}\binom{n}{k}(n − k)! = ∑_{k=1}^{n}(−1)^{k+1} \frac{n!}{(n − k)!k!}(n − k)!

= ∑_{k=1}^{n}(−1)^{k+1} \frac{n!}{k!}

Since this gives us the number of permutations that are not derangements, by subtracting this value from n! we find the number of derangements:

!n = n! − ∑_{k=1}^{n}(−1)^{k+1} \frac{n!}{k!}

= n! (1 + ∑_{k=1}^{n}(−1)^{k} \frac{1}{k!})

= n! ∑_{k=0}^{n}(−1)^{k} \frac{1}{k!}

The Taylor expansion of e^{x} is

e^{x} = 1 + x + \frac{x^{2}}{2!} + \frac{x^{3}}{3!} + …

That is,

e^{x} = ∑_{k=0}^{∞} \frac{x^{k}}{k!}

For x = −1, we have

e^{−1} = 1/e = ∑_{k=0}^{∞} \frac{(−1)^{k}}{k!}

This looks very close to our formula for derangements which is n! times the first n+1 terms in this expansion. In fact, we can observe that the number of derangements is the nearest integer to n!/e. To see this, consider the difference n!/e−!n.

n!/e−!n = n! ( ∑_{k=n+1}^{∞} \frac{(−1)^{k}}{k!} )

= (−1)^{n+1} (\frac{1}{n + 1} − \frac{1}{(n + 1)(n + 2)} + … + \frac{(−1)^{k+1}}{(n + 1)(n + 2) … (n + k)} + …)

So for n ≥ 1,

|n!/e−!n| = \frac{1}{n + 1} − \frac{1}{(n + 1)(n + 2)} + … + \frac{(−1)^{k+1}}{(n + 1)(n + 2) … (n + k)} + …

≤ \frac{1}{2} − \frac{1}{2.3} + … + \frac{(−1)^{k+1}}{(k + 1)!} = 1/e

The last inequality can be observed by grouping the terms of the summation into pairs (the first two, next two and so on) and then comparing. The difference between n!/e and !n is at most 1/e < 1/2, so the number of derangements must be the integer closest to n!/e.

4 Team Problem

In a company there are n engineers and m projects (and, thankfully, there are more engineers than projects.) Each engineer works on exactly one project, and each project must have at least one engineer assigned to it. In how many ways can the boss assign projects to the engineers?

The above problem is equivalent to the problem of counting the number of surjective functions f : A → B between two non-empty sets A and B such that |A| = n (engineers) and |B| = m (projects).

1. Find the number of functions f : A → B.

2. Use Inclusion-Exclusion to derive a formula expressing the number of nonsurjective functions f : A → B in terms of binomial coefficients.

3. Use the previous steps to prove that the number of surjections f : A → B is

∑_{k=0}^{m}(−1)^{k}\binom{m}{k}(m − k)^{n}

where n = |A| and m = |B|.

Solution

Let n = |A|, m = |B|. We compute the total number of functions f : A → B.

Lemma 4.1 The total number of functions f : A → B is m^{n}.

Proof. [Inductive] By induction on n.

Base Case. n = 1. Let A = {a}. Then a function f : {a} → B is totally specified by the value f(a). There are m choices.

Inductive Step. Assume that for all A′ such that |A′| = n − 1 it is true that there are m^{n−1} functions f′ : A′ → B. Fix an element a ∈ A and consider the set A′ = A−{a}. By the inductive hypothesis, there are m^{n−1} functions f′ : A′ → B. For any such function, and for any b ∈ B, we can define a function f : A → B as follows

f(x) = \{ \begin{matrix}b & If x = a; \\ f′(x) & otherwise. \end{matrix}

Indeed, there is a bijection between functions f : A → B and pairs (f′, b) where f′ : A′ → B and b ∈ B. By the product rule, the number of such pairs is m^{n−1} · m = m^{n}, therefore there are m^{n} functions f : A → B.

Proof.[Combinatorial] Functions f : A → B are in 1−1 correspondence with sequences in B^{|A|}. By the product rule, the size of B^{|A|} is m^{n}.

Recall that for a function f : A → B, the range of f is defined as

range(f) = {b ∈ B : ∃a ∈ A.f(a) = b} .

We say that f is not surjective when range(f) ≠ B, meaning that there exists a b ∈ B such that b ∉ range(f). Let F_{b} be the set of functions f : A → B − {b}. Clearly the set of non-surjective functions is given by ⋃_{b∈B} F_{b}. The number of non-surjective functions can now be computed using inclusion-exclusion

| ⋃_{b∈B} F_{b}| = ∑_{k=1}^{|B|}(−1)^{k+1} ∑_{S⊆B,|S|=k} | ⋂_{b∈S} F_{b}|  (3)

It remains to compute the cardinality of the intersections. Observe that ⋂_{b∈S} F_{b} is just the set of functions f : A → B − S, and there are (m − |S|)^{n} such functions. The number of non-surjective functions is thus

∑_{k=1}^{|B|}(−1)^{k+1} ∑_{S⊆B,|S|=k} | ⋂_{b∈S} F_{b}| = ∑_{k=1}^{m}(−1)^{k+1} ∑_{S⊆B,|S|=k}(m − k)^{n}

= ∑_{k=1}^{m}(−1)^{k+1}\binom{m}{k}(m − k)^{n} .

The number of surjective functions is

m^{n}−∑_{k=1}^{m}(−1)^{k+1}\binom{m}{k}(m−k)^{n} = m^{n}+∑_{k=1}^{m}(−1)^{k}\binom{m}{k}(m−k)^{n} = ∑_{k=0}^{m}(−1)^{k}\binom{m}{k}(m−k)^{n}

In the special case where |A| = |B| = n, a function f : A → B is a surjection if and only if it is a bijection. The number of bijections between two sets of size n is n!. Therefore we have the remarkable equation

n! = ∑_{k=0}^{n}(−1)^{k}\binom{n}{k}(n − k)^{n}