Understanding a Generating Function

Question

This is from generating functionology by Herbert S Wilf. Here a rule is given as let f $\longleftrightarrow$ {$a_n$}$^{\infty}_0$ is a ordinary power series generating function and let k be a positive integer,then $$f^k \longleftrightarrow [ \sum_{n_1+n_2+\cdots+n_k=n}{a_{n_1}a_{n_2}\ldots a_{n_k}}]_{n=0}^\infty $$ As an example for it a function f(n,k) is taken which denote the number of ways that the nonnegative integer n can be written as an ordered sum of k nonnegative integers. Then he takes the power series $\frac{1}{1-x} \longleftrightarrow $ {1} and uses the above rule to conclude $\frac{1}{(1-x)^k} \longleftrightarrow {f(n,k)}^\infty_{n=0} $ and then says f(n,k) = ${n+k-1} \choose {n}$ , I cant understand how he did the last step, I know this formula $\sum_{k}\binom {n}{k}x^k= (1+x)^n$ , however can't see how he applied it to get that last step

Answer 1

The last step simply follows from calculating the coefficient of $x^{n}$ in the power series expansion of $\dfrac{1}{(1-x)^k}$: \begin{align} \dfrac{1}{n!} \cdot \text{$n$-th derivative of } \dfrac{1}{(1-x)^k} &= \dfrac{1}{n!} \cdot (-1)^{n} (-k) (-k-1) \dots (-k -n+ 1) \\&= \dfrac{(n + k - 1) \dots (k+1) k}{n!} \\=& \dfrac{(n+k-1)!}{n! (k-1)!}\\&= \binom{n+k-1}{n}. \end{align}

Answer 2

The answer is not immediately obvious but you can do it combinatorially as follows. Firtly, $f(n,k)$ counts the number of solutions to the equation $n_1+\cdots+n_k = n$ in non-negative integers. To see the value of $f(n,k)$ consider the classic argument of separating $n$ balls into $k$ bins with $k-1$ separators. For example with $n = 5$ and $k = 4$, one configuration is

$$\bullet||\bullet|\bullet\bullet|\bullet$$ We can show that there is a one-to-one correspondence between the number of ways to count these ball/bin arrangements and $f(n,k)$ $-$ the separators define how big the $n_i$'s will be.

To actually find $f(n,k)$ is a basic counting. We have $n+k-1$ objects but $n$ of them are the same and the rest ($k-1$) are also the same so we have have

$$f(n,k) = \frac{(n+k-1)!}{n!(k-1)!} = \binom{n+k-1}{n}$$.