Transcript Proofs that Really Count: The Art of Combinatorial Proof

Proofs That Really Count
The Art of Combinatorial Proof
Bradford Greening, Jr.
Rutgers University - Camden
Theme
Show elegant counting proofs for several mathematical identities.
•
Proof Techniques
•
Pose a counting question
•
Answer it in two different ways. Both answers solve the same
counting question, so they must be equal.
2
 n  1
k 


2
k 1


n
Identity: For n ≥ 0,
Q:
Number of ways to choose 2 numbers from {0, 1, 2, …, n}?
1.
 n  1
By definition,  2 
2.
Condition on the larger of the two chosen numbers.
If larger number = k, smaller number is from {0, 1, …, k – 1}
n
Summing over all k, the total number of selections is
k
k 1
3
 n 
n 1

2
 2k 
Identity: 
k 0 

Q:
Count ways to create a committee of even size from n people?
1.
n n n
 n
 n
       ...       


For 2k ≤ n,  0   2   4 
 2k  k 0  2k 
4
 n 
n 1

2
 2k 
Identity: 
k 0 

Q:
Count ways to create a committee of even size from n people?
2.
A committee of even size can be formed as follows:
Step 1: Choose the 1st person ‘in’ or ‘out’
2 ways
Step 2: Choose the 2nd person ‘in’ or ‘out’
2 ways
Step n-1: Choose the (n-1)th person ‘in’ or ‘out’
Step n: Choose the nth person ‘in’ or ‘out’
2 ways
1 way
By multiplication rule, there are 2n-1 ways to form this committee.
5
n
 
k 
•
: “n multi-choose k”
Counts the ways to choose k elements from a set of n elements
with repetition allowed
{1, 2, 3, 4, 5, 6, 7, 8}
{1, 3, 3, 5, 7, 7}
(n = 8, k = 6)
or
{1, 1, 1, 1, 1, 1}
6
Identity:
Q:
1.
n
  n  1 
k    n

k
k

1

 

How many ways to create a non-decreasing sequence of length k
with numbers from {1, 2, 3, …, n} and underline 1 term?
n
There are   k   ways to create the sequence, then k ways to


choose the underlined term.
9
Identity:
n
  n  1 
k    n

k
k

1

 

Q:
How many ways to create a non-decreasing sequence of length k
with numbers from {1, 2, 3, …, n} and underline 1 term?
2.
Determine the value that will be underlined, let it be r.
Make a non-decreasing sequence of length k-1 from {1, 2, 3, …, n+1}.
Convert this sequence:
•
•
Any r’s chosen get placed to the left of our underlined r.
Any n+1’s chosen get converted to r’s and placed to the right of our r.
  n  1 
Hence, there are n  
 such sequences.

  k  1 
10
Identity:
n
  n  1 
k    n

k
k

1

 

