Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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. –  Robert Israel Sep 16 '11 at 19:02
    
I think you mean ${\sum k_i\choose n}$ on the RHS. –  anon Sep 16 '11 at 19:03
    
You're both right, thank you. –  Nicolas Essis-Breton Sep 16 '11 at 19:10
add comment

1 Answer

up vote 11 down vote accepted

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.

share|improve this answer
    
I see, thanks anon. –  Nicolas Essis-Breton Sep 16 '11 at 19:25
    
@Nicolas: I've now added a nomial derivation. –  anon Sep 16 '11 at 19:39
    
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. –  Nicolas Essis-Breton Sep 16 '11 at 20:13
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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