I was reading a course on Combinatorics where I came across following:

The number of ways in which $n$ identical things can be divided into $r$ groups so that no group contains less than $m$ items and more than $k$ (where $m<k$) is coefficient of $x^n$ in the expansion of $(x^m + x^{m+1} + … +x^k)^r$.

Is this correct? Book doesn't give proof. How can we make this formula intuitive?

  • $\begingroup$ If you factor out $x^m$ you get the easy case where you have to divide $n-rm$ identical things into $r$ groups. $\endgroup$ – user53970 May 22 '15 at 17:38

Write $$\underbrace{(x^m + x^{m+1} + … +x^k)(x^m + x^{m+1} + … +x^k)\cdots(x^m + x^{m+1} + … +x^k)}_{r\text{ times}}$$

In order to get a $x^n$ term you must choose a term from each parethesis in a such way that the sum of the exponents is $n$. This is the same as writing $n$ as the sum of $r$ numbers between $m$ and $k$.

  • $\begingroup$ I still didnt get to know from where that $x^n$ term came, and in fact I didnt get from where that whole polynomial came. Does your answer explains that? I think I can do the expansion and get the coefficient of $x^n$ in it. But I dont understand from where all that $x^n$ thingy came. Pardon me for my poor understanding. $\endgroup$ – anir123 May 22 '15 at 20:29

Your Answer

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

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