Find the number of 5-combinations of the multi-set {4*a, 4*b, 4*c} using generating functions.

Because I am finding combinations I know that I have to use ordinary generating functions and not exponential generating functions.

I can first represent this as $$(1+x+x^2+x^3+x^4)(1+x+x^2+x^3+x^4)(1+x+x^2+x^3+x^4)$$ $$=(1+x+x^2+x^3+x^4)^3$$

I'm not sure where to go from here though- I would greatly appreciate any advice or help! Thanks.

  • $\begingroup$ You could expand that polynomial (though that's probably not the cleanest way to do it) $\endgroup$ Dec 5 '13 at 18:32
  • $\begingroup$ After expanding it, what would I do to find the exact number of 5-combinations? $\endgroup$ Dec 5 '13 at 19:42
  • $\begingroup$ As already mentioned in the answer, you'd be looking for the coefficient to $x^5$. (Remember, the exponents in generating functions mean something; it's not just a magic formula) $\endgroup$ Dec 5 '13 at 19:45
  • $\begingroup$ If I'm looking at the coefficient of x^5 wouldn't it be -3? Can you explain your comment a little more or help me find more information on that. Thanks!! $\endgroup$ Dec 5 '13 at 21:44
  • $\begingroup$ Given that the polynomial has zero negative signs, I haven't a clue where you got a negative sign from. $\endgroup$ Dec 5 '13 at 21:48

This is the coefficient of $x^5$ in the expansion of $(1+x+x^2+x^3+x^4)^3 = (1-x^5)^3/(1-x)^3 = (1-3x^5 +3x^{10} -x^{15})\displaystyle\frac{1}{(1-x)^3} $. Can you find a taylor series expansion for the second term in the product?


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.