Massachusetts Institute of Technology Lecture 17 6.042J/18.062J: Mathematics for Computer Science November 7, 2000 Professors Nancy Lynch and Srinivas Devadas

More on Permutations and Combinations

Topics for today:

• Properties of binomial coefficients

• The Binomial Theorem

• Inclusion/exclusion, revisited

• Permutations with repetition

• Combinations with repetition

Reading: Rosen 4.3, 4.6

The last two lectures concerned the number of ways to choose elements from a finite set. In particular, we considered the number of ways to choose r distinct elements where order does not matter (r-combinations) and where order does matter (r-permutations). We introduced binomial coefficients to count combinations.

In this lecture we consider some of the many identities that help us to work with binomial coefficients. Then we generalize our notion of combinations. We count the number of ways to choose r elements from a finite set where we are allowed to choose the same element repeatedly. Again, we look at both the case where order does not matter (r-combinations with repetition) and where order does matter (r-permutations with repetition).

1 Properties of Binomial Coefficients

Let’s review binomial coefficients.

Definition 1.1 Let n and r be naturals, 0 ≤ r ≤ n. Then

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

Special cases:

\binom{n}{1} = n
\binom{n}{0} = 1

This last case uses the convention that 0! = 1, and also coincides with the permutation model—there is just 1 permutation of no items.

\binom{n}{n} = 1  (note symmetry with previous)
\binom{n}{n − 1} = n  (more symmetry).

There are infinitely many interesting identities involving binomial coefficients. You can’t learn them all, but you can learn the basic ones and look others up/derive them as needed. You can prove them by algebra, or by “thought experiments” that establish combinatorial meanings for the left hand side (LHS) and right hand side (RHS) of the equation and argue that they are the same.

These identities are important because of how often binomial coefficients arise in analysis of algorithms (6.046) and probability (next week).

The first identity is one we have already seen:

Theorem 1.2 Suppose 0 ≤ r ≤ n. Then

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

Proof.

Algebraic:

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

Combinatorial thought experiment: The LHS is the number of ways to choose r elements from n. The RHS is the number of ways to choose n − r elements. Choosing a set of r is equivalent to choosing the set of n − r elements in its complement; more precisely, there is a bijection between the set of sets of r elements and the set of sets of n − r elements, given by set-complement. Thus, these two counts are equal.

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}/\binom{n}{r − 1} = (n − r + 1)/r.

Proof.

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

Figure 1: Bell Curve

This ratio is > 1 if r < \frac{n+1}{2} and < 1 if r > \frac{n+1}{2}. This says that the successive coefficients increase until r reaches \frac{n+1}{2} and then decrease, i.e., they are unimodal. Form a bell-shaped curve:

In fact, the binomial coefficients form a real bell curve. These arise on examinations in a natural way. Suppose that a test has n questions. Then the bell curve describes, for every r, the number of ways the student can get exactly r of the questions right, namely

\binom{n}{r}.

If we suppose that each student taking the test is doing random guessing, so equally likely to get each of the n questions right or wrong, then these coefficients turn out to be proportional to the number of students that get those numbers of questions right. (We’ll see this when we do probability.)

Another identity:

Theorem 1.4 Suppose 1 ≤ r ≤ n. Then

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

Proof.

Algebraic proof:

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

Combinatorial proof: Consider choosing a committee of size r and a leader, from n people. One way is to pick the leader first (n ways), then pick the other r −1 committee members from the remainder (\binom{n−1}{r−1} ways). Another way is to pick the r committee members first (\binom{n}{r} ways) and then pick a leader from among them (r ways). This implies (by product rule) that:

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

Now divide both sides by r.

Now an important theorem due to Pascal:

Theorem 1.5 (Pascal) Suppose 1 ≤ r ≤ n − 1. Then

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

This is probably our most important identity, since gives a kind of recurrence for binomial coefficients. Memorize it!

Proof.

Algebraic:

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

Combinatorial: We use case analysis (a tree diagram) and the sum rule. Let S = {1, …, n}. Let A be the set of r-element subsets of S. Let B be the set of r-element subsets of S that contain 1. Let C be the set of r-element subsets of S that don’t contain 1.

Then A = B ∪ C, and B and C are disjoint. So |A| = |B| + |C|, by the Sum Rule. But now we can get expressions for |A|, |B| and |C| as numbers of combinations:

• |A| = \binom{n}{r}.

• |B| = \binom{n−1}{r−1}. This is because r−1 other elements must be chosen from the n−1 elements excluding item 1.

