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' 1' C
k 1(n-i1)!
(n-i1)!
C(n - 1, k) + C(n - 1, k- 1)
(n1=
+
(
)
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)!