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.