2
$\begingroup$

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

$\endgroup$

1 Answer 1

1
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ I presume you've set $a_0=1$ here? Thank you. $\endgroup$ Mar 26, 2012 at 9:01
  • $\begingroup$ 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. $\endgroup$ Mar 26, 2012 at 12:56
  • $\begingroup$ @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. $\endgroup$ Mar 26, 2012 at 13:07
  • $\begingroup$ 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. $\endgroup$ Mar 26, 2012 at 13:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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