Combinatorics is a subject that’s generally neglected in high school mathematics. It’s also a subject that takes a while for undergraduate math majors to get initiated into. In an introduction to probability course or “hodgepodge” topic in a pre-calculus course, students get an exposure to the idea of combinations and permutations. Sometimes in an Algebra course, when the binomial theorem is taught, students get to see “\(n\) choose \(k\)” as \({n \choose k}\). But, more often than not, the binomial theorem is taught hand-in-hand with Pascal’s Triangle. While Pascal’s Triangle is a nice way to introduce finding binomial coefficients, there often isn’t enough time in a course to dig much further into it except for how it is constructed.

For reference, and pulling from Wikipedia here’s the first few layers of Pascal’s Triangle.

Using this triangle, students are often shown that $$(a + b)^{3} = 1\cdot a^{3} + 3\cdot a^{2}b + 3\cdot ab^{2} + 1\cdot b^{3}$$ by reading the coefficients \([1,3,3,1]\) from Pascal’s Triangle and recognizing the pattern in the exponents (that they must sum to \(n\), where in this case \(n = 3\) from \((a + b)^{3}\)).

Forgotten with this introduction is a little bit of play with the triangle and a lead into combinatorics and combinatorial identities. The more notationally dense version of the binomial expansion is $$(a + b)^{n} = \sum_{k = 0}^{n}{n \choose k}a^{n-k}b^{k}$$

Now, depending on where students are in terms of technical ability, we can go down a few routes. Let’s start with the initial example, using $$(a + b)^{3} = 1\cdot a^{3} + 3\cdot a^{2}b + 3\cdot ab^{2} + 1\cdot b^{3}$$

Try this: let \(a = 1, b = 1\). Then, on the left-hand side, we have \((1 + 1)^{3} = 2^{3}\). And on the right-hand side? \(1 + 3 + 3 + 1\). Of course, both sides equal \(8\). But, here’s the fun thing, the right-hand side is the sum of the binomial coefficients: $${3 \choose 0} + {3 \choose 1} + {3 \choose 2} + {3 \choose 3}$$ And in this way, we have found a cheap way to generate combinatorial identities. Namely, our first one is
$$2^{n} = \sum_{k = 0}^{n} {n \choose k} = {n \choose 0} + {n \choose 1} + \cdots + {n \choose n-1} + {n \choose n}$$

A nice thing about this is that we haven’t wasted precious curriculum time. All we’re doing is showing examples of how the binomial expansion works — something we would have done regardless. We may have been inclined to first show an example such as expanding $$(1 + x)^{n}$$ But I’ve often found that this is initially too confusing for many students. Hence, I prefer to go with only numbers before generalizing.

A natural question that students will ask is “Why do I have to use the binomial expansion to compute \(2^{3}\) when I already know that’s \(8\)?”. With this question we get a natural response and gateway introduction to Combinatorics.

It’s not so much that we need the binomial expansion to compute powers of two, it’s more that the sum of binomial coefficients is a power of two. Here we have an opportunity to talk about how to interpret the coefficients \([1,3,3,1]\).

More likely than not, at some point, there was a “manual” expansion of \((a+b)^{3}\) as part of the exercise in introducing the binomial expansion. Now is a good time to review all EIGHT steps. Those eight steps? They are all the multiplications that are encountered before condensing the like terms. Namely, we have

• \(aaa\)
• \(aab\)
• \(aba\)
• \(abb\)
• \(baa\)
• \(bab\)
• \(bba\)
• \(bbb\)

And from the above list, we have a few places to go. We can talk about counting in binary (notice the progression I chose for the list) or we can talk about the idea of “how many ways can I choose “\(n-k\)” \(a\)s and \(k\) \(b\)s?”. The latter question lets us understand one interpretation of the coefficients, \(1,3,3,1\), in that there is one way to choose all three \(a\)s, three ways to choose two \(a\)s and one \(b\), etc. And more to the point, if we considered all ways of choosing two objects with replacement, three times, without a care for order, then there are exactly \(2^{3}\) ways of doing this. This type of reasoning and interpretation helps to keep the mechanics solid and reduces the reliance on an associative memorization of Pascal’s Triangle.