Example: n = 5, k = 9, and our underlined value is r = 2 , then we
are choosing a length 8 sequence from {1, 2, 3, 4, 5, 6}
1. Choose “r”
8-sequence: 1 1 2 3 3 5 6 6
2. Create k-1 sequence
from n+1 numbers
converts to
3. Convert
9-sequence: 1 1 2 2 2 2 3 3 5
11
Fibonacci Numbers
Fibonacci Numbers – a number sequence defined as
•
F0 = 0, F1 = 1,
•
and for n ≥ 2, Fn = Fn-1 + Fn-2
i.e. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144…
5+8
12
Fibonacci Nos: Combinatorial Interpretation
fn : Counts the ways to tile an n-board with squares and dominoes.
13
Fibonacci Nos: Combinatorial Interpretation
Example: n = 4, f4 = 5
14
Fibonacci Nos: Combinatorial Interpretation
fn : Counts the ways to tile an n-board with squares and dominoes.
Define f-1 = 0 and let f0 = 1 count the empty tiling of 0-board.
Then fn is a Fibonacci number and for n ≥ 2,
fn = fn-1 + fn-2 = Fn + 1
15
Fibonacci Nos: Combinatorial Interpretation
Q: How many ways to tile an n-board with squares and dominoes?
If the first tile is a square, there are
fn – 1 ways to complete sequence.
If the first tile is a domino, there are
fn – 2 ways to complete sequence.
Hence, fn = fn – 1 + fn – 2 = Fn + 1
16
Identity: For n ≥ 0, f0 + f1 + f2 + … + fn = fn+2 -1
Q: How many tilings of an (n+2)-board have at least 1 domino?
1.
By definition there are fn + 2 tilings of an (n+2)-board;
excluding the “all-squares” tiling leaves fn + 2 – 1.
17
Identity: For n ≥ 0, f0 + f1 + f2 + … + fn = fn+2 -1
Q: How many tilings of an (n+2)-board have at least 1 domino?
Consider the last domino
(in spots k+1 & k+2).
3
...
n
n+1 n+2
1
2
3
...
n
n+1 n+2
1
2
n
n+1 n+2
n
n+1 n+2
n
n+1 n+2
Summing
over
k+1
Cells 1, 2,
…,allkpossible
locations of k gives LHS.
k+2
1
2
1
2
3
3
3
...
...
...
fn
fn-1
...
fk ways to tile first k spots
1 way to tile remaining spots
...
•
•
2
...
2.
1
f2
f1
f0
18
Identity: For n ≥ 1, 3fn = fn+2 + fn-2
Set 1: Tilings of an n-board; by definition, |Set 1| = fn
Set 2: Tilings of an (n+2)-board or an (n-2)-board;
by definition, |Set 2| = fn+2 + fn-2
Create a 1-to-3 correspondence between the set of n-tilings and the
set of (n+2)-tilings and (n-2)-tilings.
19
Identity: For n ≥ 1, 3fn = fn+2 + fn-2
For each n-tiling, make 3 new tilings
• by adding a domino
• by adding two squares
n-tiling
• a. if n-tiling ends in a square, put
a domino before the last square.
• b. if n-tiling ends in a domino,
remove the domino
n-tiling
n-tiling
(n-1)-tiling
(n-2)-tiling
20
n
Identity: For n ≥ 0,

k 0
f k   f n f n 1
2
We say there is a fault at cell i, if both tilings are breakable at cell i.
1
2
3
4
5
6
7
8
9
1
2
3
4
5
6
7
8
9
10
10
21
n
Identity: For n ≥ 0,

k 0
f k   f n f n 1
2
Q: How many tilings of an n-board and (n+1)-board exist?
1.
By definition, fn fn+1 tilings exist.
2.
Place the (n+1)-board directly above the n-board.
Consider the location of the last fault.
1
2
3
...
n
1
2
3
...
n
n+1
22
n
Identity: For n ≥ 0,

k 0
f k   f n f n 1
2
How many tiling pairs have their last fault at cell k?
•
There are ( fk )2 ways to tile the first k cells.
•
1 fault free way to tile the remaining cells:
…
k
Summing over all possible
locations of k gives LHS.
...
k-1, k
23
n 2
Identity: For n ≥ 0,
2n
= fn + fn-1 + 
k 0
f k  2n 2k
Q: How many binary sequences of length n exist?
1.
There are 2n binary sequences of length n.
2.
For each binary sequence define a tiling as follows:
“1” is equivalent to a square in the tiling.
“01” is equivalent to a domino.
24
n 2
Identity: For n ≥ 0,
2n
= fn + fn-1 + 
k 0
f k  2n 2k
Example:
The binary sequence 011101011 maps to the 9-tiling shown below.
01
1
1
01
01
1
If no “00” exists, this gives a unique tiling of length
•
n (if the sequence ended in “1”)
•
n-1 (if the sequence ended in 0)
25
n 2
Identity: For n ≥ 0,
2n
= fn + fn-1 + 
k 0
f k  2n 2k
What if “00” exists?
Let the first occurrence of “00” appear in cells k+1, k+2 (k ≤ n-2)
1
2
3
4
...
0 0
k
k+1 k+2 k+3
fk
...
n-1 n
2n-2-k
Match this sequence to the k-tiling defined by the first k terms of
the sequence. (Note: k > 0, then the kth digit must be “1”)
Each k-tiling will be counted 2n-2-k times.
26
n 2
Identity: For n ≥ 0,
01
1
01
2n
= fn + fn-1 + 
k 0
01101000000
01101000001
01101000010
01101000011
01101000100
01101000101
01101000110
01101000111
f k  2n 2k
01101001000
01101001001
01101001010
01101001011
01101001100
01101001101
01101001110
01101001111
16 length-11 binary sequences generate the same 5-tiling
27
Lucas Numbers
Lucas Numbers – a number sequence defined as
•
L0 = 2, L1 = 1,
•
and for n ≥ 2, Ln = Ln-1 + Ln-2
i.e. 2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, …
11+18
28
Lucas Nos: Combinatorial Interpretation
ln : Counts the ways to tile a circular n-board (called bracelets) with
curved squares and dominoes.
29
Lucas Nos: Combinatorial Interpretation
“out-of-phase” – a
tiling where a domino
covers cells n and 1
“in-phase” – all other
tilings
30
Lucas Nos: Combinatorial Interpretation
ln : Counts the ways to tile a circular n-board (called bracelets) with
curved squares and dominoes.
Let l0 = 2, and l1 = 1. Then for n ≥ 2,
ln = ln-1 + ln-2 = Ln
31
Lucas Nos: Combinatorial Interpretation
Q: How many ways to tile a circular n-board?
Note that the first tile can be
• a square covering cell 1
• a domino covering cells 1 and 2
• a domino covering cells n and 1
4
1
3
2
32
Lucas Nos: Combinatorial Interpretation
Consider the last tile (the tile counterclockwise before the first tile)
Since the first tile determines
Hence, lnthe
= phase,
ln-1 + fixing
ln-2 = the
Ln last tile shows us
ln-1 tilings ending in a square and ln-2 tilings ending in a domino
33
Identity: For n ≥ 1, Ln = fn + fn-2
Question: How many tilings of a circular n-board exist?
1. There are Ln circular n-bracelets.
2. Condition on the phase of the tiling:
in-phase straightens into an n-tiling, thus fn in-phase bracelets
out-of-phase: must have a domino covering cells n and 1
cells 2 to n-1 can be covered as a straight (n-2)-board,
thus fn-2 out-of-phase bracelets.
34
Identity: For n ≥ 1, Ln = fn + fn-2
n
n
35
Continued Fractions
Given a0 ≥ 0, a1 ≥ 1, a2 ≥ 1, …, an ≥ 1, define [a0, a1, a2, …, an] to be
the fraction in lowest terms for
a0 
1
a1 
1
a2 
For example, [2, 3, 4] = 2 
1
a3 
1
1
...
30

