Mathematics for Computer Science

14.10. Combinatorial Proofs 589

Lemma 14.10.1(Pascal’sTriangle Identity).

n

k

!

D

n 1

k 1

!

C

n 1

k

!

: (14.10)

We provedPascal’s Triangle Identity without any algebra! Instead, we relied
purely on counting techniques.

14.10.2 Giving a Combinatorial Proof

Acombinatorial proofis an argument that establishes an algebraic fact by relying
on counting principles. Many such proofs follow the same basic outline:

1. Define a setS.


2. Show thatjSjDnby counting one way.


3. Show thatjSjDmby counting another way.


4. Conclude thatnDm.

In the preceding example,Swas the set of all possible Olympic boxing teams. Bob
computed

jSjD

n 1

k 1

!

C

n 1

k

!

by counting one way, and Ted 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 (14.10). In this case, the setSof things to be counted is the collection of all
size-ksubsets of integers in the intervalŒ1::nç.