MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
up vote 1 down vote accepted

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

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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