# Find a generating function.

Find a generating function for the number of selections of sticks of chewing gum chosen from eight flavors if each flavor comes in packet of five sticks.

I am having a bit of an issue with figuring out the logic for the above question. My book provides the solution as $g(x)=(1+x^5+x^{10}+...)^8$; however, here's how I solved it:

1. There are eight flavors: $e_1+e_2+e_3+...+e_8$
2. Each favor has five sticks; thus, $r=40$
3. Therefore, $e_1+e_2+e_3+...+e_8=40$ , $0 \leq e_i \leq5$
4. It follows, then, that $g(x) =(1+x+x^2+x^3+...)^8$

Obviously, I'm missing something in my logic. The book and I agree on eight types of objects, but that's it. Could someone help me understand how they got their solution? Based on their answer, I can make a good guess, but I don't fully follow their logic.

Since we are picking 0 or more packets instead of sticks of each flavor, the equation for picking $n$ sticks is \begin{align*} 5e_1+5e_2+\cdots+5e_8 &= n \tag {$e_i \ge 0$} \end{align*}

Hence, \begin{align*} g(x) &= \left(1+x^5+x^{10}+\cdots\right)^8 \\ &= \frac{1}{\left(1-x^5\right)^8} \end{align*}

Simpler problem: Say there is only one flavor. All you can do is pick the number of packets you want. So the number of ways to get $n$ sticks of gum is $1$ if $n$ is a multiple of $5$ and $0$ otherwise. This gives you $F(x)=(1+x^5+x^{10} + \cdots )$.

Now if there are 8 flavors, give them different labels $x_i$. So now to pick $n_i$ packs of flavor $i$. This gives the term $\prod_i x_i^{5*n_i}$. You sum over all possible ways to assign $n_i$. Give the generating series $\prod_i F(x_i)$

But now the problem is asking not to care about which flavors you get so set all the $x_i=x$.

• What threw me off was "selections of sticks" in the problem description. – B.K. May 8 '16 at 3:13

I think that the meant to the package be full or empty, so there no option to a package of 3 or 4 etc.