• |C| = \binom{n−1}{r}. This is because r elements must be chosen from the n−1 elements excluding item 1.

So (by the Sum Rule)

\binom{n}{r} = |A| = |B| + |C| = \binom{n − 1}{r − 1} + \binom{n − 1}{r}.

Pascal’s theorem has a nice pictorial representation: The row represents n, starting with 0 in the top row. Successive elements in the row represent r, starting with 0 at the left. (Notice that it’s

Figure 2: Pascal’s triangle.

just the double-induction matrix “reshaped”.)

This triangle has lots of nice properties. Experiment with it. E.g., what happens if we add the coefficients in one row?

Theorem 1.6 Suppose n is any natural number. Then

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

Proof.

Algebraic: This proof demonstrates an induction and Pascal’s identity. The proof is by induction on n. Let P (n) be:

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

BASE: n = 0.

∑_{r=0}^{0} \binom{0}{r} = \binom{0}{0} = 1 = 2^{0}

INDUCTIVE STEP: Assume P (n), show P (n + 1), where n ≥ 0.

∑_{r=0}^{n+1} \binom{n + 1}{r} = \binom{n + 1}{0} + ∑_{r=1}^{n} \binom{n + 1}{r} + \binom{n + 1}{n + 1}

= 2 + ∑_{r=1}^{n} \binom{n + 1}{r}

= 2 + ∑_{r=1}^{n} (\binom{n}{r} + \binom{n}{r − 1})  by Pascal’s identity

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

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

= 2 · 2^{n}  by inductive hypothesis,

= 2^{n+1}.

Combinatorial: Again, we use case analysis and the sum rule for disjoint unions. There are 2^{n} different subsets of a set of n elements. Decompose this collection based on the sizes of the subsets. That is, let A_{r} be the collection of subsets of size r. Then the set of all subsets is the disjoint union ∪_{r}A_{r}. There are \binom{n}{r} subsets of size r, for r = 0, 1, …, n. Hence the theorem follows.

Theorem 1.7 (Vandermonde) Suppose 0 ≤ r ≤ m, n. Then

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

Proof.

Combinatorial: Again we use case analysis with the sum and product rules. 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. That’s the LHS. Now decompose this collection of choices based on how many of the chosen balls are blue. 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 gives the RHS.

We can also give an algebraic proof using induction on n. However, to do this, it’s useful to generalize the notion of binomial coefficient a little:

Definition 1.8 If r > n, define \binom{n}{r} to be 0.

This makes some kind of sense informally, because there aren’t any ways to choose more elements than there are in a set! Many of the usual binomial identities are still correct with this extension. In particular, Pascal’s theorem is still true if r ≥ n (it reduces trivially). So we will prove Vandermonde’s theorem without the restriction r ≤ m, n. This means that some of the terms in the statement of the theorem could be trivial terms, e.g., \binom{n}{k} could occur, where k > n. But these terms have value 0, so don’t really matter.

Proof.

Algebraic: Induction using generalized Pascal’s identity: Let P (n) be

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

This is the generalization of Vandermonde to remove any restrictions on the relative sizes of m, n, and r.

BASE: n = 0. Then

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

This latter equation is true because the only value of k for which the second factor isn’t 0 is k = 0. Hence P (0) is true.

INDUCTIVE STEP: Assume P (n) is true, show P (n + 1). We have:

\binom{m + (n + 1)}{r} = \binom{m + n}{r} + \binom{m + n}{r − 1} by generalized Pascal’s identity

= ∑_{k=0}^{r} \binom{m}{r − k}\binom{n}{k} + ∑_{k=0}^{r−1} \binom{m}{r − 1 − k}\binom{n}{k} by the inductive hypothesis

= ∑_{k=0}^{r} \binom{m}{r − k}\binom{n}{k} + ∑_{k=1}^{r} \binom{m}{r − k}\binom{n}{k − 1}  by change of vars

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

= \binom{m}{r}\binom{n}{0} + ∑_{k=1}^{r} \binom{m}{r − k}\binom{n + 1}{k}  by Pascal’s identity

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

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

Hence, P (n + 1) is true. So P (n) is true for all n.

2 The Binomial Theorem

An important theorem gives the coefficients in the expansion of powers of binomial expressions. It turns out they are binomial coefficients—thus the name!

2.1 The Theorem

Theorem 2.1 Suppose n ∈ ℕ. Then

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

Example 2.2 (x + y)^{4} = 1x^{4} + 4x^{3}y + 6x^{2}y^{2} + 4xy^{3} + 1y^{4}

Proof.

Algebraic: By induction, using Pascal’s identity.

