1
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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*}

$\endgroup$
1
$\begingroup$

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$.

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

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

$\endgroup$

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.