Discrete Mathematics for Computer Science

458 CHAPTER 7 Counting and Combinatorics

(Algebraic)

n! k!

C(n, k) • C(k, m) =

k! (n - k)! m! (k - m)!

n! k!(n - m)!

k!(n - k)! m!(k - m)!(n - m)!

n! (n - m)!

m! (n-rm)! (k-m)!(n-m -(k-rm))!

=C(n, m) • C(n - m,k- k - )

Corollary 1:

n

C(n,k) =- C(n- 1,k- 1)

k

Proof. By Theorem 3, we have

C(n, k) • C(k, m) =C(n, m) C(n - m, k - m)

Substitute m = 1 in this identity to get

C(n, k) • C(k, 1) =C(n, 1) • C(n - 1,k- 1)

C(n,k) • k =n C(n - 1, k- 1)

n

C(n,k) =-•.C(n- l,k-1) U

k

To calculate a particular binomial coefficient, Corollary 1 leads to a good method.

When Pascal's Triangle is introduced, you will see a way to calculate all the binomial

coefficients for 1, 2, ..., n for any n e N.

The next identity is credited to Pascal (1623-1662, b. France). This result is used to

compute the entries in Pascal's triangle, which is a way of displaying binomial coefficients.

Theorem 4. (Pascal's Identity) Let n > k > 1. Then,

C(n,k) = C(n - 1,k) + C(n - 1,k- 1)

Proof (Combinatorial) The left-hand side counts the number of k-element subsets of

an n-element set. The right-hand side can be interpreted as follows. Let A be an n-element

set, and pick any x E A. Then, C(n - 1, k) k-element subsets of A do not contain x; the

k elements must be chosen from the remaining n - 1 elements of A. On the other hand,

the number of k-element subsets of A that do contain x is C(n - 1, k - 1), since k - 1

elements must be added to x to get such a k-element subset. Since these two collections of

k-element subsets of the original set are disjoint, the Addition Principle gives C(n, k) =

C(n - 1, k) + C(n - 1,k- 1).

(Algebraic)

C(n - 1, k) C' + 1' C C(n - 1, k k- 1- 1) (n1= (n-i1)! + (n-i1)!( )

k! (n - I - k)! (k - 1)! • (n - k)!

(n - 1)! (n - k) (n - 1)! k

k! (n - k)! k! (n - k)!

(n - 1)! (n - k + k)

k! (n - k)!