Combinatorial: Consider the product

(x + y)^{n} = (x + y)(x + y)(x + y)(x + y) …

This product has n factors. To expand this product, we generate individual terms of the sums by selecting (in all possible ways) one of the two variables inside each factor to get an n-variable product. If we select k “x” variables and n − k “y” variables, we get a term of the form x^{k}y^{n−k}. Then we gather all those terms together. So how many ways do we get such a term? Each x^{k}y^{n−k} term selects x from k of the factors and y from the other n − k. So there are \binom{n}{k} ways of choosing which factors have x.

2.2 Identities via Binomial Theorem

The binomial theorem can be used to give slick proofs of some binomial identities, e.g.:

Theorem 2.3

∑_{k=0}^{n} \binom{n}{k} = 2^{n}.

Proof. Plug x = 1, y = 1 into binomial theorem.

Theorem 2.4

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

Proof. Plug x = −1, y = 1 into binomial theorem.

The combinatorial interpretation is as follows: the number of ways of selecting an even number of elements from a set of n equals the number of ways of selecting an odd number. This works for both even and odd n!

Example 2.5 Consider n = 5. We can choose an odd-size set \binom{5}{1} + \binom{5}{3} + \binom{5}{5} = 5 + 10 + 1 = 16 ways. We can choose an even-size set \binom{5}{0} + \binom{5}{2} + \binom{5}{4} = 1 + 10 + 5 = 16 ways.

Example 2.6 n = 6: There are 6 + 20 + 6 = 32 odd sets. There are 1 + 15 + 15 + 1 = 32 even sets.

For odd n, this is intuitive (choosing an even set leaves an odd set). For even n, it may be somewhat surprising—there is no obvious bijection between the even and odd sets.

Theorem 2.7

∑_{k=0}^{⌊ \frac{n}{2} ⌋} \binom{n}{2k} = 2^{n−1}.

Proof.

Algebraic: Add the equations in the two previous theorems. We get

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

The terms with k odd cancel out, while the even terms double, so we get:

2 ∑_{k=0}^{⌊ \frac{n}{2} ⌋} \binom{n}{2k} = 2^{n}.

Then divide by 2.

Combinatorial: The LHS represents the number of ways to pick an even number of elements from a set of n elements. The number of ways to pick an even number is equal to the number of ways to pick an odd number of elements. Since the total number of ways is 2^{n}, the number of ways to pick even is half this, or 2^{n−1}.

The Binomial Theorem also provides a new proof of Pascal’s identity:

Proof. We know that (x+y)^{n} = x(x+y)^{n−1} +y(x+y)^{n−1}. Consider the coefficient of x^{r}y^{n−r}. On the LHS this coefficient is \binom{n}{r} by the Binomial Theorem. On the RHS this coefficient is obtained by adding the coefficient of x^{r−1}y^{n−r} in the first term, plus the coefficient of x^{r}y^{n−1−r} in the second term. These are \binom{n−1}{r−1} and \binom{n−1}{r}, respectively (again by the Binomial Theorem).

It also gives a new proof of Vandermonde’s identity:

Proof. We know (1 + t)^{m+n} = (1 + t)^{m}(1 + t)^{n}. Consider the coefficient of t^{r}. On the LHS this is \binom{m+n}{r} by the binomial theorem. On the RHS, it is obtained by adding up, for all k, the product of the coefficient of t^{k} in the second factor and the coefficient of t^{r−k} in the first factor. This is

Σ_{k=0}^{r}\binom{n}{k}\binom{m}{r − k}.

Both of these new proofs are examples of another technique called “generating functions” that make it easy to manipulate series and recurrences. They package an entire sequence (in this case, the sequence of binomial coefficients) inside the Taylor expansion of a single function (in this case, (x + y)^{n}).

3 Principle of Inclusion and Exclusion

Now we return to the principle of inclusion-exclusion from last week. Our binomial coefficient identities give us a way to prove this theorem, via our alternating sum identity (proved by binomial theorem). Recall the Inclusion-Exclusion theorem:

Theorem 3.1

| ∪_{i} A_{i}| = Σ_{i}|A_{i}| − Σ_{i,j distinct} |A_{i} ∩ A_{j}| + Σ_{i,j,k distinct} |A_{i} ∩ A_{j} ∩ A_{k}| − ⋯

The theorem can be proved by induction on the number of sets, but this approach is messy, so LTTR. Instead we will give a combinatorial proof using binomial coefficients.

