CombinatorialIdentity Intermediate

Problem - 4275

(Generalized Vandermonde's Identity) Show that $$\sum_{k_1+\cdots+k_p=m}\binom{n_1}{k_1}\binom{n_2}{k_2}\cdots\binom{n_p}{k_p}=\binom{n_1 + \cdots + n_p}{m}$$


This can be proved in a similar way as the regular Vandermonde's identity by observing the coefficient of the $x^m$ term in the following identity: $$(1+x)^{n_1}(1+x)^{n_2}\cdots(1+x)^{n_p}=(1+x)^{n_1+n_2+\cdots+n_p}$$

On the left side, the answer is $$\sum_{k_1+\cdots+k_p=m}\binom{n_1}{k_1}\binom{n_2}{k_2}\cdots\binom{n_p}{k_p}$$

On the right side, the answer is $$\binom{n_1 + \cdots + n_p}{m}$$

Because these two expressions refer to the same thing, therefore they must be equal.

Meanwhile, this claim can also be explained using the following counting model.

Consider selecting $m$ balls from totally $(n_1+n_2+\cdots + n_p)$ balls. By definition, there are $\binom{n_1 + \cdots + n_p}{m}$ different ways. On the other hand, we can first divide these balls into $p$ different groups with $n_1$, $n_2$, $\cdots$, $n_p$ balls in each of these groups, and then perform casework based on the number of balls drawn from each group in order to count the total possible ways. The answer will be the left side of the to-be-proved identity. Therefore, these two quantities must equal.

report an error