# Bijective proof of binomial determinant using gessel-viennot (from Aigner)

This is problem 5.74 (page 230) from Aigner "A Course in Enumeration".

Give a bijective proof using Gessel-Viennot of

$\text{det}$ ${m+i-1}\choose j$$^n_{i,j=1} =$${m+n-1}\choose n$

where $m-1\geq a_1 \geq a_2 \geq ...\geq a_n\geq 0$.

I think we can use these lemmas:

for RHS:
Lemma 1. The number of paths from $(x,y)$ to $(x+z, y+w)$ is ${z+w}\choose z$.

for LHS (Corollary of Gessel-Viennot Lemma):
Lemma 2. Let $M$ be the $k \times k$ matrix where $M_{ij}$ is the number of lattice paths from $v_i$ to $u_j$ then $\text{det}M$ is the number of non-intersecting $k$-paths.

For example for $n=2$ and $m=3$
$S_L=\{ (NNE,NNE),(NNE,NEN),(NNE, ENN), (NEN, NEN), (NEN,ENN),(ENN, ENN) \}$
$S_R=\{ NNEE, NENE, NEEN, ENNE, ENEN, EENN \}$
How to define the bijective map from $S_L$ to $S_R$.

• Shouldn't the $a_i$'s show up in the equation you're trying to prove? – Tad Sep 30 '15 at 3:11

I know very little about those enumerative technique but I have to say the claim is not hard at all to prove through elementary means, since the identity $$\binom{a+1}{b}=\binom{a}{b}+\binom{a}{b-1}$$ gives a straightforward way to perform gaussian elimination on our matrix; once we put it in upper or lower triangular form, to compute its determinant is an easy task.