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.

I have a homework question to solve the number of ways to choose 25 ice creams of a selection of 6 types of ice creams and there are only 7 of each ice cream type.

The question requires the use of generating functions and I have gotten to this point: $$({{x}^{48}}-6{{x}^{40}}+15{{x}^{32}}-20{{x}^{24}}+15{{x}^{16}}-6{{x}^{8}}+1)\cdot {{\left( \frac{1}{1-x} \right)}^{6}}$$

But know I need to find the coefficient of $x^{25}$ and I don't know how to continue.

Can anyone please help?

Thanks a lot,

share|improve this question
add comment

2 Answers

up vote 3 down vote accepted

The power series expression of $\frac{1}{1-x}$ is $\sum_{n = 1}^\infty x^n$, so you can rewrite what you have as $$ (x^{48} - 6x^{40} + 15x^{32} - 20x^{24} + 15x^{16} - 6x^8 + 1)(1 + x + x^2 + x^3 + \cdots)^6. $$

Now, you want to see what ways you can get a term of $x^{25}$. Let $p(n,k)$ be the number of ways to partition the integer $n$ into at most $k$ parts. A term of $x^{25}$ can arise from $-20x^{24} \cdot p(1,6)x$, $15x^{16} \cdot p(9,6)x^9$, $-6x^8 \cdot p(17,6)x^{17}$, or $1 \cdot p(25,6)x^{25}$.

The partition numbers are coming into play because we need to know how many ways we can form a particular power of $x$ by choosing a term from each of the 6 copies of $\frac{1}{1-x}$, but that's precisely the same as asking how many ways you can partition that particular integer exponent into at most 6 parts.

share|improve this answer
    
Thanks a lot, great answer –  Jason Oct 6 '11 at 16:13
add comment

It would be less work to expand $(1-x)^{-6}$ using the binomial theorem: $$ (1-x)^{-6} = \sum_m (-1)^m\binom{-6}{m}x^m $$ and then use the expression for the coefficients in the product of two series.

share|improve this answer
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.