Generating Function: $50 Change

Question

How many ways to collect $50 from 15 distinct people, if the first one gives either 0, 1 or 8 and the other 14 give either 1 or 5.

I started putting writing the function as $f(x)=(1+x+x^8)*(x+x^5)^{14}$

I understand that what we're looking for is the coefficient of $x^{50}$.

How should I proceed?

My first idea would've been to only check for the coefficients of $x^{50}, x^{49}$ and $x^{42}$ for $g(x)=(x+x^5)^{14}$ for the cases if the first person gave respectively 0,1 or 8 bucks and add the results together.

Would that be correct? Could I do it without adding each case separately?

Also, any hint about how to simplify and/or proceed would be a great help!

Answer 1

Your approach is fine. In order to obtain the result manually, it is convenient to use the coefficient of operator $[x^n]$ to denote the coefficient of $x^n$ in a series.

We obtain \begin{align*} \color{blue}{[x^{50}]}&\color{blue}{(1+x+x^8)(x+x^5)^{14}}\\ &=[x^{50}](1+x+x^8)x^{14}(1+x^4)^{14}\tag{1}\\ &=[x^{36}](1+x+x^8)\sum_{j=0}^{14}\binom{14}{j}x^{4j}\tag{2}\\ &=([x^{36}]+[x^{35}]+[x^{28}])\sum_{j=0}^{14}\binom{14}{j}x^{4j}\tag{3}\\ &=\binom{14}{9}+0+\binom{14}{7}\tag{4}\\ &=2002+0+3432\\ &=\color{blue}{5434} \end{align*}

Comment:

• In (1) we factor out $x^{14}$.

• In (2) we use the rule $[x^{p-q}]A(x)=[x^p]x^qA(x)$ of the coeffcient of operator and apply the binomial theorem.

• In (3) we use the linearity of the coefficient of operator and apply the same rule as in (2).

• In (4) we select the coefficients accordingly and observe that only multiples of $4$ of the exponent provide non-zero contributions.

Hint: Small detail due to a comment. In the following we successively skip summands which do not contribute to the coefficient of $x^k$. \begin{align*} [x^{36}]\sum_{j=0}^{14}\binom{14}{j}x^{4j}&=[x^{36}]\sum_{j=9}^{9}\binom{14}{j}x^{4j}=[x^{36}]\binom{14}{9}x^{36}=\binom{14}{9}\\ [x^{35}]\sum_{j=0}^{14}\binom{14}{j}x^{4j}&=[x^{35}]0=0 \end{align*}