Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

What is the combinatorial meaning of $$\sum_{R = 0}^{N}\binom{N}{r}\binom{N-R}{n-r} = \binom{N+1}{n+1} \quad?$$ If the summing is performed with respect to $r$, i.e. $$\sum_{r = 0}^{n}\binom{N}{r}\binom{N-R}{n-r} = \binom{N}{n},$$ then it has clear combinatorial meaning: the number of combinations by taking $n$ balls from an urn containing $R$ red balls and $N-R$ white balls.

share|cite|improve this question
Could you provide an example? Also, could you please give more context to this question eg. stating a distribution (hyper-geo; negative-binomial etc.) – bryansis2010 Feb 4 '13 at 8:01
up vote 1 down vote accepted

This is an adaptation of this answer to another question.

You are asking about an identity that reads, for $k,m,n\in\mathbf N$: $$ \sum_{i=0}^k\binom im\binom{k-i}n=\binom{k+1}{m+n+1}. $$ It is a variation of the Vandermonde identity, which reads, for $k,l,m\in\mathbf N$: $$ \sum_{i=0}^m\binom ki\binom l{m-i}=\binom{k+l}m, $$ and which is combinatorially explained by counting the possibilities to choose a team of $m$ children among $k$ girls and $l$ boys.

Here is a cominatorial explaination for the variation asked about. Choose a subset of $m+n+1$ numbers $a_j$ from the $k+1$-set $\{0,\ldots,k\}$, and arrange them in increasing order $0\leq a_0<\cdots<a_{m+n}\leq k$. Put $i=a_m$, then there are $\binom im$ choices left for $a_0,\ldots,a_{m-1}$, and $\binom{k-i}n$ choices for $a_{m+1},\ldots,a_{m+n}$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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