Discrete Mathematics for Computer Science

462 CHAPTER 7 Counting and Combinatorics

A second technique for proving identities using binomial coefficients involves recog-

nizing that the expression

n

(1 +x)n = C(n, i)x'

i=O

can be viewed as a polynomial identity. Since this expression is an identity, its derivative

will also be an identity, so

n (x + 1)n-1 = n i(n, i)xi-1

i=1

This fact is used in evaluating the next sum.

Example 9. Show that in= iC(n, i) = n 2n-1.

Solution. Compute the derivative of

n

(X + 1)n L C(n, i)xn-i

i=0

getting

n(x + 1)n-1 = •iC(n, n i) xi-1.

i=1

Now, substituting x = 1 gives

n

n2n-1 = Z iC(n, i)

In addition to differentiating an identity to produce another identity, it is also possi-

ble to multiply an identity by a power of the variable to produce another identity. Such

techniques will be explored in the exercises (see Section 7.11).

79.2 Multinomials

The computation of the coefficients of terms in expansions of a multinomial such as

(a + b + c)^6 is an obvious generalization of the problem of finding the coefficients for the

expansion of powers of a binomial. These multinomial coefficients can be computed using

the result about counting permutations with repeated letters. For example, the coefficient

of a 2bc^3 in

(a + b + c)^6 = (a + b + c)(a + b + c)(a + b + c)(a + b + c)(a + b + c)(a + b + c)

is determined by choosing, in all possible ways, a from two factors of this product, b from

a different factor, and c from the remaining three factors. The number of ways to do this is

just

6!

2! 1!3!