Proof. Each term in the summation counts certain elements in ∪_{i}A_{i}. We prove that every element of this union is counted exactly once. So, consider any particular element a, and suppose it is in exactly r of the sets A_{i}. We see how many times a is counted by each term.

In the first term, a is counted r = \binom{r}{1} times, once for each of the sets that contains it. In the second term, a is counted \binom{r}{2} times, once for each of the pairs of sets that contain it. In the third term, a is counted \binom{r}{3} times, …, and in the rth term, a is counted \binom{r}{r} = 1 times. The terms alternate signs, so the total number of times a is counted is:

\binom{r}{1} − \binom{r}{2} + \binom{r}{3} − … − (−1)^{r}\binom{r}{r}.

But Theorem 2.4 implies that

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

This implies that the sum above is equal to \binom{r}{0} = 1. That is, a is counted exactly once, as needed.

4 r-Permutations with Repetition

We now turn to permutations and combinations where elements are allowed to repeat. An rpermutation with repetition of a set S is the number of ways to choose r elements from S with repetition allowed and where order matters. For example, there are nine 2-permutations with repetition of the set S = {A, B, C}, which are listed below.

\begin{matrix}(A, A) & (A, B) & (A, C) \\ (B, A) & (B, B) & (B, C) \\ (C, A) & (C, B) & (C, C) \end{matrix}

4.1 Counting r-Permutations with Repetition

Fortunately, r-permutations with repetition are easy to count.

Theorem 4.1 The number of r-permutations with repetition of an n-element set is n^{r}.

For example, the theorem says that the number of 2-permutations with repetition of the 3-element set S = {A, B, C} is 3^{2} = 9, which checks with our previous answer.

Proof. Let S be a set with n elements. The r-permutations with repetition of S are precisely the elements of:

\underbrace{S × S × … × S}_{r terms}

By the Product Rule, this set has cardinality |S|^{r} = n^{r}.

4.2 Permutations with Limited Repetition

We might want to count the number of r-permutations where each element can be repeated a limited number of times. In general, this leads to some hairy analysis and no closed-form answer. Therefore, we will consider only a special case, the number of r-permutations where each element is repeated a precisely specified number of times.

For example, in how many ways can we arrange the letters in the word P EP P ER? This is equal to the number of 6-permutations of the set {P, E, R} where P is repeated 3 times, E is repeated 2 times, and R is repeated 1 time. (Since the total number of repetitions defines r, we will use the term “permutations” in place of “r-permutations” for the remainder of the section.)

Initially, suppose that we make all the letters distinct by adding subscripts. That is, we want the number of ways to arrange the letters P_{1}E_{1}P_{2}P_{3}E_{2}R. In this case, there are 6! = 720 arrangements because there are six choices for the first letter, five choices for the second letter, etc.

Next, suppose that we erase the subscripts on the E’s. This maps each arrangement of the letters P_{1}E_{1}P_{2}P_{3}E_{2}R to an arrangement of the letters P_{1}EP_{2}P_{3}ER. Since E_{1} and E_{2} could be ordered in 2! ways before the erasure, the mapping is 2!-to-1. For example, we have:

P_{1}E_{1}P_{2}P_{3}E_{2}R → P_{1}EP_{2}P_{3}ER

and

P_{1}E_{2}P_{2}P_{3}E_{1}R → P_{1}EP_{2}P_{3}ER

Therefore, by the Division Rule there are \frac{6!}{2!} = 360 arrangement of the letters in P_{1}EP_{2}P_{3}ER.

Finally, suppose that we erase the subscripts on the P ’s. This maps each arrangement of the letters P_{1}EP_{2}P_{3}ER to an arrangement of the letters P EP P ER. Since P_{1}, P_{2}, and P_{3} could be ordered in 3! ways before the erasure, this mapping is 3!-to-1. Therefore, by the Division Rule, the number of arrangements of the letters P EP P ER is \frac{6!}{2! 3!} = 60.

We can prove a general theorem using the same argument as in the P EP P ER problem.

Theorem 4.2 Let A be the set {a_{1}, a_{2}, …, a_{n}}, and let r_{1}, r_{2}, …, r_{n} be non-negative integers. The number of permutations of the set A where each element a_{i} is repeated exactly r_{i} times is:

\frac{(r_{1} + r_{2} + … + r_{n})!}{r_{1}! r_{2}! … r_{n}!}

For example, the theorem says that the number of permutations of {P, E, R} where P is repeated 3 times, E is repeated 2 times, and R is repeated 1 time is \frac{(3+2+1)!}{3! 2! 1!} = 60. This is the answer we found before.

