I am currently a district math student and am learning generating functions. I was working on a question for a while and still couldn't find an answer to it. Here is the question:
Find the generating function for the sequence (a_0, a_1, a_2,...) defined as follows:
a_n = the number of ways to distribute 100 dollars to n people.
Find a closed form for that generating function.
Please tell me how I should approach this question/give me a hint on how to start. Thank you very much!
Hint With a hard problem it's sometimes easier to consider an easier one.
Suppose the problem was finding the number of ways to distribute £5 to $n$ people.
For $n=1$ There is no choice but to give them all the money.
$\circ \circ\circ\circ \circ $
For $n=2$ I can share out the money by inserting a blue bar in the gaps of the coins to show who gets what. Note there are $4$ possible gaps.
$\circ \color{blue}{|}\circ\circ\circ \circ \\ \circ\circ\color{blue}{|}\circ\circ \circ \\ \circ \circ\circ\color{blue}{|}\circ \circ \\ \circ\circ\circ\circ \color{blue}{|}\circ $
There are 4 possible ways to divide the money.
For $n=3$ Now we will have to insert two bars. There are 4 possible places to put the first blue bar and only 3 possible ways to put the second red bar.
$\circ \color{blue}{|}\circ\color{red}{|}\circ\circ \circ$
There are clearly $4\times 3$ ways to do this. Note this is the same as $\frac{4!}{(4-2)!}$
However we could swap the blue and red bars and the portioning of monies would be unaltered. $\circ \color{blue}{|}\circ\color{red}{|}\circ\circ \circ$ is the same as $\circ \color{red}{|}\circ\color{blue}{|}\circ\circ \circ$ They can be swapped in $2\times 1$ (deciding which colour is first).
We therefore have $2!$ too many.
The number of ways of splitting the money between three people is therefore $\frac{4!}{(4-2)!2!}$
This is otherwise known as $\binom{4}{2}=6$
For $n=4$ Now we will have to insert three bars. There are 4 possible places to put the first blue bar, 3 possible ways to put the second red bar and only 2 for the third green bar. $\circ \color{blue}{|}\circ\color{red}{|}\circ\color{green}{|}\circ \circ$ This time there are $3\times2\times1$ too many because swapping the colours will leave the partitioning unaffected. To summarise there are $\frac{4!}{(4-3)!3!}=\binom{4}{3}=4$ possible ways.
For $n=5$ there is only one way of giving out the money.
The generating function $G(x)$ for this example is therefore $G(x)=1x^1+4x^2+6x^3+4x^4+1x^5$
The 100 question works along similar principles. Hope this helps.
Hints
If we find what $a_n$ is, the generating function should be easy to get from its definition.
To find $a_n$, define $x_1. \ldots x_{100}$ the amount of dollars given person $i$. You need to make sure $\sum_{i=1}^{100} x_i = 100$. How many solutions does this system have?
Consider that there is 1 way to give a person 0 dollars, 1 way to give them 1 dollar, and so on. This gives the generating function:
$\begin{align*} p(z) &= \sum_{k \ge 0} z^k \\ &= \frac{1}{1 - z} \end{align*}$
(bear with me, the sum should go up to $k = 100$, but the extra terms don't affect the result, and simplify the algebra that follows).
If you have $n$ people, the ways to give them $M$ dollars in all ($[z^M]$ is the coefficient of $z^M$ in what follows) is:
$\begin{align*} [z^M] p^n(z) &= [z^M] \frac{1}{(1 - z)^n} \\ &= (-1)^M \binom{-n}{M} \\ &= \binom{n + M - 1}{n - 1} \end{align*}$
The extra terms in $p(z)$ can't affect the result, as you can easily see.
