When we discussed the number of $r$-permutations, we subtly introduced another counting rule: the division rule. Here's what we did: we said that the total number of permutations on $n$ objects is $n!$, which is the same as counting permutations on $r$ objects, which is $P(n,r)$, and then counting permutations on the rest of the $n-r$ objects, which is $(n-r)!$. Then we conclude algebraically that $P(n,r) = \frac{n!}{(n-r)!}$.
Implicitly, what this says is that the number of $r$-permutations can be found by counting all $n$-permutations and tossing out the last $n-r$ elements—since they don't matter, we can treat all of them as equivalent. This is essentially what the division rule says.
Since the division rule is really about process (i.e. the number of equivalent ways to do something), we'll frame the rule in terms of a function. Specifically, we are concerned with $k$-to-1 functions.
A $k$-to-1 function $f : A \to B$ is a function that maps exactly $k$ elements of $A$ to each element of $B$.
If $f : A \to B$ is a $k$-to-1 function, then $|A| = k \cdot |B|$.
As a result, we can conclude that $|B| = \frac{|A|}k$.
In our discussion of the number of $r$-permutations, we can consider the function that maps permutations of $n$ things to the permutations of $r$ things. One such function is the one that simply takes the first $r$ elements of each permutation. For example, suppose our salesman from earlier is considering a list of itineraries containing permutations like \[(\mathrm{ORD}, \mathrm{YYZ}, \mathrm{HND}, \mathrm{YVR}, \mathrm{YUL}, \mathrm{MSP})\] but they realize they only have time for a trip to three cities. Then they would consider a a mapping from 6-permutations to 3-permutations by simply taking the "front" of the permutation: \begin{align*} (\mathrm{ORD}, \mathrm{YYZ}, \mathrm{HND}, \mathrm{CTS}, \mathrm{YVR}, \mathrm{YUL}) &\mapsto (\mathrm{ORD}, \mathrm{YYZ}, \mathrm{HND}) \\ (\mathrm{ORD}, \mathrm{YYZ}, \mathrm{HND}, \mathrm{YVR}, \mathrm{CTS}, \mathrm{YUL}) &\mapsto (\mathrm{ORD}, \mathrm{YYZ}, \mathrm{HND}) \\ (\mathrm{CTS}, \mathrm{HND}, \mathrm{YYZ}, \mathrm{YVR}, \mathrm{ORD}, \mathrm{YUL}) &\mapsto (\mathrm{CTS}, \mathrm{HND}, \mathrm{YYZ}) \\ \end{align*}
More abstractly, we would have something like \[(3,1,5,2,4,6) \mapsto (3,1,5)\] We see then that for each 3-permutation, there are $6 = 3!$ possible 6-permutations that map to it: \[(3,1,5) \leftarrow \begin{cases} (3,1,5,2,4,6) \\ (3,1,5,2,6,4) \\ (3,1,5,4,2,6) \\ (3,1,5,4,6,2) \\ (3,1,5,6,2,4) \\ (3,1,5,6,4,2) \end{cases} \] So when framed via the Division Rule, we have $|A| = n!$, $|B| = P(n,r)$, and $k = (n-r)!$. That is, for each $r$-permutation of $n$ things, we can associate it with $(n-r)!$ different $n$-permutations.
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 $\binom n r$. This is read "$n$ choose $r$".
These $\binom n r$ are called binomial coefficients for reasons that we'll see very soon. Sometimes you'll see this denoted as $C(n,r)$, but that notation really only exists in a first discrete math or combinatorics class—everyone ends up dropping it sooner or later in favour of the binomial coefficients.
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 $$\binom n r = \frac{n!}{r!(n-r)!}.$$
We can make use of the number of $r$-permutations of a set. We know that the number of $r$-permutations of a set of size $n$ is simply the number of a subset of size $r$. So we can do the following: first, choose a subset of size $r$, and then compute the number of permutations of this subset. This gives us $$P(n,r) = \binom n r \cdot P(r,r).$$ Then doing some algebra, we get $$\binom n r = \frac{P(n,r)}{P(r,r)} = \frac{n!}{r!(n-r)!}.$$
Notice that this is another application of the division rule, by expressing the number of $r$-combinations in terms of the number of $r$-permutations. Since permutations are ordered and combinations are not, we need to consider all permutations with the same elements as equivalent. How many of there are these? There are exactly $r!$ of each, so we divide by $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 $$\binom 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$, $\binom n r = \binom n {n-r}$.
We have $$\binom n {n-r} = \frac{n!}{(n-r)! (n - (n-r))!} = \frac{n!}{(n-r)! \cdot r!} = \binom 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 $\binom n {\frac n 2} = \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 $$\binom n {\frac n 3} \cdot \binom {\frac{2n}3} {\frac n 3} = \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. This makes sense—after all, we proved that the subsets of an $n$-element set are in correspondence with binary strings of length $n$.
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.
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 $000101100$.
Let's consider another possible choice: $011010000$, 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 $\{0,1\}$ Since we have six objects and four classes, we can view our possible selections as a string of length 9 with 6 $0$s and 3 $1$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 was originally called "stars and bars", using the binary alphabet $\{*,|\}$ to denote the objects and categories. It 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.
We can view each possible selection as a string of length $r+n-1$ over the alphabet $\{0,1\}$. We know that each string contains exactly $r$ $0$s and $n-1$ $1$s. Then there are $\binom{r+n-1}{r}$ possible ways to choose spots for the $r$ $0$s. Since all remaining spots must be occupied by $1$s, this is the same as choosing spots for $n-1$ $1$s, and there are $\binom{r+n-1}{n-1}$ ways to do so.
Just like with generalizing combinations, we can also think about how to generalize permutations.
How many distinguishable permutations of the word $ACGACGAAAG$ 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 five $A$s, two $C$s, and three $G$s. So we can choose five of ten positions for the $A$s and there are $\binom {10} 5$ ways to do so. This leaves five spots. We choose two for the $C$s and there are $\binom 5 2$ ways to do so, leaving three spots for the three $G$s with $\binom 3 3$ ways to place them. In total, we have $$\binom {10} 5 \binom 5 2 \binom 3 3 = \frac{10!}{5!5!} \cdot \frac{5!}{2!3!} \cdot \frac{3!}{3!0!} = \frac{10!}{5!2!3!} = 2520.$$
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 A_4 A_5 G_3$. It is clear that there are $10!$ 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 $5!$ permutations of $A_1 A_2 A_3 A_4 A_5$ and we know these are equivalent once we make these indistinguishable. By removing all the indistinguishable permutations for each symbol, we get $$\frac{10!}{5!2!3!}$$ as before.
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!}.$$
Looking back, we notice that these seeming generalizations of the combination and permutation problems are really specific problems that can be solved using exactly the same tools. The "generalized combination" that we saw with the donuts was transformed into a binary string problem and the "generalized permutation" was just a multi-step combination problem.
The theme of this lecture is thinking about how to construct the objects we're tasked with counting. If we think through the construction of these more complicated structures, we can often find a way to relate them back to other structures we've already seen before and know how to count.