Is there a simple combinatorial proof for the following identity?
$$\sum_{0\leq i \leq m} \binom{m-i}{j}\binom{n+i}{k} =\binom{m + n + 1}{j+k+1}$$ where $m,j \geq 0$, $k \geq n \geq 0$.
1
-
$\begingroup$ This seems to very similar to Combinatorial proof of $\sum_{i=0}^k\binom{m+k-i-1}{k-i}\binom{n+i-1}{i}=\binom{m+n+k-1}{k}$?. In this question and the linked questions, there is a few similar identities. $\endgroup$– Martin SleziakCommented Mar 10, 2013 at 5:49
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
4
Count $(j+k+1)$ element subsets of an ordered set with ($m+n+1$) elements, organizing the subsets by the value of the $(j+1)$-th largest element in the subset. The product of two binomial coefficients on the left side of the equation is the number of ways to choose the rest of the subset when the $(j+1)$-th largest elements in the subset is the $(m-i)$-th largest element in the whole set.
I think this formula is called the dual Vandermonde or negative Vandermonde identity.
Edit. The inequality between $n$ and $k$ in the question has the wrong sign, it should be $n \leq k$.
-
$\begingroup$ Thanks zyx for your answer and for your note. I appreciate. How do you define "n-th largest element in a subset" including when "n=0"? $\endgroup$– MikeCommented Mar 10, 2013 at 5:50
-
$\begingroup$ There is no need to define "i-th largest element in a finite ordered set" for all i. We know what it means to have a (j+k+1) element subset of an ordered set, and what it means to take the (j+1)-th largest element in that subset, and then we ask what is the rank of that element within the larger set. $\endgroup$– zyxCommented Mar 10, 2013 at 7:08
-
$\begingroup$ It looks to me like the formula requires $n \leq k$, which is the opposite of the inequality written in the question. This forces the $j$ element set to be selected from a set of $m$ or fewer (explaining the $m-i$). $\endgroup$– zyxCommented Mar 10, 2013 at 7:22
-
$\begingroup$ @xyz:Thanks.yes, k should be greater or equal n. $\endgroup$– MikeCommented Mar 10, 2013 at 15:15
$\begingroup$
$\endgroup$
1
(Essentially the same as the above)
Counting the number of lattice paths of length l+j+k+1 from $(0,0)$ to $(j+k+1,l)$ with steps $(0,1)$ and $(1,0)$ in two ways, we can derive this identity. Each path includes $(j,s)$ to $(j+1,s)$ step $(s=0,1\ldots l)$.In this way, we can divide paths into l+1 groups which are mutually exclusive. Hence,
$\sum_{0\leq s \leq l} \binom{s+j}{j}\binom{l-s+k}{k} =\binom{l+j+k+1}{l}$
Setting $l=m+n-(j+k)$, $s=(m-j-i)$, we have the identity in question.
-
1$\begingroup$ What's the need of adding an answer which is the same as an accepted one on a two years old question? $\endgroup$ Commented Nov 28, 2015 at 2:22