Proof. (Sketch.) We initially make r_{i} distinct copies of each element a_{i}. Then the number of permutations where each element is repeated exactly once is (r_{1} + r_{2} + … + r_{n})!. We then “erase the subscripts” on the distinct copies of element a_{1}. This defines an r_{1}!-to-1 mapping from old permutations to permutations where a_{1} is repeated r_{1} times and all other elements are repeated once. Therefore the number of new permutations is \frac{(r_{1}+r_{2}+...+r_{n})!}{r_{1}!}. Continuing this way with a_{2}, a_{3}, …, we we find that the number of permutations where each element a_{i} is repeated exactly r_{i} times is \frac{(r_{1}+r_{2}+...+r_{n})!}{r_{1}! r_{2}! ... r_{n}!}.

4.3 Multinomial Coefficients

What is the number of permutations of the set A = {a_{1}, a_{2}} where a_{1} is repeated r_{1} times and a_{2} is repeated r_{2} times? According to Theorem 4.2, the answer is:

\frac{(r_{1} + r_{1})!}{r_{1}! r_{2}!} = \binom{r_{1} + r_{2}}{r_{1}}

We can restate the question as follows. How many strings contain r_{1} copies of the symbol a_{1} and r_{2} copies of the symbol a_{2}? This is equal to the number of ways to choose r_{1} distinct positions for the a_{1}’s from the set of all r_{1} + r_{2} positions, which is \binom{r_{1}+r_{2}}{r_{1}}. This is the same as the previous answer.

By shifting from “permutations” to “strings” in this way, we can give an alternative proof of Theorem 4.2.

Proof. (Alternative proof of Theorem 4.2.) There is a bijection between permutations of the set A = {a_{1}, a_{2}, …, a_{n}} where each element a_{i} appears exactly r_{i} times and strings where each symbol a_{i} appears exactly r_{i} times. Therefore, we can count permutations by counting strings as follows.

The number of ways to choose r_{1} distinct positions for the a_{1}’s from the set of all r_{1}+r_{2}+…+r_{n} positions is \binom{r_{1}+r_{2}+...+r_{n}}{r_{1}}. Then the number of ways to choose r_{2} distinct positions for the a_{2}’s from the set of all r_{2} + … + r_{n} remaining positions is \binom{r_{2}+...+r_{n}}{r_{2}}, and so forth. The total number of strings is therefore:

\binom{r_{1} + r_{2} + … + r_{n}}{r_{1}} · \binom{r_{2} + … + r_{n}}{r_{2}} · \binom{r_{3} + … + r_{n}}{r_{3}} ⋯ \binom{r_{n}}{r_{n}}

= \frac{(r_{1} + r_{2} + … + r_{n})!}{r_{1}! (r_{2} + … + r_{n})!} · \frac{(r_{2} + … + r_{n})!}{r_{2}! (r_{3} + … + r_{n})!} · \frac{(r_{3} + … + r_{n})!}{r_{3}! (r_{4} + … + r_{n})!} ⋯ \frac{r_{n}!}{r_{n}! 0!}

= \frac{(r_{1} + r_{2} + … + r_{n})!}{r_{1}! r_{2}! … r_{n}!}

The first equality uses the definition of binomial coefficients, and the second follows by cancelling terms.

The quantity \frac{(r_{1}+r_{2}+...+r_{n})!}{r_{1}! r_{2}! ... r_{n}!} is called a multinomial coefficient and is denoted \binom{r_{1}+r_{2}+...+r_{n}}{r_{1},r_{2},... ,r_{n}}. Given a set with r_{1} + r_{2} + … + r_{n} elements, the multinomial coefficient \binom{r_{1}+r_{2}+...+r_{n}}{r_{1},r_{2},... ,r_{n}} represents the number of ways to choose r_{1} elements, then r_{2} of the remaining elements, and so forth.

Multinomial coefficients also arise in the Multinomial Theorem, a generalization of the Binomial Theorem. The result is stated below, but not proved.

Theorem 4.3 (Multinomial Theorem)

(x_{1} + x_{2} + … + x_{n})^{r} = ∑_{r_{1}+r_{2}+...+r_{n}=r} \binom{r}{r_{1}, r_{2}, …, r_{n}}x^{r_{1}}x^{r_{2}} … x^{r_{n}}

5 Combinations with Repetition

Now we move from permutations with repetition to combinations with repetition. Let S be the set {A, B, C}. As we saw in the previous lecture, this set has three 2-combinations. That is, there are three ways to choose two distinct elements of S where order does not matter. The three 2-combinations of S are shown below.

{A, B} {A, C} {B, C}

