Using generating function to find total no. of ways to collect 15 dollars given the particular restrictions

Question

Use generating functions to find the number of ways to collect 15 dollar from 20 distinct people if each of the first 19 people can give a dollar (or nothing) and the twentieth person can give either 1 dollar or 5 dollar (or nothing).

Answer 1

You can think of a generating function $G(s)=\sum_{k=0}^\infty a_k s^k$ as like a clothesline (the sum) holding the information (each coefficient of $s^k$) about the $k^{th}$ person using each peg (the $s$).

In your scenario, the coefficient $a_k$ is an indicator (ie $1$ for yes or $0$ for no) of whether the person can provide the amount of money in the index, $k$. So the first 19 people all have generating functions $s^0+s^1=1+s$ as they can provide either $0$ or $1$ units of money, while the final person has generating function $s^0+s^1+s^5=1+s+s^5$, since they can provide $0$, $1$ or $5$ units of money. Now the product of all $20$ such generating products gives us all the information of how many ways there are ($a_k$, the coefficient of $s^k$) to receive a total of each possible amount $k$, ‘pegged’ by being that power of $s$.

We have the following generating function: $$\begin{align} &\left( s^0+s^1 \right)^{19} \left( s^0+s^1+s^5 \right)\\ = & \left( 1+s \right)^{19} \left( 1+s+s^5 \right)\\ = & \left( 1+s+s^5 \right) \sum_{k=0}^{19}\binom{19}{k}s^k. \end{align}$$

And this is where @JMoravitz’s suggestion comes in. We want to find the coefficient of $s^{15}$ as this is the number of ways to collect a total of $15$ units of money. This is most easily done by breaking up the scenarios according to which amount the final $20^{\text{th}}$ person provides and then seeing how much we need from the first 19 to add to reach in total 15. So if the final person gives us 0,1 or 5, then we must collect exactly $15-0,15-1,15-5=15,14,10$ respectively in total from the first 19 people. This is then the coefficient of $s^{15},s^{14},s^{10}$ in the 19-people generating function. This is literally ‘19 choose k’. There are $\binom{19}{15}=3,876$ ways to collect 15 from the 19 people, $\binom{19}{14}=11,628$ ways to collect a possible remaining 15, or $\binom{19}{10}=92,378$ ways to collect a remaining 10.

Finally the overall coefficient of $s^{15}$ in the overall generating product must have been the sum of the coefficients of $s^{10}s^{5}, s^{14}s^{1}, s^{15}s^{0}$. This gives $1\times 92,378+1\times 11,628+1\times 3,876=107,882$ ways in total.

The numbers are so big because the numbers of choices are determined by factorials (inside the binomial coefficients) which grow very fast, so the binomial coefficients grow quite fast. The reason generating functions are useful is we can utilise alternative forms/identities of polynomials to simplify the determination of the coefficients in more complicated situations.

I hope this helps, stay safe