Mathematics for Computer Science

Chapter 14 Cardinality Rules590

Now we’ve already countedSone way, via the Bookkeeper Rule, and found
jSjD

n

k

. The other “way” corresponds to defining a bijection betweenSand the
disjoint union of two setsAandBwhere,

AWWDf.1;X/jXŒ2;nçAND jXjDk 1 g

BWWDf.0;Y/jYŒ2;nçAND jYjDkg:

ClearlyAandBare disjoint since the pairs in the two sets have different first
coordinates, sojA[BjDjAjCjBj. Also,

jAjD# specified setsXD

n 1

k 1

!

;

jBjD# specified setsYD

n 1

k

!

:

Now finding a bijectionf W.A[B/! Swill prove the identity (14.10). In
particular, we can define

f.c/WWD

(

X[f 1 g ifcD.1;X/;

Y ifcD.0;Y/:

It should be obvious thatf is a bijection.

14.10.3 A Colorful Combinatorial Proof

The set that gets counted in a combinatorial proof in different ways is usually de-
fined in terms of simple sequences or sets rather than an elaborate story about
Teaching Assistants. Here is another colorful example of a combinatorial argu-
ment.

Theorem 14.10.2.
Xn

rD 0

n

r

!

2n

nr

!

D

3n

n

!

Proof. We give a combinatorial proof. LetSbe alln-card hands that can be dealt
from a deck containingndifferent red cards and2ndifferent black cards. First,
note that every3n-element set has

jSjD

3n

n

!