Combinatorial Equivalences
19 Aug 2008
The Fibonacci Sequence

Many problems are related to the Fibonacci sequence. Lists of such problems are maintained by R Knott: Easy and Hard.

1. A boy runs up a flight of n steps, either taking 1 step or taking 2 steps at a time. How many ways can the boy run up?
2. How many sequences of n coin tosses have no consecutive heads?
3. In how many ways may we pick a subset from 1, 2, 3, 4, ... n so that no two successive numbers are picked?

The Catalan Number

Our textbooks for introductory courses in Combinatorics mentioned that the Catalan Number is the solution to all problems listed below. It is fun to find 1-1 mappings between pairs of problems.

1. How many ways can the expression 2 x 2 x 2 x ... x 2 be parenthesized?
2. How many paths from one corner to the diagonally opposite corner in an n x n matrix do not cross the diagonal?
3. A sequence of n numbers, 1 thru n, is processed as follows: we either drop the next number into a stack, or we pop the topmost number of the stack. In 2n operations, all numbers would have been processed and the stack would also be empty. The output is the sequence of elements that were popped. How many output sequences are possible?
4. In how many ways can a polygon with n sides be triangulated?
5. How many trees with n nodes are there with each node having at most two children?

It turns out that there are tens of problems in combinatorics whose solution is the Catalan number! Check out Richard Stanley's addendum to his book Enumerative Combinatorics and Catalan Numbers by Tom Davis.

Major Theorems in Combinatorics

An exposition by Robert Borgersen that all of the following theorems are equivalent to each other:

1. Marriage Theorem
2. Dilworth's Theorem for partially ordered sets.
3. Birkhoff - Von Neumann Theorem for doubly stochastic matrices.
4. Max-Flow Min-Cut Theorem for directed graphs
5. Menger's Theorem
6. Konig's Theorem for graphs.
7. Konig-Egervary Theorem for graphs

Proofs that Really Count

Proofs that Really Count: The Art of Combinatorial Proof (208 pages, 2003) by Arthur Benjamin and Jennifer Quinn is a beautiful book with techniques for proving combinatorial identities by computing the cardinality of some set in two different ways. For example, let \$latex F_i\$ denote the i-th Fibonacci number. Then Fi equals the number of ways of tiling a rectangular array of size 1 × n with tiles of size 1 × 1 or 2 × 1. This insight can be used to prove Fm + n = Fm - 1 Fn - 1 + Fm Fn by considering the squares at positions m and m + 1: either these are covered with a tile of size 2 × 1 or they are not.