# What are the coefficients when you write iterated additive convolutions as sums over integer partitions?

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}}.$$

-

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.)

-
I presume you've set $a_0=1$ here? Thank you. –  Kevin Smith Mar 26 '12 at 9:01
Mark, there is an issue with this - you are absolutely right about the appearance of the multinomial coefficient and the $s$ notation, yet I think there are in fact $n+1$ factors in the denominator. Assuming that $a_0=1$, the coefficient of $a_1^{j_1}\cdots a_{n}^{j_n}$ in \left(\sum_{0}^{\infty}a_nx^n\right)^m would then be $${{m}\choose{m-j_1-\cdots-j_n,j_1,...,j_n}},$$ where $j_1+j_2+\cdots +j_n<m$. I obtained this directly from the definition of the multinomial expansion. –  Kevin Smith Mar 26 '12 at 12:56
@Kevin: starting the sum from zero was a typo which I've now corrected. I think you will find everything works if we start from n=1. I agree the formula in your comment is correct if we set a_0 = 1. –  Mark Wildon Mar 26 '12 at 13:07
Ah, I see whats going on here - your $j_i$s are all zero for $i>n-m+1$, so the definitions are equivalent. Sorted. –  Kevin Smith Mar 26 '12 at 13:53