Mathematics for Computer Science

14.11. References 591

n-element subsets.

From another perspective, the number of hands with exactlyrred cards is

n

r

!

2n

nr

!

since there are

n

r

ways to choose therred cards and

2n

nr

ways to choose the

nrblack cards. Since the number of red cards can be anywhere from 0 ton, the

total number ofn-card hands is:

jSjD

Xn

rD 0

n

r

!

2n

nr

!

:

Equating these two expressions forjSjproves the theorem. 

Finding a Combinatorial Proof

Combinatorial proofs are almost magical. Theorem 14.10.2 looks pretty scary, but

we proved it without any algebraic manipulations at all. The key to constructing a

combinatorial proof is choosing the setSproperly, which can be tricky. Generally,

the simpler side of the equation should provide some guidance. For example, the

right side of Theorem 14.10.2 is

3n

n

, which suggests that it will be helpful to

chooseSto be alln-element subsets of some3n-element set.

14.11 References

[4], [8], [14]

Problems for Section 14.2

Practice Problems

Problem 14.1.

Alice is thinking of a number between 1 and 1000.

What is the least number of yes/no questions you could ask her and be guaranteed

to discover what it is? (Alice always answers truthfully.)

(a)