# A combinatorial identity involving binomial coefficients

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 ?

• 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$. May 7 at 18:30
• 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$. May 7 at 22:56

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.

• 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$$ ? May 7 at 18:46
• Yes, that's right. May 7 at 19:12
• Or rather, it’s right if we constrain $i,j,k,l > 0$. May 8 at 8:51