2
$\begingroup$

Let $n$ be a positive integer. How can I derive a bijection to show that the following equality holds?

$2\displaystyle\sum\limits_{j=0}^{n-1} \binom{n-1+j}{j} = \binom{2n}{n}$

In class, we've been deriving bijections using lattice paths in-order to order to show that the size of both sets are the same. So for example, in class we've shown that the size of the set $L(a, b) = \binom{a+b}{b}$, where $L(a, b)$ is the set of lattice paths from (0, 0) to (a, b). Any suggestions?

I should also mention that this MUST be a bijective proof. I know that I can prove this inductively or algebraically really easily, but this isn't what I need to do.

  • 0
    I have also noticed that you would be "double counting some paths", which could be why the sum ends at n-1 ... but I am not sure where the factor of 2 comes from either.2012-10-04

1 Answers 1

5

Consider lattice paths from $\langle 0,0\rangle$ to $\langle n-1,n\rangle$ in the planar lattice $\mathbb{Z}^2$ using unit steps to the right (i.e., $\langle i,j\rangle \to \langle i+1,j\rangle$) and unit steps to the top (i.e., $\langle i,j\rangle \to \langle i,j+1\rangle$).

For each path $\pi$ from $\langle 0,0\rangle$ to $\langle n,n-1\rangle$ let $r(\pi)$ be the smallest $j$ such that $\langle n,j\rangle$ is in $\pi$. For $j=0,\dots,n-1$ let $\Pi_j=\{\pi:r(\pi)=j\}$. Then $|\Pi_j|=\binom{n-1+j}j$ (since the elements in $\Pi_j$ are in bijection with lattice paths from $\langle 0,0\rangle$ to $\langle n-1,j\rangle$, of which there clearly are $\binom{n-1+j}j$), so there are

$\sum_{j=0}^{n-1}|\Pi_j|=\sum_{j=0}^{n-1}\binom{n-1+j}j$ paths from $\langle 0,0\rangle$ to $\langle n,n-1\rangle$.

Let $\Pi_j'$ be the paths from $\langle 0,0\rangle$ to $\langle n-1,n\rangle$ that pass through $\langle j,n\rangle$ but not $\langle j-1,n\rangle$; reflection in the diagonal gives a bijection between $\Pi_j'$ and $\Pi_j$, so there are $\sum_{j=0}^{n-1}|\Pi_j'|=\sum_{j=0}^{n-1}\binom{n-1+j}j$ paths from $\langle 0,0\rangle$ to $\langle n-1,n\rangle$.

Each path from $\langle 0,0\rangle$ to $\langle n,n\rangle$ passes through exactly one of the points $\langle n,n-1\rangle$ and $\langle n-1,n\rangle$, so

$\binom{2n}n=2\sum_{j=0}^{n-1}\binom{n-1+j}j\;.$

  • 0
    @darij: Thanks (and for the other one, too).2015-09-18