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.

  • $\begingroup$ 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. $\endgroup$ – user1770201 Mar 8 '14 at 19:27
  • $\begingroup$ That is not what I meant. $n$ is just a number. $\endgroup$ – Kaladin Mar 8 '14 at 19:29
  • $\begingroup$ 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)$ $\endgroup$ – Kaladin Mar 8 '14 at 19:35
  • $\begingroup$ OK -- I think I see what you mean. It seems that that generating function just came out of nowhere though! $\endgroup$ – user1770201 Mar 8 '14 at 19:58
  • $\begingroup$ 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? $\endgroup$ – 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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.