|
Algebra students are often presented with three different ideas:
Often both Pascal's Triangle and binomial expansions are described using combinations but without any justification that ties it all together. The passionately curious surely wonder about that connection! Here's my attempt to tie it all together. As always, read mathematics with a pencil and work through it!
Before learning about combinations we usually learn about permutations, where nPr is the number of permutations of n things taken r at a time. Since we have n choices for the first thing, n - 1 choices for the second, and so on down to n - r + 1 choices for the rth thing,
This is a fine formula, but those three dots are annoying. We often prefer a “closed-form” formula without the ellipsis. To do that, we do the same thing we do when we reduce fractions: multiply by a strange form of the number 1:
| nPr | = | n (n - 1) …(n - r + 1) | ||
| = | n (n - 1) …(n -
r + 1)⋅
|
|||
| = |
|
|||
| = |
|
The easiest way to think about combinations, which are like permutations but in which order doesn't matter, is to note that all permutations of the same r things represent the same combination, and there are r! of those permutations. Therefore
| nCr | = |
|
||
| = |
|
Pascal's Triangle is usually shown like this
| 1 | ||||
| 1 | 1 | |||
| 1 | 2 | 1 | ||
| 1 | 3 | 3 | 1 | |
| … |
where each entry is the sum of the one above and the one above and to the left. I've highlighted one example of this rule; in this case 3 = 1 + 2. (Imagine the triangle is surrounded by zeros so every entry can follow this rule.) Sometimes the triangle is also shown like this:
| 0C0 | |||
| 1C0 | 1C1 | ||
| 2C0 | 2C1 | 2C2 | |
| 3C0 | 3C1 | 3C2 | 3C3 |
| … |
That's pretty cool; it's always cool when different parts of math point at each other, but it still leaves us to wonder, why ? Why does, for example, 3C1 =
| 2C0 + 2C1 |
There are a number of ways to look at this. One way is informally, based on what we know nCr to mean: the number of combinations of r things that can be taken from n things. Another way is algebraically.
Let's look at the informal way first. Based on the informal meaning of nCr, why is it that
In mathematics, we can often get surprisingly far by just thinking about what the equations mean. Looking at the left side of the equation, n + 1Cr is how many combinations of r things can be taken from a collection of n + 1 things. To make this more vivid, imagine a bag of n + 1 cats, and you are (for some reason) wondering how many combinations of r cats can be taken from the bag.
If you look at the right side of the equation, we see two combinations taken from n things. That encourages us to imagine that one cat in our bag is named Wilma, leaving n more cats in the bag. Those n cats better fits the right side of the equation. Well, any combination of r cats from our bag of n + 1 cats must either include Wilma or not. How many combinations include Wilma? Besides Wilma, those combinations have r - 1 more cats, so there are nCr - 1 combinations that include Wilma. How many combinations are there that don't include Wilma? In that case, all r cats must come from the n remaining cats in the bag, so there are nCr combinations. Adding the combinations with Wilma and the combinations without Wilma (right side of the equation) gives us our total (left side).
Now let's look at Pascal's Triangle algebraically. In that case we again want to see why
This time we'll try algebra. To figure this out, I used a trick I often use when trying to prove one thing equals another: I worked in both directions and met in the middle. In other words, I started from nCr - 1 + nCr in one direction and n + 1Cr in the other and kept moving toward each other until I could see the connection. This is like laying a railroad from point A to point B by going (say) east from A and west from B until the tracks meet. You can read this the same way if you like, starting from nCr - 1 + nCr and going down and also starting from n + 1Cr and going up. I've highlighted in red the things changed from the previous line to make it easier to follow.
Basically the argument depends on splitting up factorials into pieces over and over again. For example, r! = r (r - 1)!. (Mak sure you understand that before reading on.) Besides that, all we do is add fractions by finding a common denominator and a few simplifications.
| nCr - 1 + nCr | = |
|
||||
| = |
|
|||||
| = |
|
|||||
| = |
|
|||||
| = |
|
|||||
| = |
|
|||||
| = |
|
|||||
| = |
|
|||||
| = | n + 1Cr |
It works, but it's maybe not as clear as the informal approach.
Somewhere in our algebra studies, we learn that coefficients in a binomial expansion are rows from Pascal's triangle, or, equivalently,
But why is that? Why are the coefficients related to combinations? One simple way to view it is to imagine (x + y)n written out as (x + y) (x + y) …. (x + y) (n times). If you use the distributive law to multiply this out, you get the sum of all possible ways to pick either x or y from each factor and multiply. For example,
| (x + y)3 | = | (x + y) (x + y) (x + y) |
| = | x x x + x x y + x y x + x y y + y x x + y x y + y y x + y y y |
At this point we would normally add the like terms, but how many like terms are there of each kind? For example, how many x2 y terms are there? You can pick the y from any of our three (x + y) binomials and x's from the rest. For example, if we choose the y from the third binomial we get x x y; if we choose the second we get x y x, and if we choose the first we get y x x. Since there are three (x + y) factors and we are choosing one y, here are 3C1 different combinations. In general, when multiplying (x + y)n, there are nCr combinations of exactly r factors from which to take the y's (and the rest are x's), which means there are nCr terms equaling xn - r yr. So adding those terms together gives nCr xn - r yr.
We can also show this binomial expansion rule using mathematical induction. Mathematical induction is a method of proof where we prove something for a very simple case first (the basis step), and then prove that if it's true for some case then it's true for the next case (the induction step). If you can cover all the cases that way, then you have proven it for all cases.
So let's prove the basis step, in this case that
It's easy to see that both sides of the equation equal 1, so that's done.
Now, for the induction step, let's assume that
We'll try to prove that it's true for the next step, i.e. that
This is just a gazillion uses of the distributive law. First we multiply (x + y)n by one more (x + y), distributing the new x and y over the giant sum. Then we combine like terms, which is really another use of the distributive law. (Why?) I've color-coded a few of the like terms to highlight that combining those like terms matches Pascal's triangle!
| (x + y)n + 1 | = | (x + y)(x + y)n |
| = | (x + y) ( nC0 xn y0 + nC1 xn - 1 y1 + … + nCn x0 yn) | |
| = | x( nC0 xn y0 + nC1 xn - 1 y1 + … + nCn x0 yn) + y( nC0 xn y0 + nC1 xn - 1 y1 + … + nCn x0 yn) | |
| = | ( nC0 xn + 1 y0 + nC1 xn y1 + … + nCn x1 yn) + ( nC0 xn y1 + nC1 xn - 1 y2 + … + nCn x0 yn + 1) | |
| = | nC0 xn + 1 y0 + ( nC1 + nC0)xn y1 + … + ( nCn + nCn - 1) x1 yn + nCnx0 yn + 1 | |
| = | n + 1C0 xn + 1 y0 + n + 1C1 xn y1 + … + n + 1Cn x1 yn + n + 1Cn + 1 x0 yn + 1 |
The last step uses the rule that makes Pascal's triangle:
The first and last terms work because nC0 = nCn = 1 for all n.
Induction may at first seem like magic, but look at it this way. The basis step was easy. Then we proved that if it's true for n, it's true for n + 1. Why did that prove it for all n? It's true for n = 1 because we proved that if it's true for 0 then it's true for 1 (and it's true for 0 by the basis step). It's true for n = 2 because we proved that if it's true for 1 then it's true for 2 (and it's true for 1 by the previous step). And so on.
This is one of those places where lots of math comes together. We have connected combinations with Pascal's Triangle and with binomial expansions, though at first blush these may not seem related.
By the way, the long sums above can be made much simpler with the use of sigma (∑) notation. I avoid it here because many high school students are not exposed to this notation until late or not at all.