CMSC 27100 — Lecture 15

Combinations

Now, suppose that order is not so important and we are only concerned about the selection of $r$ objects from a set of $n$ objects.

An $r$-combination of a set $A$ with $n$ elements is a subset of $r$ elements from $A$. The number of $r$-combinations of a set with $n$ elements is denoted $C(n,r)$ or $\binom n r$. This is read "$n$ choose $r$".

What you'll find is that everyone introduces the notation for combinations as some variant of $C(n,r)$, because $C$ is a nice mnemonic for "choose" or "combination" but then this is almost immediately dropped for the $\binom n r$ notation. The $\binom n r$ are called binomial coefficients for reasons that we'll get to next class (see, I said we'd drop $C(n,r)$ almost immediately).

So when considering the number of $r$-combinations, we are basically counting the number of subsets of size $r$. Recall that sets are unordered so this differs from permutations in that all we care about is whether an element gets chosen at all.

Thinking back to a three element set $A = \{1,2,3\}$, we observe that unlike permutations, there is only one 3-combination: $A$ itself. Then how many 2-combinations are there? Let's enumerate all of the subsets of $A$ of size 2: $$\begin{matrix} \{1,2\} & \{1,3\} & \{2,3\} \end{matrix}$$ Remember that since sets are not ordered, $\{1,2\}$ and $\{2,1\}$ are the same set.

So how many of these things are there?

If $n \gt 0$ and $0 \leq r \leq n$, then $$C(n,r) = \frac{n!}{r!(n-r)!}.$$

Suppose you and six of your friends decide to go somewhere for dinner and like fools, you all drive your own cars. When you get there, there are only three parking spots left. How many possible parking situations are there? In this case, it doesn't really matter who arrives first, second, and third, you just need to make sure not to be fourth. In this case, it makes sense to count the number of 3-combinations rather than 3-permutations. So we get $$C(7,3) = \frac{7!}{3!(7-3)!} = \frac{7!}{3! \cdot 4!} = \frac{7 \cdot 6 \cdot 5}{3 \cdot 2 \cdot 1} = 35$$ different ways where three people are happy and four people are stuck circling the parking lot.

Something you might have noticed when going through the previous example is that if we have $\binom 7 3 = \frac{7!}{3! \cdot 4!}$, then this looks the same as $\binom 7 4 = \frac{7!}{4! \cdot 3!}$. This is not a coincidence! First of all, this is very easy to verify.

For all $n \gt 0$ and $0 \leq r \leq n$, $C(n,r) = C(n,n-r)$.

Now, intuitively, what does this mean? Suppose we have a set of $n$ elements. We want to choose $r$ of these elements to form a subset. Then there are $n-r$ elements that weren't chosen. Alternatively, we can think of this as choosing $n-r$ elements to exclude from our subset, so that the remaining $r$ elements happen to form our subset. In both cases, we get the same result.

We say a word over a binary alphabet, say $\{0,1\}$, is balanced if it contains exactly as many $0$s as it does $1$s. How many balanced words of length $n$ are there? First of all, if $n$ is odd, then there are no balanced words of length $n$. So $n$ has to be even. At first, we might approach this like previous string problems, where we place things sequentially. However, we know exactly how many $0$s and $1$s we need in our word: we want exactly $\frac n 2$ of each.

If we have $n$ spaces to fill, we first think about how to place our $0$s. We need to choose $\frac n 2$ of these spaces to fill. After we choose these spaces, we know the rest of the word must be filled with the $1$s. This gives us $C\left(n,\frac n 2\right) = \frac{n!}{\frac n 2! \left(n - \frac n 2\right)!} = \frac{n!}{\left(\frac n 2 !\right)^2}$ balanced words.

We can apply the same idea if we happen to be working in a larger alphabet. Suppose that we're working in a ternary alphabet $\{0,1,2\}$. Then a balanced word over this alphabet is one that has the same number of 0s, 1s, and 2s. Again, we would make sure that $3 \mid n$ but then our problem is solved in the following way:

First, we choose $\frac n 3$ spots for our 0s. However, we're left with $\frac 2 3 n$ spots for the 1s and 2s. We then choose half of these spots for the 1s and everything left over goes to the 2s. This gives us a total of $$C\left(n, \frac n 3\right) \cdot C\left(\frac{2n}3, \frac n 3\right) = \frac{n!}{\frac n 3! \cdot \left(n - \frac n 3\right)!} \cdot \frac{\frac{2n}3!}{\frac n 3! \cdot \left(\frac{2n}3 - \frac n 3\right)!} = \frac{n!}{\frac n 3! \cdot \frac{2n}3!} \cdot \frac{\frac{2n}3!}{\frac n 3! \cdot \frac n 3!} = \frac{n!}{\left(\frac n 3!\right)^3}.$$

Recall that combinations are really about counting subsets, while this suggests that there's a correspondence between how to arrange or select spots in a binary string.

One common question that comes up is when to count permutations and when to count combinations. It is very easy to turn a problem of one kind into a problem of the other, just like in our parking example. The key to look for is whether what you're counting has an element of ordering or arrangement or distinguishability.

Generalizing Permutations and Combinations

Right now, we're restricting our view of counting to choosing elements from a set. And because we're working with a set, we assume that we have one of each "thing". But 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—that is, multiples of the same thing. We can make use of the ideas we saw with combinations and permutations and how to consider counting equivalent objects.

Suppose you've been tasked with gathering six donuts/muffins/scones/other pastry and there is a choice of four types, say chocolate, plain, strawberry, and green. How many different combinations can you make, with repetition? For an ordinary combination, we would only choose one of each type, 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 chocolate, one plain, two green), assuming this is the order in which we chose our goods. 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 that the box we have has a compartment for each type,regardless of the number that we end up choosing, so we have something like $CCC|P||GG$. Finally, we note that since each compartment contains a specific type, we don't need to specifically denote the type, and we can represent our choice by $***|*||**$.

Let's consider another possible choice: $*||*|****$, which is one chocolate, one strawberry, and four green. 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 binary alphabet $\{*,|\}$ (so in fact, we could have done this with the alphabet $\{0,1\}$). 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.

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$}$

How many solutions to $x+y+z = 13$ are there, where $x,y,z$ are non-negative integers? 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.

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.

The number of different permutatiosn 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!}.$$