Suppose that we are not required to choose distinct elements of S, but rather can choose the same element repeatedly. The resulting sets are called the r-combinations with repetition of the set S. Listed below are the six 2-combinations with repetition of S.

{A, B} {A, C} {B, C} {A, A} {B, B} {C, C}

Strictly speaking, these are multisets (bags), not sets, since an element may appear multiple times.

5.1 Counting r-Combinations with Repetition

The following theorem gives a nice formula for the number of r-combinations with repetition of an n-element set.

Theorem 5.1 The number of r-combinations with repetition of an n-element set is

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

In the example above, we found six ways to choose two elements from the set S = {A, B, C} with repetition allowed. Sure enough, the theorem says that the number of 2-combinations of a 3-element set is \binom{3+2−1}{2} = 6.

For comparison, recall that the number of ordinary r-combinations of an n-element set is \binom{n}{r}. Every ordinary r-combination is also a valid r-combination with repetition. So, as one would expect, the number of r-combinations with repetition is greater if r > 1.

The proof of this theorem uses an important trick called “stars and bars”.

Proof. Let S be a set with n elements that are ordered in some way. We will establish a bijection between r-combinations with repetition of the set S and strings of stars and bars.

Let R be a particular r-combination with repetition of S. Write down n − 1 bars. These n − 1 bars divide the line into n regions.

|  |  |  …  |

n − 1 bars define n regions

Put one star in the i-th region for each time that the i-th element of S appears in R. This procedure maps each r-combination with repetition to a string with r stars and n − 1 bars.

(For example, let S be the set {A, B, C, D, E}, with elements ordered alphabetically. Let R be the 7-combination with repetition {A, B, B, B, D, E, E}. The stars-and-bars string corresponding to R is shown below.

\underbrace{⋆}_{A} | \underbrace{⋆ ⋆ ⋆}_{B,B,B} | | \underbrace{⋆}_{D} | \underbrace{⋆ ⋆}_{E,E}

The two bars with no stars between indicate that element C never appears in R.)

This mapping is a bijection because it has an inverse. That is, given any stars-and-bars string, we can construct the corresponding r-combination with repetition. The number of stars in the first region determines the number of times that the first element of S appears in the r-combination, the stars in the second region determine the number of times that the second element appears, etc.

Since the mapping is a bijection, the number of r-combinations with repetition of an n-element set is equal to the number of strings containing n − 1 bars and r stars. The number of such strings is equal to the number of ways to choose r distinct positions for the stars in a string of n + r − 1 stars and bars. This is the number of ordinary r-combinations of a set with n + r − 1 elements, which is \binom{n+r−1}{r}.

5.2 Triple-Scoop Ice Cream Cones

Baskin-Robbins is an ice cream store that has 31 different flavors. How many different triple-scoop ice cream cones are possible at Baskin-Robbins? Two ice cream cones are considered the same if one can be obtained from the other by reordering the scoops. Of course, we are permitted to have two or even three scoops of the same flavor.

Of course, the best solution to this problem is to go to the Baskin-Robbins in Harvard Square and explicitly construct all possible combinations. This is called the consumption method. However, there is also a purely mathematical approach.

The number of triple-scoop ice cream cones is precisely the number of 3-combinations with repetition of the set of 31 flavors. Therefore, we can count the number of ice creams cones with the formula in Theorem 5.1 where n = 31 and r = 3. This gives:

\binom{31 + 3 − 1}{3} = \binom{33}{3} = \frac{33 · 32 · 31}{3 · 2 · 1} = 5456

On Thursdays the Harvard Square Baskin-Robbins is run by an irritating woman who refuses to serve a cone with two or three scoops of the same flavor. How many different triple-scoop ice cream cones are possible on Thursday?

Now we must select an ice cream cone by choosing 3 distinct flavors from the complete set of 31. Therefore, the number of different cones is the number of ordinary 3-combinations of a 31-element set. This is:

\binom{31}{3} = \frac{31 · 30 · 29}{3 · 2 · 1} = 4495

As we would expect, the number of combinations with repetition is greater than number number of combinations without repetition. Permitting scoops of the same flavor gives an extra 5456−4495 = 961 options.

5.3 Dozens of Dunkin Donuts

Suppose we next stagger down to the Dunkin Donuts in Central Square. We want a box of a dozen doughnuts and there are 21 varieties available. How many options do we have?

We select our box of doughnuts by pointing out 12 varieties from the complete set of 21 where repetition is allowed. Therefore, the number of options is the number of 12-combinations with repetition of a 21 element set. Applying Theorem 5.1 with n = 21 and r = 12, we find that number of different boxes of doughnuts is:

