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) \}$
How to define the bijective map from $S_L$ to $S_R$.

  • $\begingroup$ Shouldn't the $a_i$'s show up in the equation you're trying to prove? $\endgroup$ – 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.

  • $\begingroup$ But the problem does not ask us to prove it algebraically, but bijectively. Bijective proof means we have to find a bijective map which maps from one set to other different set having same cardinality, CMIIW. $\endgroup$ – El Qanas Sep 30 '15 at 1:01

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.