# Finding the Generating Function for $\sum_{n_1 +n_2 + \ldots + n_k = n} n_1 n_2 \cdot \ldots \cdot n_k$

I'm studying problem 2.6 (p. 65) in Herbert Wilf's generatingfunctionology (released by the author for free online). This problem actually has a solution already written in the back of the book (p. 203) which I'm trying to understand.

Problem: For $k, n \in \mathbb{N}$, let $f(n,k)$ be defined as follows:

$$\sum_{n_1 +n_2 + \ldots + n_k = n} n_1 n_2 \cdot \ldots \cdot n_k$$

Find the following:

(i) the ordinary power series generating function of $f$ (i.e., the $opsgf$ of $f$)

(ii) a simple formula for it

Book Solution:

$$\sum_{n_1 +n_2 + \ldots + n_k = n} n_1 n_2 \cdot \ldots \cdot n_k \\ = [x^n] \left(\sum_r rx^r \right)^k \\ = [x^n] \left \{ \frac{x}{(1-x)^2} \right \}^3 \\ = [x^n] \frac{x^k}{(1-x)^{2k}} \\$$

Hence $\sum_n f(n,k) x^n = \frac{x^k}{(1-x)^{2k}}$. Explicitly, since

$$\frac{1}{(1-x)^{2k}} = \sum_{r \ge 0} {r + 2k - 1 \choose r} x^r,$$

we find that $f(n,k) = {n+k-1 \choose n-k}$.

Question: I'm at a loss why the first jump in the equality above holds. In particular, why do we start with

$$\sum_{n_1 +n_2 + \ldots + n_k = n} n_1 n_2 \cdot \ldots \cdot n_k \\ = [x^n] \left(\sum_r rx^r \right)^k$$

as above? I think I understand this is saying that $f(n,k)$ is the $nth$ term of the power series expansion of $\left(\sum_r rx^r\right)^k$. Why are we raising $\sum_r rx^r$ to the $k$th power? What fundamentally is going on here?

For the first step

Every $n_i$ can have a value $1,2,..$ so the generating function for this $n_i$ is $\sum_r rx^r$. So look at $$(\sum_r rx^r)^k$$If you look to the coefficient of $x^n$ then you have $n_1+...+n_k=n$ because of the exponents and as coefficients it has $$\sum_{n_1+...n_k=n}n_1\cdot...\cdot n_k$$ I hope this makes it understandable.

• By "if you look at the coefficient of $x^n$" do you mean looking at the coefficient of $x^{rk}$, i.e., looking at $r^k$? If that's the case, I'm not sure I understand. – user1770201 Mar 8 '14 at 19:27
• That is not what I meant. $n$ is just a number. – Kaladin Mar 8 '14 at 19:29
• Example $(x+2x^2+3x^3+...)(x+2x^2+3x^3+....)$ then the coefficient in front of $x^5$ equals $(0+4+6+6+4+0)=((5\cdot 0)+(4\cdot 1)+(3\cdot 2)+(2\cdot 3)+(1\cdot 4)+(0\cdot 6)$ – Kaladin Mar 8 '14 at 19:35
• OK -- I think I see what you mean. It seems that that generating function just came out of nowhere though! – user1770201 Mar 8 '14 at 19:58
• I'm also confused by the notation used in the third step of the equality reasoning: do we have that $[x^n] \left \{ \frac{x}{(1-x)^2} \right \} = [x^n] \left ( \frac{x}{(1-x)^2} \right)$? If not, what are the set brackets here denoting? – user1770201 Mar 8 '14 at 19:59

$$\begin{array}{ll} \sum_{n\ge0}\left(\sum_{n_1+\cdots+n_k=n}n_1\cdots n_k\right) x^n & =\sum_{n\ge0}\sum_{n_1+\cdots+n_k=n} (n_1 x^{n_1})\cdots(n_k x^{n_k}) \\ & =\sum_{n_1\ge0}\cdots\sum_{n_k\ge0}(n_1x^{n_1})\cdots(n_k x^{n_k}) \\ & = \left(\sum_{n_1\ge0}n_1x^{n_1}\right)\cdots\left(\sum_{n_k\ge0}n_kx^{n_k}\right)\end{array}.$$

One more method you can look at this is, we know $$\frac{1}{1-x}=\sum_{x=0}^\infty x^n$$ So applying operator $xD$ where D is derivative w.r.t x on it, we have $$\frac{x}{(1-x)^2} = \sum_{x=0}^{\infty} n x^n$$ Now if raise both side to k, then we have $$\frac{x^k}{(1-x)^{2k}}= \sum_{n_1+n_2+\ldots+n_k=n}n_1n_2\ldots n_k$$ This is the generating function that was needed