Is the following true? $$\sum_{x_1+x_2+...+x_n=n}\ \ \, \prod_{i=1}^{n}{k_i\choose x_i}={\sum_{i=1}^{n}k_i \choose n} .$$

I tried to use the multinomial theorem, but it doesn't seem applicable.

  • $\begingroup$ This equation doesn't make sense: $x_i$ seem to be dummy variables on the left (you're adding over all ways to write $n$ as the sum of $x_1$ to $x_n$), but free variables on the right. $\endgroup$ – Robert Israel Sep 16 '11 at 19:02
  • $\begingroup$ I think you mean ${\sum k_i\choose n}$ on the RHS. $\endgroup$ – anon Sep 16 '11 at 19:03
  • $\begingroup$ You're both right, thank you. $\endgroup$ – user14108 Sep 16 '11 at 19:10

Combinatorially the equality is obvious. Each way of picking $n$ items out of $k_1+k_2+\cdots+k_n$ items will amount to choosing $x_1$ from first $k_1$, $x_2$ from the next $k_2$, and so on all the way to $x_n$ out of last $k_n$, where the total count of items picked is $x_1+\cdots+x_n=n$ (with some summands possibly being $0$): the number of ways of doing this is ${k_1\choose x_1}{k_2\choose x_2}\cdots{k_n\choose x_n}$ because the selections are independent. Now sum over all $x_i$ with $\small\sum x_i=n$ and you're done.

This can be seen more formally with generating functions too. Write $K=k_1+\cdots k_n$ so that $$(1+u)^K=\sum_{m=0}^K{k_1+\cdots+k_n\choose m}u^m$$ which is also equal to $$(1+u)^{k_1}(1+u)^{k_2}\cdots(1+u)^{k_n}=\large\prod_{i=1}^n\left(\sum_{\ell_i=0}^{k_i}{k_i\choose\ell_i}u^{\ell_i}\right)$$ so that the coefficient of $u^m$ (note this is more general than just the $m=n$ case) is the product of all factors of the form ${k_i\choose\ell_i}$ with $0\le\ell_i\le\ k_i$ where the $\ell_i$'s all add up to $m$. Note however that if $\ell_i>k_i$ the binomial coefficient is $0$ and so it makes no difference if we also add in the products of factors with any of the $\ell_i$'s breaking the inequality: in other words we can write $$=\large\sum_{m=0}^K\left(\sum_{\ell_1+\cdots+\ell_n=m}\;\;\prod_{i=1}^n{k_i\choose\ell_i}\right)u^m.$$ Equating the coefficients gives the desired equality.

  • $\begingroup$ @Nicolas: I've now added a nomial derivation. $\endgroup$ – anon Sep 16 '11 at 19:39
  • $\begingroup$ Wow! very clever anon. Just in case, some may wonder the same thing has me: step (1.) is the binomial theorem, step (2.) recognize $(1+u)^K=(1+u)^{k_1}(1+u)^{k_2}\cdots(1+u)^{k_n}$ and expand each term on the right with the binomial theorem. $\endgroup$ – user14108 Sep 16 '11 at 20:13
  • $\begingroup$ Is there a way to compute the OP's left-hand side with constraints that $x_i\geq 1$ for all $i$? $\endgroup$ – user58955 Mar 21 '16 at 23:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy