Pascal's Triangle
463
as was proved in Theorem 1 of Section 7.8.1. These coefficients are called multinomial
coefficients.
Pascal's Triangle
Pascal's Identity (see Theorem 4 in Section 7.9) can be used to calculate the binomial
coefficients for any n and m such that 0 < m < n using the boundary conditions and the
binomial coefficients for n - 1. The terms pointed to by a pair of arrows in Figure 7.9 are
found by adding the two values at the head of the arrows.
... C(n - 1, O)
C(n - 1, 1)
C(n - 1, 2) ...
... C(n, 0)
C(n, 1)
C(n, 2)
C(n, 3)...
Figure 7.9 Finding terms in Pascal's Triangle.
There is a long history for the binomial coefficients and an extensive list of identities
they satisfy. The display of these numbers in triangular form in Figure 7.10 is called Pascal's triangle even though these numbers were displayed in that fashion centuries before
Pascal's time.
C(O, 0)
1
1
C(1, 0) C(1, 1)
1
2
1
c(2, 0) c(2, 1) c(2, 2)
1
3
3
1
C(3, 0) C(3, 1) C(3, 2) C(3, 3)
1
4
6
4
1
C(4, 0) C(4, 1) C(4, 2) C(4, 3) C(4, 4)
Figure 7.10 Five rows of Pascal's triangle.
The rows of Pascal's triangle represent the coefficients of the terms in (x + y)n. By
representing the numbers in Pascal's triangle in a slightly different form, as seen in Figure 7.11 on page 464, it is natural to define rows, columns, and diagonals for Pascal's
triangle.
The next theorem gives a formula for the sum of elements in a row, consecutive elements from the beginning of a column, or elements on a diagonal of Pascal's triangle.
Theorem 8. Let n > r > 0. Then,
Row Sum :C(n,0)+C(n, 1)+.-.+C(n,n)=2'.
Column Sum :C(r,r)+C(r+1,r)+...+C(n,r) =C(n+ 1,r+ 1).
Diagonal Sum :C(n,0)+C(n+ 1, 1)+..+C(n+r,r)
=C(n+r+l,r)