CMSC 27100 — Lecture 17

Generalized Permutations and Combinations

Sometimes, rather than picking a bunch of things from a fixed set, we may want to choose some objects from a set of types of things.

Example 17.1. Suppose you're ordering six scoops of ice cream and there is a choice of four types, say cookies & cream, pralines & cream, salted caramel, and gold medal ribbon. How many different combinations can you make, with repetition? For an ordinary combination, we would only choose one of each flavor, but because we're concerned about classes of objects rather than single objects, we're able to choose multiples of a particular type.

Let's begin by considering one possible selection, $C,P,G,C,C,G$ (three cookie, one praline, two gold), assuming this is the order in which we chose our scoops. However, since this is a combination and some of the elements are indistinguishable anyway, the order doesn't really matter, so let's group them together into $CCCPGG$. Now, let's separate these so they don't touch each other and cross contaminate the flavours or something, and we have something that looks like $CCC|P|GG$.

We can play with this analogy further and suppose we have a cup for each flavor, regardless of the number that we end up choosing, so we have something like $CCC|P||GG$. Finally, we note that since each cup contains a specific flavor, we don't need to specifically denote the flavor, and we can represent our choice by $***|*||**$.

Let's consider another possible choice: $*||*|****$, which is one cookies & cream, one salted caramel, and four gold medal ribbon. What we observe is that each choice of six items from four classes can be represented by an arrangement of six stars representing the items and three bars representing the division of classes of items.

But this is something we've already seen before: it's just a string problem over the alphabet $\{*,|\}$. Since we have six objects and four classes, we can view our possible selections as a string of length 9 with 6 $*$s and 3 $|$s and ask how many such strings there are. There are $$\binom 9 6 = \binom 9 3 = \frac{9!}{6!3!} = \frac{9 \cdot 8 \cdot 7}{3 \cdot 2 \cdot 1} = 3 \cdot 4 \cdot 7 = 84$$ such strings.

This method of using stars and bars to denote the objects and categories was popularized by William Feller's An Introduction to Probability Theory and its Applications in 1950.

Theorem 17.2. There are $\binom{r+n-1} r = \binom{r+n-1}{n-1} = \frac{(r+n-1)!}{r!(n-1)!}$ $r$-combinations from a set $A$ of $n$ elements with repetition.

Proof. We can view each possible selection as a string of length $r+n-1$ over the alphabet $\{\star,|\}$. We know that each string contains exactly $r$ $\star$s and $n-1$ $|$s. Then there are $\binom{r+n-1}{r}$ possible ways to choose spots for the $r$ $\star$s. Since all remaining spots must be occupied by $|$s, this is the same as choosing spots for $n-1$ $|$s, and there are $\binom{r+n-1}{n-1}$ ways to do so. $\tag*{$\Box$}$

Example 17.3. How many solutions to $x+y+z = 13$ are there, for $x,y,z \in \mathbb{N}$? Here, we can think of $x,y,z$ as our types of objects, of which we want to choose 13 in some combination. For instance, one solution would be to choose 6 $x$s, 4 $y$s, and 3 $z$s, which would give us $6+4+3 = 13$. Then the number of solutions is just $$\binom{13+3-1}{13} = \frac{15!}{13!2!} = \frac{15 \cdot 14}{2} = 105.$$

Just like with generalizing combinations, we can also think about how to generalize permutations.

Example 17.4. How many distinguishable permutations of the word $ACGACGA$ are there? There are two approaches we can take. The first is something we've seen already, by counting the number of ways to choose positions in a word. Here, we have three $A$s, two $C$s, and two $G$s. So we can choose three of seven positions for the $A$s and there are $\binom 7 3$ ways to do so. This leaves four spots. We choose two for the $C$s and there are $\binom 4 2$ ways to do so, leaving two spots for the two $G$s with $\binom 2 2$ ways to place them. In total, we have $$\binom 7 3 \binom 4 2 \binom 2 2 = \frac{7!}{3!4!} \cdot \frac{4!}{2!2!} \cdot \frac{2!}{2!0!} = \frac{7!}{3!2!2!} = 210.$$

The other way to consider this problem is to suppose that each symbol of our word is distinguishable, by adding marks to each symbol in some way. So suppose we have $A_1 C_1 G_1 A_2 C_2 G_2 A_3$. It is clear that there are $7!$ permutations of this word. However, we know that these symbols aren't really distinguishable, so we treat each such permutation as equivalent. For instance, there are $P(3,3) = 3!$ permutations of $A_1 A_2 A_3$ and we know these are equivalent once we make these indistinguishable. By removing all the indistinguishable permutations for each symbol, we get $$\frac{7!}{3!2!2!}$$ as before.

Theorem 17.5. The number of different permutations of $n$ objects, where there are $n_i$ indistinguishable objects of type $i$ for $1 \leq i \leq k$ is $$\frac{n!}{n_1! n_2! \cdots n_k!}.$$

These are called multinomial coefficients and are denoted $\binom{n}{n_1,n_2, \dots, n_k}$. As you might guess, these are the coefficients that we'd get if we generalized the binomial theorem to multinomial terms. In particular, $$\binom{n}{n_1, n_2, \dots, n_k} = \frac{n!}{n_1! n_2! \cdots n_k!}$$ is the coefficient for the term $(x_1^{n_1} x_2^{n_2} \cdots x_k^{n_k})$ in $(x_1 + x_2 + \cdots + x_k)^n$.

(Metaphorical) Boxes and (metaphorically) putting things in boxes are a popular formulation for combinatorial problems. There are a few variations, depending on whether the objects or the boxes are distinguishable or indistinguishable. This gives us four different kinds of problems.

If our boxes are distinguishable, then we'll see that we can apply the generalized counting techniques we've seen today.

Example 17.6. Suppose you've narrowed down a list of courses you might want to take in the 2022-2023 year to 14. Assuming every course on your list is offered every quarter, how many different ways to take 3 courses per quarter are there? This is the case of distinguishable items (courses) into distinguishable boxes (quarters). In the autumn quarter, you take 3 and there are 14 courses to choose from, so there would be $\binom{14}{3}$. For the winter quarter, you'd have 11 courses left to choose from, giving you $\binom{11}{3}$ possibilities, leaving $\binom 8 3$ choices for the spring quarter. Then this gives us $$\binom{14}{3} \binom{11}{3} \binom 9 3 = \frac{14!}{11!3!} \frac{11!}{8!3!} \frac{8!}{5!3!} = \frac{14!}{3!3!3!5!}$$ possible choices in total. This looks suspiciously like a number of distinguishable permutations with repeated elements. One way to think about this is to play the same trick that we did with the stars and bars and think about strings. If we want to dispense 14 objects, we consider a string of length 14, with each spot corresponding to an object. Then we assign that position a symbol $A,W,S,N$ for autumn, winter, spring, or none. Then this becomes exactly our permutation with repetition problem from above, with 3 $A$s, $W$s, and $S$s and 5 $N$s.

Example 17.7. Suppose that you go to a canned tomato factory and grab six unlabelled cans off of the assembly line. How many different ways are there to brand your premium tomatoes if you have four types of labels? This is the case of indistinguishable items (cans of tomatoes) and distinguishable boxes (labels). This turns out to be identical to combinations with repetitions. We have six objects that we need to assign four types. Then this is just $$\binom{6+4-1}{6} = \frac{9!}{3!6!} = \frac{9 \cdot 8 \cdot 7}{3 \cdot 2 \cdot 1} = 3 \cdot 4 \cdot 7 = 84.$$ In other words, we can think of the act of taking $n$ generic objects from $k$ distinct types in the same way as putting $n$ generic objects things into $k$ distinct boxes.

Now, if our boxes are indistinguishable, the problem is much harder and there aren't any "nice" ways to compute the following numbers except to enumerate the possibilities.

Example 17.8. Suppose you're moving and you pack a cast iron skillet, a saucepan, a stainless steel skillet, and an enameled cast iron dutch oven into three boxes but forgot to label them. How many possible ways could you have packed them? This is the case of distinguishable items (cookware) and indistinguishable boxes (unlabelled boxes). Essentially, what we would like to do is take our $n$ objects and distribute them into $k$ sets. So in our case, if we label our cookware by $1,2,3,4$, then some possible distributions include $\{\{1\},\{2\},\{3,4\}\}$, $\{\{1,2,3\},\{4\},\emptyset\}$, and $\{\{1,2,3,4\},\emptyset,\emptyset\}$. But, if you remember our definitions from set theory, you'd remember that the last one would be $\{\{1,2,3,4\},\emptyset\}$. This means we need to account for the number of empty/non-empty boxes when counting.

It turns out that the number of all of these sets can be described by using Stirling numbers of the second kind. The Stirling number of the second kind for $n$ and $j$ is defined by $$\genfrac\{\}{0pt}{} n j = \frac 1 {j!} \sum_{i=0}^{j-1} (-1)^i \binom j i (j-i)^n.$$ This number describes the number of ways to distribute $n$ objects into exactly $j$ non-empty boxes. Then the total number of ways to distribute $n$ distinguishable objects into $k$ boxes where boxes can be empty is $$\sum_{j=1}^k \genfrac\{\}{0pt}{} n j = \sum_{j=1}^k \frac 1{j!} \sum_{i=0}^{j-1} (-1)^i \binom j i (j-i)^n.$$ As you might expect/hope, this is not something we'll get into further.

Example 17.9. Suppose you're moving and you pack six black t-shirts into four identical suitcases. How many ways can you distribute the t-shirts? This is the case of indistinguishable objects (black t-shirts) into indistinguishable boxes (identical suitcases). Again, we can enumerate these. This problem is equivalent to asking to find solutions to $a_1 + a_2 + a_3 + a_4 = 6$, with $0 \leq a_1 \leq a_2 \leq a_3 \leq a_4 \leq 6$. This looks similar to the combination with repetitions problem above, but the difference here is that the "order" in which the coefficients are assigned doesn't matter (this is enforced by the ordering condition on the $a_i$'s). Such a choice for $a_1, a_2, a_3, a_4$ is called a partition of an integer $n$ (6) into at most $k$ (4) positive integers. These are described by the partition numbers and have no simple closed form.