# 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? May 20, 2015 at 17:47

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). May 23, 2015 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, 2015 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? May 20, 2015 at 18:04
• @BrianTung of course, fixed May 20, 2015 at 18:05

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.