Timeline for Bijective proof of a combinatorial identity: $\sum\limits_{k=0}^n\binom nk^2 \binom k{n-m}=\binom nm \binom{n+m}m$
Current License: CC BY-SA 4.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 11, 2020 at 5:32 | history | edited | Martin Sleziak | CC BY-SA 4.0 |
I have added the identity into the title to make the title more descriptive; of course, feel free to revert my edit if you prefer the original version
|
| Jul 9, 2020 at 16:43 | comment | added | Iosif Pinelis | @MartinSleziak : Thank you for your comments, one providing another bijective proof and the other providing a generalization of the identity. Also, I think you previously suggested this valuable resource, approach0, and I actually bookmarked it, but then forgot about it. | |
| Jul 9, 2020 at 16:34 | comment | added | Iosif Pinelis | @darijgrinberg : Thank you for your comment, which actually answers the question. Your identity is the same I used in the linked answer to reduce (1) to (2). However, I did not realize that it is an instance of the trinomial revision (and I did not even know that term, "trinomial revision"). | |
| Jul 9, 2020 at 15:05 | comment | added | Martin Sleziak | Proving $\sum_{m=0}^n\binom{n}{m}^2 \binom{m}{n-k}=\binom{n}{k}\binom{n+k}{k}$ The answers there point out that this is a special case of $\sum_{k\ge0}\binom ak\binom bk\binom kc=\binom ac\binom{a+b-c}a$. | |
| Jul 9, 2020 at 15:04 | comment | added | Martin Sleziak | I have tried to put this identity into some search engines, specifically Approach0 and SearchOnMath. There is this post, where the answer gives a combinatorial proof: Some binomial coefficient identity | |
| Jul 9, 2020 at 15:03 | comment | added | darij grinberg | First apply the trinomial revision formula (and symmetry of binomial coefficients) to get $\dbinom{n}{k}\dbinom{k}{n-m} = \dbinom{n}{m} \dbinom{m}{k-n+m}$. This lets you factor out $\dbinom{n}{m}$, and the sum turns into an easy Vandermonde convolution. All the steps can be made bijective, since they just use trinomial revision (in the case when everything is a nonnegative integer), symmetry of binomial coefficients and Vandermonde convolution. Thus you get a bijective proof by pasting together these bijections. | |
| Jul 9, 2020 at 14:53 | history | asked | Iosif Pinelis | CC BY-SA 4.0 |