Massachusetts Institute of Technology Handout 47 6.042J/18.062J: Mathematics for Computer Science November 6, 1998 Professors N. Lynch and S. Devadas

Notes for Recitation 9 (11/6/98)

1 Balls and Bins

1.1 Identical vs Distinguishable Balls and Bins

In lecture we saw two results on the number of ways of putting balls into bins under different assumptions.

1. There are n^{r} ways to put r distinct balls into n distinct bins.

2. There are

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

ways to put r balls into n bins when the balls are identical and the bins are distinct.

There are other two cases that could be of interest: when the balls are distinct and the bins are identical, and when both balls and bins are identical. In the first case, there is a complicated formula, in the second case, the problem has to be solved by case analysis (see Figure 1.)

Bins are distinct Bins are identical
Balls are distinct n^{r}  complicated formula
Balls are identical \binom{n+r−1}{r}  case analysis

Figure 1: Number of ways of putting r balls into n bins.

For example, consider the problem of putting 5 different balls into 3 identical bins (i.e. the problem of dividing 5 distinct object into at most 3 groups). The partition of balls into bins can have one of the following patterns:

• (5, 0, 0): all the balls are in the same bin. This case arises only once.

• (4, 1, 0): a bin is empty, a bin gets one ball, the other bin gets the remaining 4 balls. There are 5 ways to get this case (corresponding to the number of ways to choose the ball that goes alone in one bin).

• (3, 2, 0): this case arises \binom{5}{3} = 10 times (corresponding to the number of ways to choose the three balls that go together in one bin).

• (3, 1, 1): this case arises \binom{5}{3} = 10 times.

• (2, 2, 1): this case arises 5 · \binom{4}{2} · \frac{1}{2} = 15 times. This is the trickier case. There are 5 ways to choose the ball that goes alone in one bin, and then there are \binom{4}{2} · \frac{1}{2} = 3 ways to partition the remaining 4 balls into two indistinguishable bins so that there are two balls in every bin. We have to divide by two since \binom{4}{2} counts the number of subsets of size 2 of a set of 4 elements, which is also the number of ways to arrange 4 distinct balls into 2 distinct bins.

Thus, there are 1 + 5 + 10 + 10 + 15 = 41 ways to put 5 different balls into 3 identical bins.

What is the number of ways to put 5 identical balls into 3 identical bins? We have to repeat the previous case analysis, however now each of the previous cases can occur only once, so the answer is simply 5.

1.2 Distinguishable Balls into Identical Bins

How many ways are there of putting r distinct balls into n identical bins?

We will set up a many-to-one correspondence between this problem and the problem in Question 1. Namely, for each way to put the balls in indistinguishable bins, we can distinguish these bins in n! ways – just number the bins in every possible way. Morever, every arrangement of r distinguishable balls in n distinguishable bins is associated in this way with some arrangement of r distinguishable balls in n indistinguishable bins – just take the numbers off the bins. Thus, we have a n!-to-1 correspondence. So is the answer simply \frac{n^{r}}{n!} ?

For example, with n = 3, and r = 2, we get \frac{3}{2}. This can’t be right!

The error is: Our correspondence is not always n!-to-1. Some configurations with indistinguishable bins match up with fewer than n! configurations with distinguishable bins. For instance, suppose that there are four balls, 1, 2, 3, 4, and three indistinguishable bins. One arrangement is:

(1) (2 4) (3)

If we now label the urns by their positions, then the above arrangement certainly does correspond to 3! = 6 different arrangements with distinguishable bins. But suppose that our initial arrangement before we gave bins labels was:

(1 2 3 4) () ()

Now, if we label the bins by position, and then switch the last two bins, we are left with exactly the same label arrangement: four balls in one bin, and no balls in eithr bin two or bin three. There are only three choices for where the set of balls can be put.

Our n!-to-1 correspondence breaks down only when two or more bins are empty. So for the moment, let us just worry about arrangements in which no bin is empty.

