Discrete Mathematics for Computer Science

464 CHAPTER 7 Counting and Combinatorics

Row 0 1

C(O, 0)

Row 1 1 1

C(1, 0) C(1, 1)

Row 2 1 2 1

C(2, 0) C(2, 1) C(2, 2)

Row 3 1 3 3 1

C(3, 0) C(3, 1) C(3, 2) C(3, 3)

Row 4 1 4 6 4 1

C(4, 0) C(4, 1) C(4, 2) C(4, 3) C(4, 4)

Column 0

D n 1 l Column

C(D, 1 0)

C(1, 0) C(1, 1) •un

Q21,0) Q2,1) Q(2, 2) Comn

C(1, 0) C(3, 1) C(3, 2) Q(1, 3)

cQA, 0) C(44, 1) C(6, 2) Q(4, 3)

Diagonal^0 1

Diagonal^3 1

Diagonal 2 1" ' 2 1

7(2, O) C(2 ,1) Q"..C2, 2)

Diagonal 3 1" -. 3". 3"-. l•x.

Diagonal 4 Q(4, 14 0) Q4, 1)• (42) 6 Q4, 4 3) Q4, 1 4)•

Figure 7.11 Rows, columns, and diagonals in Pascal's triangle.

Proof. The Row Sum is the content of Theorem 6 in Section 7.9.1. The proofs of the

other identities are left as exercises for the reader. M

By recognizing how to represent powers of integer variables as linear combinations of

binomial coefficients, the row, column, and diagonal sum identities can be used to evaluate

finite sums of such powers.

Theorem 9. (Sums of Powers) Let n > 1. Then,

(a) l+2+3+...+n=n(n+1)/2