Question

I expect that this question is an elementary exercise in combinatorics, so hopefully somebody who knows more than me can explain.

Specifically, if $m\in\mathbb{N}$ and $$f(x)=\sum_{n=1}^{\infty}a_nx^n,$$ one obviously has $$f^m(x)=\sum_{n=m}^{\infty}\left(\sum_{k_1+k_2+\cdots + k_m=n}a_{k_1}a_{k_2}\cdots a_{k_m}\right)x^n.$$

The number of distinct products appearing in the iterated convolution is the integer partition number $p(n-m)$ so, writing the inner sum as

(1) $$\sum_{j_1+2j_2+\cdots + mj_m=n}s_{n}(j_1,j_2,...,j_m)a^{j_1}_1a^{j_2}_2\cdots a^{j_m}_m,$$ the questions arise:

What is the coefficient sequence of integers $s_{n}(j_1,j_2,...,j_m)$, explicitly?

What is its combinatorial significance?

EDIT: The fact that the number of terms in the sum is $p(n-m)$ is perhaps not so obvious, but you can reason as follows: note that the largest subscript that can appear in the coefficient of $x^n$ is $n-m+1$, because $n-m+1+(m-1)\times 1=n$. This restricts you to having only those partitions of $n$ whose largest part is $m-n+1$, that is, the set of solutions to the diophantine equation

(2)$$ j_1+2j_2+\cdots +(n-m+1)j_{n-m+1}=n.$$ On the other hand, since there are a total of $m$ coefficients in each product (counting repetitions), you know that

(3)$$j_1+j_2+\cdots +j_{n-m+1}=m.$$ Thus, subtracting (2) from (1), you get $$j_2+2j_3+\cdots +(n-m)j_{n-m+1}=n-m,$$ the number of distinct solutions to which is the partition number $p(n-m)$. I am trying to think of a better notation for the summation in (1), as I think it is definitely misleading.

EDIT: I should've indexed everything by $+1$ so that (1) becomes $$\sum_{j_1+2j_2+\cdots +(n-m)j_{n-m}=n-m}s(j_1,j_2,...,j_{n-m})a_1^{m-(j_1+\cdots +j_{n-m})}a_2^{j_1}\cdots a_{n-m+1}^{j_{n-m}}.$$

Answer 1

Let $j_1 + 2j_2 + \cdots + nj_n = n$. The coefficient of $a_1^{j_1} a_2^{j_2} \ldots a_n^{j_n} x^n$ in $ \Bigl( \sum_{n=1}^\infty a_n x^n \Bigr)^m $ is equal to the multinomial coefficient

$$ \binom{m}{j_1,j_2,\ldots,j_n} $$

since when we multiply out $\Bigl( \sum_{n=1}^\infty a_n x^n \Bigr) \ldots \Bigl( \sum_{n=1}^\infty a_n x^n \Bigr) $ we must take $a_ix^{i}$ from exactly $j_i$ of the terms. So the coefficient is $\frac{m!}{j_1! j_2! \ldots j_n!} $ provided $j_1 + \cdots + j_n = m$ and $0$ otherwise.

(There are some problems with the $s$ notation in the question. I think $s_n(j_1,\ldots,j_m)$ should be $s_m(j_1,\ldots,j_n)$, since it is possible for $a_rx^r$ to contribute to the coefficient of $x^n$ in $f(x)^m$ for $r > m$. Later it is noted that the highest $r$ that can appear is $n-m+1$, but the shifted definition then defines a different family of numbers.)