Discrete Mathematics for Computer Science

Combinatorial Identities 457

Solution. First, restate the problem in terms of urns and balls. How many ways can n

balls be put into r urns? This number is just C(n + r - 1, r - 1). The number of balls in

urn i is just ki for i = 1, 2 .... r. M

Example 7. How many ways can you solve

k 1 +k 2 +k 3 +k 4 = 18

provided that k1, k 2 , k 3 , and k 4 are integers and k 1 , k 2 > 0, k 3 > 3, k 4 > 2?

Solution. First, put the five required values in k 3 and k 4 .Then, ask how many ways there

are to solve

k 1 + k 2 + k3 + k 4 = 13

with k1, k 2 , k 3 , k 4 > 0. This number is just

C(13 +4- 1,4- 1) = C(16, 3)^0

rnCombinatorial Identities

In this section, a representation of the binomial coefficients known as Pascal's triangle is

introduced and used to prove several useful combinatorial identities. Typical arguments

for solving counting problems can be algebraic or combinatorial in nature. We will show

examples of how to prove combinatorial identities using both types of arguments. Com-

binatorial arguments for proving combinatorial identities usually involve counting the

same objects in two different ways. Since the same objects are being counted, the two ex-

pressions for the count must be equal. Often, a combinatorial argument restates the problem

in a context with an obvious interpretation for the two sides of the identity. Theorems 3,

4, and 5 give examples of this kind of a proof. An algebraic argument normally involves

straightforward algebraic manipulations to turn the expression on one side of the identity

into the expression on the other side. Pascal's Triangle is also used to prove a number of

combinatorial identites.

The next two theorems have two proofs each, one an algebraic proof and the other a

combinatorial proof.

Theorem 3. (Newton's Identity) Let n > k > m > 1. Then,

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

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

sets of an n-element set. The left-hand side then counts how many m-element subsets are

contained in an arbitrary k-element subset. The right-hand side first counts the number of

m-element subsets of an n-element set. The right-hand side then determines how many

ways an m-element subset could have elements added to form a k-element subset of the

original set. Since the first step chooses m elements, the augmentation for that m-element

set is done by choosing from the (n - m) elements of the original set that were not chosen.

In both cases, the result is the number of k-element subsets of an n-element set with m of

the k elements distinguished. Therefore, the result follows.