2
$\begingroup$

Identity \begin{equation} \sum_{k=0}^n\binom nk^2 \binom k{n-m}=\binom nm \binom{n+m}m \tag{1} \end{equation} was used in an answer here. As shown in that answer, (1) easily reduces to \begin{align} \sum_{k=0}^n\binom nk \binom m{n-k}=\binom{n+m}n, \tag{2} \end{align} which latter admits an obvious bijective proof.

Question: Is there a bijective proof of the original identity (1), without the reduction to (2)?

A possibly relevant reference is to automated search for bijective proofs.

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ 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. $\endgroup$
    – darij grinberg
    Commented Jul 9, 2020 at 15:03
  • 2
    $\begingroup$ 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 $\endgroup$
    – Martin Sleziak
    Commented Jul 9, 2020 at 15:04
  • 2
    $\begingroup$ 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$. $\endgroup$
    – Martin Sleziak
    Commented Jul 9, 2020 at 15:05
  • $\begingroup$ @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"). $\endgroup$
    – Iosif Pinelis
    Commented Jul 9, 2020 at 16:34
  • $\begingroup$ @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. $\endgroup$
    – Iosif Pinelis
    Commented Jul 9, 2020 at 16:43

0

Reset to default

You must log in to answer this question.