1
13
3
4
1

an
36
Continued Fractions: Comb. Interpretation
Define functions p and q such that the continued fraction
[a0, a1, a2, …, an] =
p(a0 , a1 , a2 ,..., an )
p
 n
q(a0 , a1 , a2 ,..., an )
qn
when reduced to lowest terms.
37
Continued Fractions: Comb. Interpretation
Let Pn = P(a0, a1, a2, …, an) count the number of ways to tile an
(n+1)-board with dominoes and stackable square tiles.
Height Restrictions:
• The ith cell may be covered by a stack of up to ai square tiles.
• Nothing can be stacked on top of a domino.
38
Continued Fractions: Comb. Interpretation
a1
a3
an
a0
an-1
a2
0
1
2
...
...
3
...
n-1
n
39
Continued Fractions: Comb. Interpretation
Recall Pn counts the number of ways to tile an n+1 board with
dominoes and stackable square tiles.
Let Qn = Q(a0, a1, a2, …, an) count the number of ways to tile an
n-board with dominoes and stackable square tiles.
Define Qn = P(a1, a2, …, an).
Pn
pn

 [a0 , a1 , a2 , ... , an ]
Then
Qn
qn
40
Continued Fractions: Comb. Interpretation
a1
a3
an
a0
Pn
an-1
a2
0
1
...
...
2
3
...
n-1
n
a1
a3
an
an-1
Qn
a2
1
2
...
...
3
...
n-1
n
41
Continued Fractions: Comb. Interpretation
15
7
3
0
1
For example, the beginning of the
“π-board” given by [3, 7, 15] can be
tiled in 333 ways:
• all squares = 315 ways
• stack of squares, domino = 3 ways
• domino, stack of squares = 15 ways
2
15
7
Removing the initial cell, the
[7, 15]-board can be tiled in 106 ways:
• all squares = 105 ways
• domino = 1 way
Thus [3, 7, 15] = 333 ≈ 3.1415
106
1
2
42
What else?
•
Linear Recurrences
•
Continued Fractions
•
Binomial Identities
•
Harmonic Numbers
•
Stirling Numbers
•
Number Theory
Includes many open identities…
43
References
All material from
“Proofs That Really Count: The Art of Combinatorial Proof”
By
Arthur T. Benjamin, Harvey Mudd College
and
Jennifer J. Quinn, Occidental College
©2003
44