Mathematics for Computer Science

14.11. References 621

is it?
X

r 1 Cr 2 Cr 3 Cr 4 Dn;

ri 2 N

n

r 1 ; r 2 ; r 3 ; r 4

!

D‹ (14.25)

Hint:How many terms are there when.wCxCyCz/nis expressed as a sum
of monomials inw;x;y;zbeforeterms with like powers of these variables are
collected together under a single coefficient?

Problem 14.62.

(a)Give a combinatorial proof of the following identity by lettingSbe the set of
all length-nsequences of lettersa,band a singlecand countingjSjis two different
ways.

n2n^1 D

Xn

kD 1

k

n

k

!

(14.26)

(b)Now prove (14.26) algebraically by applying the Binomial Theorem to.1C
x/nand taking derivatives.

Problem 14.63.
What do the following expressions equal? Give both algebraic and combinatorial
proofs for your answers.

(a)

Xn

iD 0

n

i

!

(b)

Xn

iD 0

n

i

!

.1/i

Hint:Consider the bit strings with an even number of ones and an odd number of
ones.