We now return to the subject of identities. We’re going to meet some important integers. They bear the name n choose k. Little terminology– let’s start with k equals 2. n choose 2 means the number of ways of choosing 2 objects from a group of n objects. The notation– parentheses with the n over the 2. And this is read, n choose 2. How many ways are there of choosing 2 objects from a group of n? Well, the first object can be chosen n ways, after which, the second can be chosen n minus 1 ways. This produces, in all, n times n minus 1 choices.
But actually, we don’t wish to distinguish pairs by the order in which they were chosen, so we’ve counted each pair twice. So n choose 2 is actually n times n minus 1, divided by 2. More generally, n choose k refers to the number of ways of choosing k elements from a set of n elements. We can prove by induction that n choose k is given by a certain formula. In the numerator, you find the product of the integers n, n minus 1, all the way down to n minus k plus 1. And in the denominator, you find the product of the first k integers.
It turns out to be convenient to write such formulas to introduce a certain notation called factorial notation. Here’s the definition– for a positive integer n, we define its factorial to be the product of 1 times 2, times 3, all the way up to n. Now, the notation for this factorial of n is n followed by an exclamation mark. I know that’s very dramatic for notation, but that’s the way it is. For example, the factorial of 6 is 6 times 5, times 4, times 3, times 2, times 1, which is, of course, 720. Convention– the factorial of 0, by definition, is 1. Given this factorial notation, we have the following compact formula for the number n choose k.
It’s n factorial divided by k factorial, times n minus k factorial. For example, 4 choose 2, if one works it out, turns out to be 6. Is that correct? Are there 6 ways to choose 2 objects from a group of 4 objects? Let’s test it. Here are 4 different objects. How can I choose 2 of them from this group? Well, I can make a list of all the possible choices of 2 objects. There’s the list. I count the number of elements in the list, and then I see that there are 6 possible choices. Well, that’s correct– 4 choose 2 equals 6.
The numbers n choose k are called binomial coefficients because they appear in the so-called binomial expansion for the n-th power of a binomial term, that is, a sum of the form a plus b. Here’s that general formula for the binomial expansion of order n in our sigma notation. It expresses the fact that a plus b to the power n is the sum of n plus 1 terms that you get by successively putting k equals 0, 1, 2– all the way up to n– in the terms that you see, and adding them up.
So for example, if you express this formula in the special case n equals 2, it turns out to say a plus b squared is a squared plus 2ab, plus b squared, which happens to be a notable identity that we already know. The next case– n equals 3 will give you a certain expression in which the coefficients are 1, 3, 3, and 1. You notice there’s a certain pattern there– there is a pattern in the preceding one– 1, 2, 1. And it turns out there is an interesting geometric way to generate this pattern, and it’s called Pascal’s Triangle. Pascal was a 17th century mathematician and philosopher. And here’s how his triangle works– you give yourself, initially, a hollow pyramid of 1s.
There it is. And you’re going to fill it in according to a certain rule. The first missing number at the top– how are you going to fill it in? Answer– you look at the 1 plus 1 above it, to the left and to the right, and add them up, and get a 2. Now, you generate the next line in a similar fashion. The 2 plus 1 will give you a 3. And the next line– the 3 plus 1 will give you a 4. And you continue this way infinitely, and you will get Pascal’s Triangle. Now, it turns out that the lines of this triangle correspond to the coefficients in our binomial expansions.
For example, if you look at a plus b squared, you see the coefficients 1, 2, 1, and they correspond to the first interesting line in the triangle. a plus b to the power 3– the coefficients 1, 3, 3, 1 correspond to the next line– and so forth. This type of mathematics, by the way, is the mathematics of counting, a subject called combinatorics. It’s a very beautiful subject, and it’s a great way to meet new integers.