Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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
add comment

1 Answer

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|improve this answer
add comment

Your Answer

 
discard

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.