# Four models of combinatorial proof

Today I heard someone mention there are four combinatorial models to prove identities: tiling, flagpole, block walking and committee selection. I am familiar with the last one and up till this point I thought it was THE combinatorial method.

For example it's not hard to show $\sum_{k=0}^n \binom nk^2 = \binom {2n}{n}$ by selecting committees. If it's at all possible how would one use other models to prove this identity? I can't find any info about these models in my book. All the proofs are either algebraic or by committee selection. If you(anyone) don't mind, can I get three simple examples demonstrating these models?

## 1 Answer

I feel like anyone who would reduce even basic combinatorics to a statement as dry as "there are four models..." has got to hate the subject. Anyway.

Suppose you are trying to get from point $(0,0)$ to point $(n,n)$ by taking steps of $(+1,0)$ or $(0,+1)$ (up or right). How many different paths can you take?

On the one hand, you need to take a total of $n$ steps up and $n$ steps right, and there are $\binom{2n}{n}$ ways to rearrange those (if you like, $\binom{2n}{n}$ ways to choose which steps will be the up steps).

On the other hand, at some point you have to come to the line $x+y=n$, at which point you will stand on some point of the form $(k,n-k)$. So we can do casework on the value of $k$.

For each $k$, there are $\binom{n}{k}$ ways to get from $(0,0)$ to $(k,n-k)$: you take $n$ steps there, and $k$ of them are steps to the right, so there's $\binom{n}{k}$ ways to choose which ones those are. There are also $\binom{n}{k}$ ways to get from $(k,n-k)$ to $(n,n)$: that's $k$ steps up out of $n$ steps total, so there's $\binom{n}{k}$ ways to choose which ones those are.

So there's $\binom{n}{k}^2$ ways to choose a path from $(0,0)$ to $(n,n)$ passing through $(k,n-k)$, and summing over all $k$ we get $$\sum_{k=0}^n \binom{n}{k}^2 = \binom{2n}{n}.$$

So that's probably "block walking". "Tiling" would be something like "fill two $1 \times n$ rectangles with $n$ $1\times 1$ red tiles and $n$ $1\times 1$ blue tiles" and if you can select committees, you should have no trouble with that.

I have no idea what flagpoles are.