Finding a Particular Coefficient Using Generating Functions

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.

Thanks a lot,

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.

• Thanks a lot, great answer – Jason Oct 6 '11 at 16:13

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.

• Note that OP wants just the coefficient of $x^{25}$, thus most of the first polynomial is irrelevant. – vonbrand Apr 22 '14 at 18:18

It might be useful (or not) to note that the first factor is $$(z^8 - 1)^6$$. Try:

\begin{align*} [x^{25}] (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 &= [x^{25}] (1 - 6 x^8 + 15 x^{16} - 20 x^{24}) \cdot \sum_{k \ge 0} (-1)^k \binom{-6}{k} x^k \\ &= ([x^{25}] - 6 [x^{17}] + 15 [x^9] - 20 [z]) \sum_{k \ge 0} \binom{k + 6 - 1}{6 - 1} z^k \\ &= \binom{25 + 5}{5} - 6 \binom{17 + 5}{5} + 15 \binom{9 + 5}{5} - 20 \binom{1 + 5}{5} \\ &= 14412 \end{align*}