3
$\begingroup$

When I was reading an article by CHUN-GANG JI (A SIMPLE PROOF OF A CURIOUS CONGRUENCE BY ZHAO), he mentioned in the acknowledgement the following identity

$$\sum_{i+j+k=p,\text{ } i,j,k\gt 0}{p\choose i}{p\choose j}{p\choose k}={3p\choose p}-3{2p\choose p}+3$$

Can anybody give me a lead to a combinatorial or algebraic proof of this identity ?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Combinatorial proof must be also easy to find: fixing a subdivision of a $3p$-element set $S$ into three $p$-element subsets $P_1$, $P_2$, $P_3$ produces from each $p$-element subset $P$ of $S$ (of which there are $\binom{3p}p$) a triple $P_1\cap P$, $P_2\cap P$, $P_3\cap P$ of subsets of a $p$-element set with total cardinality $p$. These are "not ours" iff $P$ is included in $P_1\cup P_2$, $P_1\cup P_3$ or $P_2\cup P_3$, each of the latter having $2p$ elements - $3\binom{2p}p$ cases to be excluded. But here we excluded twice each of the three cases when $P$ coincides with one of the $P_i$. $\endgroup$
    – მამუკა ჯიბლაძე
    Commented May 7, 2023 at 18:30
  • 6
    $\begingroup$ Another proof is to compute in two ways the coefficient of $x^p$ in $[(1+x)^p-1]^3 =(1+x)^{3p} -3(1+x)^{2p} +3(1+x)^p -1$. $\endgroup$
    – Ira Gessel
    Commented May 7, 2023 at 22:56

1 Answer 1

Reset to default
6
$\begingroup$

Without the inequality on the $i, j, k$, the sum on the left would be $\binom{3p}{p}$. This is an immediate consequence of the Chu-Vandermonde convolution identity

$$\sum_{i+j = k} \binom{x}{i}\binom{y}{j} = \binom{x+y}{k}$$

which is treated in many places, for example in Concrete Mathematics by Graham, Knuth, and Patashnik.

By an inclusion-exclusion argument, the adjustment one must make to account for the inequality in the sum is to subtract the sum where at least one of the $i, j, k$ is $0$, then add back in the sum where at least two of them are $0$. For example, the sum over all cases where $k = 0$ is

$$\sum_{i+j=p} \binom{p}{i}\binom{p}{j} = \binom{2p}{p}$$

where again we use Chu-Vandermonde. This leads to the answer you want.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Thanks a lot is true that $$\sum_{i+j+k+l=p}{p\choose i}{p\choose j}{p\choose k}{p\choose l}={4p \choose p}-4{3p\choose p}+6{2p\choose p}-4$$ ? $\endgroup$
    – wkmath
    Commented May 7, 2023 at 18:46
  • $\begingroup$ Yes, that's right. $\endgroup$
    – Todd Trimble
    Commented May 7, 2023 at 19:12
  • $\begingroup$ Or rather, it’s right if we constrain $i,j,k,l > 0$. $\endgroup$
    – Geoffrey Irving
    Commented May 8, 2023 at 8:51

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .