Derive Pascal's formula from the fact that C (n, r) is the number of ways of selecting r objects from a set of n objects. Let x denote the nth object of the set. Count the number of ways that a subset of r objects containing x can be selected, and then count the number of ways that a subset of r objects not containing x can be selected.
In the following triangular table, known as Pascal's triangle, the entries in the nth row are the binomial coefficients

Observe that each number (other than the ones) is the sum of the two numbers directly above it. For example, in the 5th row, the number 5 is the sum of the numbers 1 and 4 from the 4th row, and the number 10 is the sum of the numbers 4 and 6 from the 4th row. This fact is known as Pascal's formula. Namely, the formula says that

Transcribed Image Text:

|6). (). (). . (C). . Oth row 1st row 1 2 1 13 3 1 2nd row 3rd row 1 4 6 4 1 4th row 15 10 10 5 1 5th row 16 15 20 15 6 1 6th row 1 7 21 35 35 21 7 1 7th row