Here’s a useful identity.
For all $n \gt 0$ and $0 \leq r \leq n$, $\binom n r = \binom n {n-r}$.
As usual, this is not too hard to see algebraically: $$\binom n {n-r} = \frac{n!}{(n-r)! (n - (n-r))!} = \frac{n!}{(n-r)! r!} = \binom n r.$$
But what does it mean? Let’s consider a combinatorial proof instead.
Suppose we have a set of $n$ elements. We want to choose $r$ of these elements to form a subset. The number of ways to do this is $\binom n r$.
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. The number of ways to do this is $\binom n{n-r}$.
Therefore, $\binom n r = \binom n{n-r}$.
Let’s think about binomials. Recall that a binomial is an expression of two terms. Hopefully, we are all familiar with how to expand a binomial. For instance, we have $$(x+y)^2 = x^2 + xy + xy + y^2 = x^2 + 2xy + y^2.$$ Of course, we can do the same thing with higher degrees, like \begin{align*} (x+y)^3 &= (x+y)^2 (x+y) \\ &= (x^2 + 2xy + y^2)(x+y) \\ &= x^3 + 2x^2y + xy^2 + x^2y + 2xy^2 + y^3 \\ &= x^3 + 3x^2y + 3xy^2 + y^3 \end{align*}
Now, this process is straightforward but a bit tedious. Perhaps there is an alternative way to think about the resulting coefficients. This becomes a bit more clear if we step away from our algebraic impulses a bit. We can write \begin{align*} (x+y)^4 &= (x+y)(x+y)(x+y)(x+y) \\ &= xxxx + xxxy + xxyx + xxyy + xyxx + xyxy + xyyx + xyyy + \\ &\quad\: yxxx + yxxy + yxyx + yxyy + yyxx + yyxy + yyyx + yyyy \end{align*} When written in this way, each term looks much more like the kinds of objects that we’ve been working with over the past week. That is, we can think of each term as a combination of the terms from each binomial. In other words, how many terms of the form $x^3y$ are there? Exactly as there are many ways to choose three $x$’s and one $y$ from each binomial.
We can generalize this result as the following.
For all $n \in \mathbb N$, $$(x+y)^n = \sum^n_{j=0} \binom n j x^{n-j} y^j.$$
One can prove this via induction and it makes a nice exercise. Again, we will prove this via a combinatorial argument instead.
Each term of our polynomial is of the form $x^{n-j}y^j$. Then the coefficients are exactly the number of ways to choose $n-j$ $x$’s from each binomial. There are $\binom n {n-j}$ ways to do this and $\binom n {n-j} = \binom n j$.
An interesting consequence of this theorem is how it gives us a connection between combinatorics and algebra. Being able to shift problems from one area of math to another is a powerful move because it allows us to use tools in different area of mathematics. In a class with more time to spend on combinatorics, we would have seen that this idea leads to generating functions, which are encodings of sequences as power series.
Suppose you have to prove the inductive case in some proof and you’re faced with expanding $(k+1)^5$. Luckily, you don’t need to futz around with expanding this polynomial and can directly apply the binomial theorem: \begin{align*} (k+1)^5 &= \binom 5 0 k^5 1^0 + \binom 5 1 k^4 1^1 + \binom 5 2 k^3 1^2 + \binom 5 3 k^2 1^3 + \binom 5 4 k 1^4 + \binom 5 5 k^0 1^5 \\ &= k^5 + 5k^4 + 10k^3 + 10k^2 + 5^k + 1 \end{align*}
Suppose we set $y = 1$. Then we have that $$(x+1)^n = \sum_{i=0}^n \binom n i x^i.$$
Here is a neat consequence of the binomial theorem that should match with our intution about what the binomial coefficients mean. Setting $x = y = 1$ gives us $$2^n = (1+1)^n = \sum_{i=0}^n \binom n i 1^{n-i} 1^i = \sum_{i=0}^n \binom n i.$$ Of course, this makes total sense when interpreted combinatorially: if $\binom n i$ is the number of subsets of $n$ elements of size $i$, then adding the number of these subsets together is the total number of subsets of a set of size $n$, which is $2^n$.
For all natural numbers $n \geq k \gt 0$, $$\binom{n+1}{k} = \binom{n}{k-1} + \binom n k.$$
Let $A$ be a set of $n+1$ elements. We want to count the number of subsets of $A$ of size $k$, which is $\binom{n+1}{k}$, by definition.
Choose an arbitrary element $x \in A$ and a subset $B \subseteq A$ of size $k$. Then either $x \in B$ or $x \not \in B$; these two cases are disjoint. If $x \in B$, then $B$ contains $k-1$ elements in $A \setminus \{x\}$ and there are $\binom{n}{k-1}$ such sets. On the other hand, if $x \not \in B$, then $B$ contains $k$ elements in $A \setminus \{x\}$ and there are $\binom{n}{k}$ such sets. Together, this gives us $\binom{n}{k-1} + \binom n k$ subsets of $A$ of size $k$.
This identity leads us to the famous Pascal’s Triangle: $$ \begin{matrix} &&&&&& \binom 0 0 &&&&&& \\ &&&&& \binom 1 0 && \binom 1 1 &&&&& \\ &&&& \binom 2 0 && \binom 2 1 && \binom 2 2 &&&& \\ &&& \binom 3 0 && \binom 3 1 && \binom 3 2 && \binom 3 3 &&& \\ && \binom 4 0 && \binom 4 1 && \binom 4 2 && \binom 4 3 && \binom 4 4 && \\ & \binom 5 0 && \binom 5 1 && \binom 5 2 && \binom 5 3 && \binom 5 4 && \binom 5 5 & \\ \binom 6 0 && \binom 6 1 && \binom 6 2 && \binom 6 3 && \binom 6 4 && \binom 6 5 && \binom 6 6 \end{matrix} $$ Filling in the values for the coefficients, the triangle looks like this: $$ \begin{matrix} &&&&&& 1 &&&&&& \\ &&&&& 1 && 1 &&&&& \\ &&&& 1 && 2 && 1 &&&& \\ &&& 1 && 3 && 3 && 1 &&& \\ && 1 && 4 && 6 && 4 && 1 && \\ & 1 && 5 && 10 && 10 && 5 && 1 & \\ 1 && 6 && 15 && 20 && 15 && 6 && 1 \end{matrix} $$ When viewed like this, one can see how Pascal’s identity is used to construct the following row.
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.
If we generalize our argument from the example, we essentially have a proof for the following statement.
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.
What are the coefficients of the expansion of $(x+y+z)^6$? Of course, this is an extension of our discussion of binomials. If we try the same strategy, we see that we have \[(x+y+z)^6 = (x+y+z)(x+y+z)(x+y+z)(x+y+z)(x+y+z)(x+y+z).\] Then by the same argument we employed for binomials, we see that this is the number of ways to choose one of $x$, $y$, and $z$ from each trinomial. Suppose we consider the number of terms $x^1y^3z^2$. We want the number of ways to have gotten 1 $x$, 3 $y$’s, and 2 $z$’s. We know that this is $\binom 6 1 \binom 5 3 \binom 2 2 = \frac{6!}{1!3!2!}$.
We can generalize this idea to trinomials and other larger nomials. These are called multinomial coefficients and are denoted $\binom{n}{n_1,n_2, \dots, n_k}$. 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$.