Define T (r, n) to be the number of ways to put r distinguishable balls into n distinguishable bins, with no empty bins.

Define S(r, n) to be the number of ways to put r distinguishable balls into n indistinguishable bins, with no empty bins.

Then we really do have a n!-to-1 correspondence between the things counted by T (r, n) and S(r, n), so

S(r, n) = \frac{1}{n!}T (r, n)

Next, let B(r, n) equal the number of ways to put r distinguishable balls into n indistinguishable bins, with empty bins allowed. This is the answer we want. Because the bins are indistinguishable, if k of them are empty, it does not matter which k. It is as if we only had n − k bins to start with. Thus,

B(r, n) = ∑_{j=0}^{n} S(r, j) = ∑_{j=0}^{n} \frac{T (r, j)}{j!}

We have not solved the problem but we have reduced it to another problem, we have seen before in Team Problems 8, the r engineers to n project assignment, so we know what T (r, n) is.

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

Finally, we can get

B(r, n) = ∑_{j=0}^{n} ∑_{k=0}^{j} \frac{(−1)^{k}}{j!} \binom{j}{k}(j − k)^{r}

as our answer. Now, if you compute the inner sum for different j, here’s what you get:

j = 0, k = 0, v = 0
j = 1, k = 0, v = 1 k = 1, v = 0
j = 2, k = 0, v = 16, k = 1, v = −1, k = 2, v = 0

j = 3, k = 0, v = 40.5, k = 1, v = −16, k = 2, v = 0.5, k = 3, v = 0

Summing up the v’s gives us 41, which is exactly what we computed using case analysis.

2 Multinomial Coefficients

The following theorem was proved in lecture using the Division Theorem.

Theorem 2.1. 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.

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 2.1, 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 alternate proof of Theorem 2.1.

Proof. (Alternate proof of Theorem 2.1.) 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 following generalization of the Binomial Theorem.

Theorem 2.2 (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}}

3 An Apparently Complicated Counting Problem

Here is an absurd counting problem. In how many ways can we fill a bag with n fruits subject to the following constraints?

• The number of apples must be even.

• The number of bananas must be a multiple of 3.

• There can be at most 2 oranges.

• There can be at most one pear.

For example, there are 7 ways to form a bag with 6 fruits:

Apples 6 4 4 2 2 0 0
Bananas 0 0 0 3 3 3 6
Oranges 0 2 1 1 0 2 0
Pears 0 0 1 0 1 1 0

This problem appears complicated and without much hope for a closed form solution for selecting n fruits. But we can actually use generating functions to find an answer.

First, we need a generating function for the number of fruit bags. Initially, we can consider each fruit separately. That is, we can count the number of fruit bags with just apples, then just bananas, pears, etc. For example, the number of fruit bags with 0 apples is one (the empty bag), the number of bags with 1 apple is zero (the number of apples must be even), the number of bags with 2 apples is one (the bag with two apples), etc. The generating functions for the four types of fruit are worked out below.

A(x) = 1 + x^{2} + x^{4} + x^{6} + … = 1/(1 − x^{2}),
B(x) = 1 + x^{3} + x^{6} + x^{9} + … = 1/(1 − x^{3}),
O(x) = 1 + x + x^{2}  = (1 − x^{3})/(1 − x),
P (x) = 1 + x.

Now from lecture, we know Theorem 3.1. Let A(x) and B(x) be ordinary generating functions for the number of ways to choose items, subject to given constraints, from disjoint sets A and B, respectively. The generating function for the number of ways to choose objects from the union A ∪ B subject to the same constraints is the product A(x) · B(x).

So the generating function for the number of ways to pick n fruits subject to the constraints above is the product of A, B, O and P:

OGF for fruit bags = A(x) · B(x) · O(x) · P (x)
= \frac{1}{1 − x^{2}} \frac{1}{1 − x^{3}} \frac{1 − x^{3}}{1 − x} (1 + x)
= \frac{1}{(1 − x)^{2}}
= 1 + 2x + 3x^{2} + 4x^{3} + …

The coefficient of x^{n} is simply n + 1; that is, the number of ways to form a bag of n fruits is just n + 1. This is consistent with the example we worked out, since there were 7 fruit bags with 6 fruits.

4 Team Problem

We consider an ingenious approach to counting well-matched parenthesis strings. Our approach will involve considering paths in the plane from a point (x_{1}, y_{1}) to (x_{2}, y_{2}) for x_{i}, y_{i} ∈ ℤ, where each step in the path is at a ±45 degree angle, increasing the x-coordinate by 1 and the y-coordinate by ±1. For example, a path might start at (1, 1) and make seven steps to the successive points (2, 0), (3, −1), (4, 0), (5, 1), (6, 2), (7, 1), (8, 0) as in Figure 2.

Problem 1. (a) Explain why the number of well-matched parenthesized strings of length 2n is the same as the number of paths from (0, 0) to (2n, 0) which only touch the x-axis at their endpoints. (That is, if 0 < i < 2n and (i, j) is a point on the path, then j > 0.) Solution: Interpret left paren as a “move up” step and right paren as a “move down” step. Then every string of k parens corresponds to a path of length k from the origin and vice-versa — a bijection. Remember in Recitation 2 Team Problem 2, we showed that the well-matched strings were the same as the well-counting strings. Well-counting strings correspond exactly to paths from the origin back to the x axis which don’t touch the x-axis in between endpoints.

(x_1, y_1)

(x_2, y_2)

Figure 2: A path from (1, 1) to (8, 0).

(b) How many paths are there from (x_{1}, y_{1}) to (x_{2}, y_{2})? (Express the answer as a binomial coefficient.) Solution:

#moves = x_{2} − x_{1}
#up moves − #down moves = y_{2} − y_{1}
#up moves + #down moves = #moves = x_{2} − x_{1}
#up moves = \frac{(x_{2} + y_{2}) − (x_{1} + y_{1})}{2} ::= u
#down moves = \frac{(x_{2} − y_{2}) − (x_{1} − y_{1})}{2} ::= d
#paths = \binom{u + d}{u} = \binom{u + d}{d}

(c) For y_{1}, y_{2} > 0, show that the number of paths from (x_{1}, y_{1}) to (x_{2}, y_{2}) which touch or cross the x-axis is equal to the number of paths from (x_{1}, −y_{1}) to (x_{2}, y_{2}). Solution: See Figure 3.

(d) Conclude that the number of well-matched strings of 2n parentheses equals the n − 1st Catalan number

\frac{1}{n}\binom{2n − 2}{n − 1}.

Solution:

(x_{1}, y_{1})

(x_{1}, −y_{1})

(x_{2}, y_{2})

Figure 3: Reflection of the initial part of a path.

#paths((1, 1) → (2n − 1, 1)) = \binom{2n − 2}{n − 1}

because

u = \frac{2n − 2}{2} = n − 1
d = \frac{(2n − 2) − 0}{2} = n − 1

#paths((1, 1) → (2n − 1, 1) touching x-axis) = #paths((1, −1) → (2n − 1, 1))

= \binom{2n − 2}{n} = \binom{2n − 2}{n − 2}

because

u = \frac{2n − 0}{2} = n
d = \frac{(2n − 2) − 2}{2} = n − 2

Handout 47: Notes for Recitation 9 (11/6/98) 10

#paths((1, 1) → (2n − 1, 1) above x-axis) = #paths((1, 1) → (2n − 1, 1)) − #paths((1, 1) → (2n − 1, 1) touching)

= \binom{2n − 2}{n − 1} − \binom{2n − 2}{n}

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

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

= \binom{2n − 2}{n − 1} − \frac{n − 1}{n}\binom{2n − 2}{n − 1}

= \binom{2n − 2}{n − 1} · \frac{1}{n}