Finding EGF of $c(n,k)$: How did my professor manipulate $(\sum_{n \geq1} \frac{x^n}{n})^k$ into this nested summation?

Question

I am trying to understand how to find the exponential generating function for the number of permutations of $[n]$ having exactly k disjoint cycles, $c(n,k)$. We have defined $A(x)$ as the exponential generating function of number of cycles of size $n$. Then, we have found that $A(x) = \sum_{n \geq1} \frac{x^n}{n}$.

Then we did the following manipulation:

$\sum_{n \geq 0} c(n,k) \frac{x^n}{n!} = \frac{A(x)^k}{k!} = \frac{1}{k!} \left( \sum_{n \geq 1} \frac{x^n}{n} \right)^k$

I have no problem with these steps, however, I do not understand how we did the following manipulation:

$(\sum_{n \geq1} \frac{x^n}{n})^k = \sum_{n \geq k} \left( \sum_{\substack{r_1, r_2, \ldots, r_k \\ r_i \geq 1 \\ \sum r_i = n}} \frac{1}{r_1 r_2 \ldots r_k} \right) \frac{n!}{n!} x^n$

I would greatly appreciate any help!

Answer 1

It might be helpful to take a closer look at the case $k=2$. The general case should follow rather easily.

We obtain \begin{align*} \color{blue}{\left(\sum_{n\geq 1}\frac{x^n}{n!}\right)^2} &=\left(\sum_{r_1\geq 1}\frac{x^{r_1}}{{r_1}!}\right)\left(\sum_{r_2\geq 1}\frac{x^{r_2}}{{r_2}!}\right)\\ &=\sum_{n=2}^{\infty}\left(\sum_{{r_1+r_2=n}\atop{r_1,r_2\geq 1}}\frac{x^{r_1}}{r_1!}\,\frac{x^{r_2}}{r_2!}\right)\tag{1}\\ &=\sum_{n=2}^{\infty}\left(\sum_{{r_1+r_2=n}\atop{r_1,r_2\geq 1}}\frac{1}{r_1!r_2!}\right)x^n\tag{2}\\ &\,\,\color{blue}{=\sum_{n=2}^{\infty}\left(\sum_{{r_1+r_2=n}\atop{r_1,r_2\geq 1}}\frac{n!}{r_1!r_2!}\right)\frac{x^n}{n!}}\tag{3}\\ \end{align*}

and we derive from (3) for general $k$: \begin{align*} \left(\sum_{n\geq 1}\frac{x^n}{n!}\right)^k =\sum_{n\geq k}\left(\sum_{{r_1+r_2+\cdots+r_k=n}\atop{r_1,\ldots,r_k\geq 1}}\frac{n!}{r_1!r_2!\cdots r_k!}\right)\frac{x^n}{n!} \end{align*}

Comment:

• In (1) we apply the Cauchy product of series, which means sorting the entries according to increasing $n$. Note the series starts with $n=2$ since $r_1, r_2\geq 1$.

• In (2) we use $r_1+r_2=n$ and factor out $x^n$.

• In (3) we multiply with $\frac{n!}{n!}=1$ to obtain a representation as EGF.