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$
    – მამუკა ჯიბლაძე
    May 7 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
    May 7 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
    May 7 at 18:46
  • $\begingroup$ Yes, that's right. $\endgroup$
    – Todd Trimble ♦
    May 7 at 19:12
  • $\begingroup$ Or rather, it’s right if we constrain $i,j,k,l > 0$. $\endgroup$
    – Geoffrey Irving
    May 8 at 8:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.