Next, extensions of the binomial theorem are at least conceptually and mechanical more with reach. With Pascal’s Triangle we are stuck in the mud a little bit when having to contend with $$(a + b + c)^{3}$$ Consider the following questions:

• If the coefficients of \((a + b)^{3}\) sum to eight, what should the coefficients of \((a + b + c)^{3}\) sum to?
• If we know that the coefficient of \(a^{2}b\) is \(3\) in the expansion of \((a+b)^{3}\) since there are \({3 \choose 2}\) ways of obtaining this product, what then is the coefficient of \(a^{2}b\) in the expansion of \((a + b + c)^{3}\)? Can we reason that the result should be \({3 \choose 2}{1 \choose 1} = 3\)?
• What about the coefficient of \(abc\) in \((a + b + c)^{3}\)? Can we reason that this should be \({3 \choose 1}{2 \choose 1}{1 \choose 1}\)?

From here, the motivation, conversationally, for the multinomial expansion (and its notation) is natural and straightforward and we can begin to see that
$${n \choose k_{1}}{n – k_{1} \choose k_{2}}\cdots {n – k_{1}-k_{2}-\cdots-k_{r-1} \choose k_{r}} = \frac{n!}{k_{1}!k_{2}!\cdots k_{r}!}$$

And we can introduce the general notation for the right-hand side as $${n \choose k_{1}, k_{2}, \ldots, k_{r}}$$

We can then see that the idea of a “combination” is, in some sense, an unnecessary simplification of “multinomial choosing”.

Anyway, back to the original point of fiddling with \((1 + 1)^{n}\); we were able to develop the identity $$2^{n} = \sum_{k=0}^{n}{n \choose k}$$ as a matter of consequence of binomial expansion. If students can get the hang of this, then we can look at something like \(0^{n} = (1-1)^{n}\) which expands to $$\sum_{k=0}^{n}(-1)^{k}{n \choose k}$$

More fun with this is that \(2^{n} = 2^{n} + 0^{n} = (1+1)^{n} + (1-1)^{n}\) and we can see that if we retain the “even” terms and double them, we have yet another combinatorial identity for \(2^{n}\), or equivalently $$2^{n-1} = \sum_{k=0, k \mbox{ even}}^{n}{n \choose k}$$ and the same for \(k\) odd. In fact, we can point back to our Pascal Triangle and see by inspection that this is true: \((1 + 3)\cdot 2 = 2^{3}\) or the next row \((1 + 6 + 1)\cdot 2 = 16\) and so forth.

Finally, if we really want to push this further, we can, with a little additional motivation, talk about rolling dice or flipping coins, for example — both staple “events” in probability. We often ask a question like “What is the probability that the sum of two, standard, six-sided dice will equal 7?”. Most of my Algebra students already have seen the “trick”. They make a matrix of sums and count the number of sevens and divide by 36. The result is that the probability is \(\frac{1}{6}\). Ok. But what about three, standard, six-sided dice? A little excursion into generating functions can show that this is not as daunting is it sounds. We need to read off the coefficient of \(x^{7}\) in $$(x^{1} + x^{2} + x^{3} + x^{4} + x^{5} + x^{6})^{3}$$

To get the probability take the coefficient of \(x^{7}\) and divide by \(6^{3}\). Voila! Easier said than done, many teachers may think and I admit that the step to “Voila!” has some details, but this is a productive struggle for students. They can start with the same problem, but replace three dice with their familiar two, since they already know what the answer should be. Or if the writing is too cumbersome, take two, three sided dice for example and ask to compute the distribution of their sum. And this is a matter of finding the appropriate coefficient for \((x^{1} + x^{2} + x^{3})^{2}\).

In any case, this stuff is sometimes lost in the Algebra shuffle, but I think that there is time to cover material like this without sacrificing the curriculum. More forcefully, I think it is better to go down this line of exploration rather than endlessly futz with memorizing the expansion formula or writing layers and layers of Pascal’s Triangle. I want my students to be able to see that finding the coefficient of, say, \(a^4b^2c\) in \((a + b + c)^{7}\) is no more complicated [maybe more tedious] than finding coefficients of a binomial.