Please, help me to understand following convolution (or give a reference): $$ \sum_{R=0}^N \binom{R}{r} \binom{N-R}{n-r} = \binom{N+1}{n+1} $$ Why is it true?
Thank you!
11
-
$\begingroup$ Dear @ilya.gromov: the formula you gave is not a sentence, hence not even meaningful. I am confident you will get kind help at math.stackexchange.com. $\endgroup$– Peter HeinigCommented Mar 12, 2018 at 17:09
-
1$\begingroup$ @LSpice With that extra sum the equality does not hold (neither with sum up to $n$) $\endgroup$– მამუკა ჯიბლაძეCommented Mar 12, 2018 at 17:13
-
3$\begingroup$ @LSpice, in that case it would be Vandermonde convolution. It's not what I'm looking for. The exprassion I wrote I found in "Probability Theory. The Logic of Science" of Jaynes on page 153. $\endgroup$– ilya.gromovCommented Mar 12, 2018 at 17:32
-
1$\begingroup$ Simply putting the formula into Approach0 returns some posts on math.SE which seem relevant - at least at the first glance - this one seems the closest: Two identities with binomial coefficients. $\endgroup$– Martin SleziakCommented Mar 12, 2018 at 17:58
-
1$\begingroup$ This is really a question for Math Stack Exchange. $\endgroup$– Alexander BursteinCommented Mar 12, 2018 at 23:24
|
Show 6 more comments
1 Answer
$\begingroup$
$\endgroup$
0
I guess that $r \le n$. Then it seems to me that you could proceed as follows: regarding integers as sets (and binomial coefficients as sets of sets, and sums of integers as disjoint unions of sets) in a hopefully obvious way, map $\sum_{R = 0}^N \binom R r\binom{N - R}{n - r}$ to $\binom{N + 1}{n + 1}$ by sending the element $A \times B$ of the $R$th summand to $A \cup \{R + 1\} \cup \{b + R + 2 : b \in B\}$. The inverse map $\binom{N + 1}{n + 1} \to \sum_{R = 0}^N \binom R r\binom{N - R}{n - r}$ sends $\{i_1, \dots, i_r, i_{r + 1}, i_{r + 2}, \dotsc, i_n\}$ to $\{i_1, \dotsc, i_r\} \times \{i_{r + 2}, \dotsc, i_n\}$, viewed as an element of $\binom{\{1, \dotsc, i_{r + 2} - 1\}}r \times \binom{\{i_{r + 2} + 1, \dotsc, N\}}{n - r}$.
EDIT: After following @MartinSleziak's link, I think that this is just Brian M. Scott's answer. I leave it here in case it is an acceptable answer to the question, but mark it community wiki to avoid reputation.