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

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!

• Could you tell us about at least one of your failed attempts? – epimorphic May 20 '15 at 17:47

## 2 Answers

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.

• Thanks for this great post. I wonder if the original problem allows for the possibility that some people get no money? In which case I have: The coefficient of x^100 in the expansion of 1/(1 - x)^n. For n=1,2,3,... the first few terms are 1, 101, 5151, 176851, 4598126, 96560646,... which is binomial(100 + n -1, n-1). – Geoffrey Critzer May 23 '15 at 15:56
• @GeoffreyCritzer I wondered that too. I assumed different cases but the 100 people could arrive at different times or all be there to start. I'd planned on convincing myself of the alternative stars and bars formula when I've chance. – Karl May 23 '15 at 19:07

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?

• "...the amount of dollars given person $i$", surely? – Brian Tung May 20 '15 at 18:04
• @BrianTung of course, fixed – gt6989b May 20 '15 at 18:05