Discrete Mathematics for Computer Science

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 Pas-
cal'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 Fig-
ure 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 ele-
ments 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)