Lecture 13: Generalized Permutations and Combinations
\( \newcommand{\set}[1]{\{#1\}} \newcommand{\comprehension}[2]{\{#1\,\vert\,#2\}} \newcommand{\size}[1]{\left\vert#1\right\vert} \newcommand{\true}{\top} \newcommand{\false}{\bot} \newcommand{\limplies}{\rightarrow} \newcommand{\divides}{\mathbin{\vert}} \newcommand{\mult}{\mathbin{\cdot}} \newcommand{\xor}{\oplus} \newcommand{\union}{\cup} \newcommand{\intersect}{\cap} \newcommand{\complement}[1]{\overline#1} \newcommand{\powerset}{\mathcal{P}} \newcommand{\ixUnion}{\bigcup} \newcommand{\ixIntersect}{\bigcap} \newcommand{\Div}{\mathrm{div}} \newcommand{\gcd}{\mathrm{gcd}} \newcommand{\divmod}{\mathop{\mathbf{divmod}}} \newcommand{\div}{\mathop{\mathbf{div}}} \newcommand{\mod}{\mathop{\mathbf{mod}}} \newcommand{\ceiling}[1]{\lceil#1\rceil} \newcommand{\floor}[1]{\lfloor#1\rfloor} \)The midterm will be in class, Wednesday of 6th week, February 13. If you have an examination accommodation, please make the necessary arrangements with Student Disability Services to schedule your exam, and please choose a time that substantially overlaps with the in-class final.
The lecture will cover material through Lecture 13, inclusive.
Combinations with Repetition
Example 13.1 Let's start by considering a variant of an un-starred exercise from a couple lectures back. Assume you walk by the McDonald's near the intersection of Ontario and Clark, and this makes you hungry for pizza. So you decide to walk to the Giordano's Pizza at Rush and Superior, which is 3 blocks north, and 4 blocks east. (I'll walk a good way for decent pizza, myself!) How many direct routes (i.e., traveling only north or east) through the network of streets are possible?
Let's start with an idealized version of this problem, in which we have a directed graph whose vertices represent real-world intersections, and whose edges represent connected streets, oriented according to our intended direction of travel:
One way to approach this problem is via a simple dynamic program. We know that the number of viable routes from Rush and Superior to Rush and Superior is one—corresponding to the empty path. And in general, the number of routes from any other node will be the sum of the number of routes from each of its children. Adapting this plan to the graph, we have:
From which we can read off the answer of 35 routes. Of course, we might recognize this a rotated rectangle within Pascal's triangle:
So another way of answering this is that there are $7 \choose 3$ routes, and this looks like more than a coincidence.
Another way we might think about this problem is to imagine that we're going to direct a robot to make the trip from McDonald's to Giordano's. In this case, we might think about providing the robot with a simple sequence of instructions—north, east, east, north, east, north—resulting in the following path:
This reduces the problem of counting paths to the problem of counting programs that traverse the paths. In this case, we easily see that all of the valid programs must have seven steps, precisely three of which must be “north,” i.e., and since there are $7 \choose 3$ distinct program of this form, there are as many distinct paths. So, not a coincidence.
Example 13.2 Here's another example (adapted from Rosen) that we can treat in a similar way. How many different ways can we select five bills of varying denomination from a cash drawer that has at least five each of $\$$100-, $\$$50-, $\$$20-, $\$$10-, $\$$5-, and $\$$1-dollar bills? (Note here that we're ignoring $\$$2-bills, because everyone but Rosen does.) To be clear here, the order doesn't matter, neither do we attempt to distinguish between different bills of the same denomination. Again, we can reduce the counting problem to designing an abstract machine that doles out sets of bills, and then counting the number of programs for that machine that dole out precisely five bills. Our money robot has 6 cash trays, laid out sequentially, and a dispenser (indicated by an arrow below):
We'll again imagine that the robot has two commands, “dispense” which dispenses a bill from the current tray, and “right” which shifts the dispenser mechanism one tray to the right. A full program will involve 5 dispense instructions, and 5 shift instructions, so the problem reduces to counting the number of 10-instruction programs with 5 dispense instructions, i.e., ${10 \choose 5} = 252$.
The situation of the these two examples is called combinations with repetition, i.e., we assume that the original set has a few classes of elements that are indiscernible except with respect to class, and we're interested in the number of recognizably different collections (sometimes called “bags,” to differentiate them from sets, as multiplicity matters) can be formed of a given size. Generalizing from the examples above, we have
Theorem 13.3 There are ${n + r -1 \choose r} = {n+r-1 \choose n-1}$ $r$-combinations from a set $A$ with $n$ distinct elements, when repetition is allowed.
Proof We can build a robot for generating $r$-combinations with repetition, much as we did with the cash example, where the instructions are “dispense” or “next,” the latter indicating that we should move on to the next element to dispense members of the collection from. A valid program will have $r$ “dispense” instructions, and $n-1$ “next” instructions, reducing the problem to choosing $r$ elements from a set of size $n+r-1$ without repetition.
$\Box$ Theorem 13.3
Example 13.4 The local Dunkin' Donuts has thirty varieties of donuts. How many distinct ways can a box of a dozen donuts be filled?
We're just asking for $12$-combinations of a $30$-element set, with repetition/replacement. So, ${30 + 12 - 1 \choose 12} = 7,898,654,920$. Note that this would require making $12 * {30 + 12 - 1 \choose 12} / 30 = 3,159,461,968$ of each variety. It's time to make the donuts!
Example 13.5 How many solutions are there in the non-negative integers to the equation $x_1 + x_2 + x_3 = 11$?
This amounts to drawing 11 balls from a bag of red, blue, and yellow balls, and counting the distinct combinations. So, $11$ combinations of $3$ elements with repetition give us ${11 + 3 - 1 \choose 11} = {13\choose 2} = 78$ distinct solutions.
Example 13.6 Consider the same problem, but with the constraint that $x_i \geq 2$ for $i\in\set{1,2,3}$.
This amounts to taking out two balls of each color first, essentially reducing the problem to selecting $5$ balls of $3$ different colors. So we're looking for $5$-combinations with replacement from a $3$-element set. So, by the theorem above, ${5+3-1 \choose 5} = {7 \choose 2} = 21$ distinct solutions to the constrained equation.
Example 13.7 Consider the following Swift code fragment:
var k:Int
k = 0
for i1 in 1...10 {
for i2 in i1...10 {
for i3 in i2...10 {
for i4 in i3...10 {
k += 1
}
}
}
}
print(k)
What gets printed? Well, we could just run it...
715
That's not very interesting. Can we think about this in a better way? All we're really doing is enumerating bags containing $l_1$, $l_2$, $l_3$, and $l_4$ such that $1 \leq l_1 \leq l_2 \leq l_3 \leq l_4 \leq 10$. Again, we can think about this in terms of an idealized robot tasked to produce such a sequence. It starts with an internal counter initialize to $1$, and has two instructions: “increment” which increases the counter, and ”emit” which emits the value held by the counter. E.g., if we abbreviate these instructions by the letters ‘I’ and ‘E’ respectively, "IIEEIEIIIEIII" corresponds to $0\leq 3 \leq 3 \leq 4 \leq 7$. So we're looking for $4$ combinations with repetition from a $10$ element set, i.e., ${10 + 4 - 1 \choose 4} = 715$, as advertised.
If we generalize the top end of the loops from $10$ to $n$, and the number of for loops from 4 to $r$, clearly, we'll be counting (the hard way) the number of $r$-combinations with repetition from an $n$ element set, i.e., $n+r-1 \choose r$.
Permutations with Repetition
Example 13.8 How many distinguishable permutations of the word “SUCCESS” are there?
Rosen attacks this one way, we'll attack it another. We'll give a combinatorial proof, which involves equating two different ways of counting the same collection. In this proof, the number we're looking for will be on one side, and not the other, enabling us to solve.
Imagine that first make the letters distinguishable, e.g., $\text{S}_1\text{U}_1\text{C}_1\text{C}_2\text{E}_1\text{S}_2\text{S}_3$. We can count the number of permutations of these (now distinguishable) letters two different ways. First, would just jump to the answer, $P(7,7) = 7!$. Next, we could imagine generating all of the permutations where the order isn't distinguishable (the $n$ we're looking for), times the number of ways to distinguish each of the letters, $P(3,3)=3!$ for ‘S’, $P(1,1)=1!$ for ‘U’, $P(2,2)=2!$ for ‘C’, and $P(1,1)=1!$ for ‘E’. Thus, we have
\begin{align*} 7! &= n \cdot 3! \cdot 1! \cdot 2! \cdot 1! \\ \end{align*}which we solve for $n$:
\begin{align*} n &= {7! \over 3! \mult 1! \mult 2! \mult 1!} = 420\\ \end{align*}These numbers are known (although only mentioned in Rosen in Exercise 63 on page 434) as multinomial coefficients based on a straight-forward generalization of the binomial theorem to powers of higher multinomials. In the standard notation, we'd describe the solution above as $7 \choose 3,1,2,1$, and in general, if $n_1 + n_2 + \ldots n_k = n$, the multinomial coefficient
\begin{align*} {n \choose n_1,n_2,\ldots,n_k} &= {n! \over n_1! \mult n_2! \mult \cdots \mult n_k!} \end{align*}This will be the coefficient of $x_1^{n_1}x_2^{n_2}\cdots x_k^{n_k}$ in $(x_1 + x_2 + \cdots + x_k)^n$, hence the name.
Exercise 13.9 Prove the multinomial theorem, Exercise 63 on page 434 of Rosen.
*Exercise 13.10 How many distinguishable permutations of the word “MISSISSIPPI” are there?
Distributing Objects into Boxes
There's a broad class of problems that involve taking a collection of objects (which may be distinguishable or indistinguishable) and distributing some or all of them among a collection of containers/boxes (which likewise may be distinguishable or indistinguishable). We'll sometimes use the synonyms labelled and unlabelled for distinguishable and indistinguishable, respectively.
Example 13.11 (Distinguishable objects, distinguishable boxes) How many ways can we distribute $5$ cards from a standard deck of $52$ cards to each of $4$ players?
We'll approach this problem two different ways. First, we can simply dole out cards to each player. There are $52 \choose 5$ ways to give cards to the first player, leaving $52-5 =47$ cards remaining, and so $47 \choose 5$ ways to give cards to the second player, $42 \choose 5$ ways to give cards to the third player, and $37\choose 5$ ways to give cards to the fourth player.
But now,
\begin{align*} {52 \choose 5} {47 \choose 5} {42 \choose 5} {37 \choose 5} &= {52! \over 5! \, 47!} \mult {47! \over 5! \, 42!} \mult {42! \over 5! \, 37!} \mult {37! \over 5! \, 32!}\\ &= {52! \over 5! \, 5! \, 5! \, 5! \, 32!}\\ &= {52 \choose 5,5,5,5,32} \end{align*}The emergence of the multinomial coefficient here suggests that there may be an alternative way of counting that results in a more direct calculation. In this case, we can consider strings of length $52$ over the alphabet $\set{1,2,3,4,*}$, which consist of five $1$'s, five $2$'s, five $3$'s, five $4$'s, and thirty-two $*$'s. Each such string can be thought of as specifying deal of the hand, but rather than shuffling the deck, it's shuffling the locations in a fixed deck from which the cards are drawn at each stage of the deal. Of course, we've seen how to count such strings, and the multinomial coefficient $52 \choose 5,5,5,5,32$ follows immediately.
Example 13.12 (Indistinguishable objects, distinguishable boxes) Three identical tabby kittens are to be distributed to four families, the Smiths, the Joneses, the Browns, and the Millers. How many different ways can this be done?
It is natural to think of this as the number of $3$-combinations with repetition from a $4$ element set, so the answer, as we've seen before, is ${3+4-1 \choose 3} = {6\choose 3} = 20$.
The problems with indistinguishable boxes turn out to be harder, without closed form solutions (unless we invent new closed forms).
Example 13.13 (Distinguishable objects, indistinguishable boxes) Let's say we have $3$ identical gift boxes, and $4$ gifts to be packed in these boxes. How many distinguishable outcomes exist?
It's tempting to believe we can approach this as a problem with distinguishable boxes, and then divide through by the number of permutations of the boxes that are possible. Thus, we'd have $3^4$ ways to distribute $4$ distinguishable items among $3$ boxes, and $3!$ many ways of permuting the distinguishable boxes, which suggests that the answer is $3^4 \over 3!$. Right away, it's clear that something's gone amiss, as the result isn't an integer! So, what breaks down? What we're trying to do is to distinguish boxes based on their content, and so we might generate $[\set{1},\set{2,3}.\set{4}]$ and every permutation of the boxes gives rise to a distinct item in the labelled boxes case. The problem comes when we have multiple empty boxes, e.g., $[\set{1,2,3,4},\emptyset,\emptyset]$ In this case, we can permute the last two items, but still have the same object when viewed in terms of unlabeled boxes. A more complete development of this requires more time than we can devote to the topic, but would typically be covered in a combinatorics class, under the guise of Stirling numbers of the second kind.
Example 13.14 (Indistinguishable objects, indistinguishable boxes) How many ways can we pack $6$ identical books into $4$ identical boxes?
This problem, like the last, can be attacked via a more-or-less direct enumeration of the possibilities, giving rise to $9$ ways. This is essentially the same problem as finding solutions to the equation $a_1 + a_2 + a_3 + a_4 = 6$, subject to the constraint $0 \leq a_1 \leq a_2 \leq a_3 \leq a_4 \leq 6$, and indeed, this sort of equivalence guides our enumeration. We can think a solution as specifying a way to partition $6$ elements into $4$ classes, giving rise to the partition numbers. Unfortunately, like Stirling numbers of the second kind, there is no simple closed form for partition numbers.
Exercise 13.15 Exercise 44, page 433 of Rosen.