\binom{21 + 12 − 1}{12} = \binom{32}{12} = 225, 792, 840

5.4 Balls and Bins

Suppose that we have r identical balls and n distinct bins. In how many ways can we arrange the balls in the bins? There are six possibilities for the case of two balls and three bins, as shown below.

\underline{∘ ∘}

\underline{∘ ∘}

\underline{∘ ∘}

\underline{∘  ∘}
\underline{∘  ∘}
\underline{∘  ∘}

Claim 5.2 There are \binom{n+r−1}{r} ways to arrange r identical balls in n distinct bins.

Proof. Each arrangement of the r balls corresponds to an r-combination with repetition of the set of n bins. Specifically, if the i-th bin contains a_{i} balls, then the corresponding r-combination with repetition contains the i-th bin a_{i} times. Therefore, the number of arrangement of balls is equal to the number of r-combinations of an n element set, which is \binom{n+r−1}{r} by Theorem 5.1.

There is another way to prove the claim that uses a cute bijection between balls-and-bins arrangements and stars-and-bars strings. The six arrangements in the preceding example are redrawn below with some lines erased and the balls replaced by stars.

⋆ ⋆

⋆ ⋆

⋆ ⋆
⋆  ⋆
⋆  ⋆
⋆  ⋆

Now each balls-and-bin diagram has become a stars-and-bars string. The number of ways to place r balls in n bins is therefore equal to the number of strings with r stars and n − 1 bars, which is \binom{n+r−1}{r}.

5.5 Data Compression

Stars and bars can help solve a data compression problem. How many bits are needed to specify a multiset of N arbitrary integers in the range [0, 2N]? For example, how much disk space do we need to store one million numbers in the range zero to two million?

A Simple Scheme

One simple scheme is store each number in binary. With this approach, storing each number requires ⌈log_{2}(2N + 1)⌉ bits. Storing all N numbers requires N ⌈log_{2}(2N + 1)⌉ bits. In the case of a million numbers, we need 21 bits to store each number and therefore 21 million bits to store all of the numbers.

A Better Approach Using Stars and Bars

There is a more clever scheme that uses stars and bars. We can regard the multiset of numbers that we want to store as an N-combination with repetition of the (2N + 1)-element set [0, 2N]. The proof of Theorem 5.1 shows that such N-combinations with repetition correspond to strings of N stars and 2N bars. If we represent a star with a 0 and a bar with a 1, then we can store such a stars-and-bars string using N + 2N = 3N bits.

To make the scheme clear, suppose that we are storing a multiset of N = 5 numbers in the range [0, 10]. In particular, suppose that the numbers are {2, 4, 4, 6, 7}. We can represent this multiset as a stars-and-bars string and then with 3N = 15 bits as follows.

{2, 4, 4, 6, 7} → | | ⋆ | | ⋆ ⋆ | | ⋆ | ⋆ | | |
→ 1 1 0 1 1 0 0 1 1 0 1 0 1 1 1

As another example, we could store a million numbers in the range zero to two million using only 3 million bits, a factor of 7 improvement over the simple scheme. It is rather surprising that we need only 3 bits per number on average, no matter how large N becomes!

An Optimal Scheme

The stars-and-bars approach is simple and efficient, but not quite optimal.

In any scheme, we must associate every multiset of N numbers with a distinct binary string. From the stars-and-bars interpretation, we know that there are \binom{3N}{N} possible sets of N numbers. Therefore, we must be prepared to store any one of \binom{3N}{N} distinct binary strings. Using k bits, we can store at most 2^{k} different binary strings. This means that we need at least k bits where 2^{k} ≥ \binom{3N}{N}. This inequality is satisfied provided k ≥ ⌈log_{2} \binom{3N}{N}⌉. Therefore, as a lower bound, we

need at least ⌈log_{2} \binom{3N}{N}⌉ bits.

How far from optimal is the stars-and-bars scheme? To answer this question, we must rewrite the lower bound in a more familiar form. To this end, we can use Stirling’s Formula to approximate \binom{3N}{N} as follows.

\binom{3N}{N} = \frac{(3N)!}{(2N)! N!}

∼ \begin{matrix}\sqrt{2π(3N)} & (\frac{3N}{e} ) & 3N \\ \sqrt{2π(2N)} & (\frac{2N}{e} ) & 2N & \sqrt{2πN} & (\frac{N}{e} ) & N \end{matrix}

