Mathematics for Computer Science

Chapter 15 Cardinality Rules478

by counting one way, and Oscar computed

jSjD

n

k

!

by counting another way. Equating these two expressions gave Pascal’s Identity.

Checking a Combinatorial Proof

Combinatorial proofs are based on counting the same thing in different ways. This
is fine when you’ve become practiced at different counting methods, but when in
doubt, you can fall back on bijections and sequence counting to check such proofs.
For example, let’s take a closer look at the combinatorial proof of Pascal’s Iden-
tity (15.4). In this case, the setSof things to be counted is the collection of all
size-ksubsets of integers in the intervalŒ1;nç.
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 (15.4). 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.

15.11.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