Generating function - the number of ways to distribute 100 dollars to n people.

Question

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!

Answer 1

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?

Answer 2

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.