= \sqrt{\frac{3}{4πN}} (\frac{3^{3N}}{2^{2N}} )
= \sqrt{\frac{3}{4πN}} (\frac{27}{4})^{N}

With this formula, we can approximate the lower bound.

⌈log_{2} \binom{3N}{N}⌉ ∼ N log_{2} \frac{27}{4} − \underbrace{\frac{1}{2} log_{2} \frac{4πN}{3}}_{low-order term}

∼ 2.755 . . . · N

The stars-and-bars approach uses 3N bits, which is slightly more than the lower bound of about 2.755N bits.

This lower bound is actually not hard to achieve, though we will not cover the details. The idea is to order all of the multisets of N numbers in the range [0, 2N] and then index them 0, 1, 2, . . .. We then store a multiset by storing its index. The index is a number in the range 0 to \binom{3N}{N} − 1, which we can store in exactly ⌈log_{2} \binom{3N}{N}⌉ bits. Of course, the hard part is efficiently mapping a multiset to an index and vice versa. Nevertheless, we can store a million numbers in the range zero to two million with only 2.755 million bits.

5.6 r-Combinations with at Least One of Each Item

Suppose that Kaybee Toys carries balls in three delightful colors: red, blue, and green.^{1} In how many ways can we choose five balls so that we get at least one ball of each color?

We might as well start by choosing one ball of each color. Then we can choose the last two balls however we like. Remember that we are counting combinations, so the order in which we choose the balls does not matter.

Under this interpretation, the number of options is equal to the number of ways to choose two balls from the set of three colors with repetition allowed. Therefore, by Theorem 5.1 there are \binom{3+2−1}{2} = 6 possibilities. Here they are:

\begin{matrix}\{R, G, B, R, R\} & \{R, G, B, R, G\} & \{R, G, B, R, B\} \\ \{R, G, B, G, G\} & \{R, G, B, G, B\} & \{R, G, B, B, B\} \end{matrix}

This argument generalizes to give the theorem below.

1I bet you’re wondering if the 6.042 staff has discovered a lucrative scam involving product promotion in lecture notes. No comment.

Theorem 5.3 The number of r-combinations with repetition of an n-element set that contain every element in the set at least once is:

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

For example, in the colored balls problem, we have r = 5 and n = 3. The theorem says that there are \binom{5−1}{3−1} = 6 possibilities, which is consistent with our previous answer.

Proof. Every such r-combination consists of the entire n-element set together with an (r − n)- combination with repetition of the n-element set. By Theorem 5.1 the number of such combinations is:

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

The last equality uses the identity \binom{m}{k} = \binom{m}{m−k}.

How many n-combinations with repetition of an n-element set are there that contain every element in the set? In this case, Theorem 5.3 gives \binom{n−1}{n−1} = 1. This makes sense; the only such combination is the set S itself!

In how many ways can we arrange r identical balls in n distinct bins so that no bin is empty? If we first put one ball in each bin, then we can arrange the remaining r − n balls in \binom{n+(r−n)−1}{r−n} = \binom{n−1}{r−1} ways.

5.7 r-Combinations with Limited Repetition

Suppose that we want to count r-combinations where an element can be repeated only a limited number of times. For example, in how many ways can we arrange 10 identical balls in 4 distinct bins such no bin gets more than 7 balls? A good way to solve such problems is first to count the number of arrangements without a limit on repetition and then to subtract off the illegal arrangements.

The number of ways to arrange 10 identical balls in 4 distinct bins without a limit on repetition is \binom{4+10−1}{10} = 286.

Now we must count the illegal arrangements; that is, arrangements in which some bin contains 8 or more balls. Since there are only 10 balls in total, at most one bin can be overloaded with 8 or more balls. We can count the number of ways to overload the first bin by putting 8 balls into the first bin and then observing that the last two balls can be placed in \binom{4+2−1}{2} = 10 ways. Since any one of the four bins could be overloaded, the total number of illegal arrangement is 4 · 10 = 40.

Overall, there are 286 − 40 = 246 ways to arrange 10 balls in 4 bins so that no bin gets more than 7 balls.

Sometimes when there are limits on repetition, the number of illegal arrangements can itself be difficult to compute. In such cases, a messy inclusion-exclusion calculation may be necessary.

20 Lecture 17: More on Permutations and Combinations

6 Summary

The table below summarizes the basic results from our lectures about choosing r elements from an n-element set:

r-combinations without repetition = \binom{n}{r}
r-permutations without repetition = \frac{n!}{(n − r)!}
r-combinations with repetition = \binom{n + r − 1}{r}
r-permutations with repetition = n^{r}