Combinatorial interpretation of the power of a series

Question

I am trying to understand a result involving the power of a series that occurs in Gradstein and Ryzhik's Table of Integrals, Series, and Products. Result 0.314 (p.17, 7th ed.) is:

$$\left(\sum_{k=0}^\infty a_k x^k\right)^n=\sum_{k=0}^\infty c_k x^k$$

where $$c_0 = a_0^n, c_m=\frac 1 {ma_0} \sum_{k=1}^m (kn-m+k) a_k c_{m-k}$$ for $m\ge1$ and $n\in\mathbb N$.

What is an appropriate combinatorial interpretation of this result?

---

One way I am trying to understand it is to see how it arises from the multinomial expansion

$$ \left(\sum_{k=0}^\infty b_k \right)^n = \sum_{\kappa\vdash k} \binom k \kappa b^\kappa $$

which has the usual nice combinatorial interpretation of how to put objects in bins. This is suggested in the reference given in Gradstein and Ryzhik, which is an even older book: Smithsonian mathematical formulae and tables of elliptic functions, p.118. However, the additional structure provided by regrouping powers of $x$ after substituting $b_k = a_k x^k$ must surely have some significant, nontrivial and well-known combinatorial implications that I am simply unaware of. (I hope this is clear; the multiindex notation is new to me and I don't know a nice way to write the result of this last step.)

Answer 1

Ralph gave a nice proof but I don't think it counts as a combinatorial interpretation. However, we can work directly with his rearrangement (1). If $a_k$ is the number of "objects" of "size" $k$, then $c_k$ is the number of vectors of $n$ objects with total size $k$. (This is the standard interpretation of the power of an ordinary generating function.)

Now consider an object of size $k$ to be a sack of $k$ distinguishable "atoms". Let $N$ be the number of $(n+1)$-tuples of objects, of total size $m$, with one atom (out of the $m$ atoms altogether) distinguished.

We can start with one object, say of size $k$, append $n$ more objects of total size $c_{m-k}$ to make the total size up to $m$, then distinguish one of the $m$ atoms. So $N$ is the left side of (1).

Alternatively, start with one object, say of size $k$, distinguish one of its atoms, then extend this in either or both directions in $(n+1)c_{m-k}$ ways to make $n+1$ objects of total size $m$. (The factor of $n+1$ is the number of positions that the originally chosen object might end up in.) So $N$ is the right size of (1).

Answer 2

I don't know if this counts as a combinatorial interpretation, but the identity can be seen as follows: Firstly it's equivalent to $$m\sum_{k=0}^m a_k c_{m-k} = (n+1)\sum_{k=0}^mka_kc_{m-k}\hspace{40pt}(1)$$ If we write $f(x) = \sum_{k=0}^\infty a_kx^k$ then the LHS resp. RHS of $(1)$ is just the $(m-1)$-th coefficient of the LHS resp. RHS of $$(f^{n+1})'=(n+1)f^nf'.\hspace{50pt}$$

Answer 3

A train is composed putting in series $n$ carriages. Carriages of size $k=0,1,\dots$ (number of places) are available in $a_k$ different colors. So, there are $c_k$ possible trains of $n$ carriages and $k$ places.

Now suppose a further carriage is attached, reaching an amount of $m$ places. Clearly, there are $n$ times as many ways of having your seat in the old $n$ carriages of such trains than in the new one (just imagine to switch the new carriage with one of the $n$ old ones), and this is your identity, written
$$n\sum_{k=0}^m ka_k c_{m-k}=\sum_{k=0}^m kc_k a_{m-k}\, .$$

(and, of course, this is the identity $n\alpha'\alpha^n=\alpha(\alpha^n)'$ between g.f.'s)

Note that one may state this in a probability language in terms of an independence property, coming from a symmetry argument.

Answer 4

Nice question! You are looking for a combinatorial interpretation of nth-fold self-convolution of a sequence. A quick google serach gave me this result on Catalan sequence. In this paper, a similar result is worked out on a series with Catalan coefficients. May be you can use similar idea for generic sequences.