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?


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.