15.13. A Magic Trick 507
Hint:LetSbe the set of all length-nsequences of 0’s, 1’s and a single *.
(b)Now prove (15.23) algebraically by applying the Binomial Theorem to.1C
x/nand taking derivatives.
Homework Problems
Problem 15.35.
Prove the following identity by algebraic manipulation and by giving a combinato-
rial argument:
n
r
!
r
k!
D
n
k!
n k
r k!
Problem 15.36. (a)Find a combinatorial (notalgebraic) proof that
XniD 0n
i!
D 2 n:(b)Below is a combinatorial proof of an equation. What is the equation?Proof.Stinky Peterson ownsnnewts,ttoads, andsslugs. Conveniently, he lives
in a dorm withnCtCsother students. (The students are distinguishable, but
creatures of the same variety are not distinguishable.) Stinky wants to put one
creature in each neighbor’s bed. LetWbe the set of all ways in which this can be
done.
On one hand, he could first determine who gets the slugs. Then, he could decide
who among his remaining neighbors has earned a toad. Therefore,jWjis equal to
the expression on the left.
On the other hand, Stinky could first decide which people deserve newts and slugs
and then, from among those, determine who truly merits a newt. This shows that
jWjis equal to the expression on the right.
Since both expressions are equal tojWj, they must be equal to each other.
(Combinatorial proofs are real proofs. They are not only rigorous, but also con-
vey an intuitive understanding that a purely algebraic argument might not reveal.
However, combinatorial proofs are usually less colorful than this one.)