| Contents |
Supplements and Links
|
| Objectives: To understand the main combinatorial properties of Pascal's triangle and generalize this understanding to the d-dimensional case. | Necessary Background: Only basic facts about probability and knowledge of how to expand powers of polynomials are necessary. Section II considers arrays of numbers which reside in higher dimensional space, so it may be helpful to be familiar with simplices as geometric objects. |
| Summary: Students are introduced to Pascal's triangle and to its applications in probability and binomial expansion. In Section II, the analogous properties of d-dimensional Pascal simplices are investigated, and students arrive at an explicit formula for the entries. | |
Early on in our mathematics education we are taught the formula for expanding the square of a sum of two terms:
A similar formula applies to the cube of a sum:
These binomial expansions can be completely specified by their coefficients, since the determination of the exponents is straightforward: In the expansion of (a + b)n, the exponents of a begin at n and decrease to 0, and the exponents of b begin at 0 and increase to n. Therefore we can think of the square expansion simply as the coefficients "1 2 1" and the cube expansion as "1 3 3 1".
It turns out that binomial coefficients display some very interesting relationships. These relationships can be seen effectively by arranging the coefficients into a triangular array, where the nth row consists of the coefficients of the expansion of (a + b)n. The first eleven rows of this array are shown below. (Click the table for a larger version.)
This triangle is called Pascal's triangle. The top row (which corresponds to n = 0) signifies that (a + b)0 = 1 for all a and b, and the next row says that (a + b)1 = 1a + 1b.
The first property to notice about Pascal's triangle is that we can compute its entries without actually working out binomial expansions, for each number in Pascal's triangle is the sum of the two numbers that lie above it to the left and right. For example, the 2 is the sum of the two 1s above it to the left and to the right, and each 10 in the "1 5 10 10 5 1" row is the sum of the 4 and 6 above it. (The space surrounding the triangle is considered to be filled with zeros, so each of the 1s (after the first) comes from the 0 + 1 above it.) Find the coefficients in the expansions of (a + b)11 and (a + b)12.
Not only does Pascal's triangle appear in binomial expansions, but it also appears in probability. Consider the following question: If we have n objects, in how many different ways can we select just m of them? For example, if we have 4 marbles, we can pick 1 of them in four different ways. If we want to choose 2 marbles of the 4, there are six different ways to do it. How many ways are there to choose 1 marble from a set of 5? How many ways are there to choose 2 marbles from a set of 5? 3 from 5? 4 from 5? 5 from 5? 0 from 5?
Let 
denote the mth entry of the nth row of Pascal's triangle (where the top row is row 0 and the leftmost "1" of each row is entry 0). It turns out that the number of ways of choosing m objects from n is exactly . The reason for this is not too difficult to see: The number of times that the term an – mbm appears in the expansion of (a + b)n = (a + b) (a + b) ··· (a + b) is exactly the number of ways to "choose" m powers of b from the n available factors (a + b).
We will next obtain an explicit formula for the binomial coefficient . To do this we will need the factorial function, which multiplies a natural number n by all natural numbers less than n. It is denoted by n! (read "n factorial"). Thus
(By definition, 0! = 1.) For example, 4! = 4 · 3 · 2 · 1 = 24 and 2! = 2 · 1 = 2. Compute n! for n = 3, 5, 6, 7, 8, 9, 10.
To derive the explicit formula for in terms of the factorial function, we work through the possibilities of choosing m objects from n objects. First let us choose the objects one at a time. For the first, we have n objects from which to choose. Once we have selected one, we have n – 1 objects from which to choose a second. After that, we have n – 2 objects from which to choose a third, etc. The total number of ways to choose m objects in order is therefore
However, we are interested in the number of ways to choose m objects from n objects without respect to order. Therefore we divide this number by m!, the number of different orders in which we can select the same m objects. So we have the identity
 | (1) |
for any nonnegative integers n and m with m ≤ n. Thus, for example, 
For m > n, is defined to be 0.
Prove the Pascal relation, that for 0 ≤ m ≤ n,
 | (2) |
What is the sum of the numbers in the nth row of Pascal's triangle? Write this statement as an algebraic identity, and prove it.
We now turn to the generalizations of Pascal's triangle and to discover what forms they take. Our motivation will be in trying to understand trinomial expansions (a + b + c)n. What are the trinomial coefficients for n = 1, 2, and 3?
Verify that the geometric relationship is correct by comparing the predicted trinomial coefficients with the actual coefficients for the case n = 4.
What is the sum of the nth trinomial coefficients? Prove it.
Generally, we desire to find the multinomial coefficients of the expansion 
. Find an additive relation for d-nomial coefficients. It may be helpful to invent some new notation to represent d-nomial coefficients.
What is the sum of the nth d-nomial coefficients?
Relevant links: