Series of iterates of a power series

Solution 1:

I've done one example.
Consider the function $f(x)=2 x^2-x^3+1/4 x^4 $ The top left segment of the Carlemanmatrix, let's call it $F$ is $$ F_{8 \times 8}=\small \begin{bmatrix} 1 & . & . & . & . & . & . & . \\ 0 & 0 & . & . & . & . & . & . \\ 0 & 2 & 0 & . & . & . & . & . \\ 0 & -1 & 0 & 0 & . & . & . & . \\ 0 & 1/4 & 4 & 0 & 0 & . & . & . \\ 0 & 0 & -4 & 0 & 0 & 0 & . & . \\ 0 & 0 & 2 & 8 & 0 & 0 & 0 & . \\ 0 & 0 & -1/2 & -12 & 0 & 0 & 0 & 0 \end{bmatrix} $$ such that the coefficients for $f(x)$ are in the second column (let's define the columnindex $c=1$ and rows and column-indexes always begin at 0) In the next column there are the coefficients for $f(x)^2$ and in the first column that (trivial one) for $f(x)^0 = 1$. (Note: my convention here is the transpose of the example in the wikipedia for some historical reasons)

The coefficients for the h'th iterate of $f(x)$ occur in the second column of the h'th power of $F$.

Then the coefficients for the sum of all iterates occur in the second column of the sum of all powers of $F$. But that means, that we could define the matrix $A$ as result of the geometric series of $F$, which is known as Neumann series and would be computed by $$ \sum_{k=0}^\infty F^k = (I - F)^{-1} $$

Unfortunately, the top left element of that geometric series $(I-F)$ is zero, so it is not invertible. But for any finite truncation we can use the submatrix without the first column and row and then this is invertible: $$ A = ((I - F)^*)^{-1} $$ The top left segment of $A$ is then $$ A=\small \begin{bmatrix} 1 & . & . & . & . & . & . & . \\ 2 & 1 & . & . & . & . & . & . \\ -1 & 0 & 1 & . & . & . & . & . \\ 33/4 & 4 & 0 & 1 & . & . & . & . \\ -8 & -4 & 0 & 0 & 1 & . & . & . \\ -4 & 2 & 8 & 0 & 0 & 1 & . & . \\ 11 & -1/2 & -12 & 0 & 0 & 0 & 1 & . \\ 985/8 & 1025/16 & 9 & 16 & 0 & 0 & 0 & 1 \end{bmatrix} $$ The coefficients in the first column in $A$ allow now to compute the sum of any contiguous segment of the iterates of $f°^h(x)$ just by the function $$g(x_0,x_m) = \sum_{h=0}^{m-1} f°^h(x_0) = \sum_{k=1}^\infty (x_0^k-x_m^k) \cdot A_{k-1,0} $$ where $x_m = f°^m(x_0)$

This is a pretty general scheme and the current example is just to get an intuition. For other polynomials and even power series $f(x)$ one might need some finetuning and exceptions, but I think it is pretty obvious what's going on in general.

[update] I should add, that the current example gives a pretty small range of convergence, and perhaps one should take a better one. We can only use such $x_0$ , where $|f(x_0)|<|x_0|$, and I tried with $x=0.01$ and smaller... [/update]

Solution 2:

If $f(z),g(z)$ are the generating functions for combinatorial classes $\mathcal{F},\mathcal{G}$, then the composition $f(g(z))$ is the generating function for the class of objects of $\mathcal{F}$ whose atoms have been replaced with elements of $\mathcal{G}$.

So, for example, if $f(z)=z^2(1-z)^{-1}$ is considered to be the g.f. for rooted trees of depth 1 with at least two leaf nodes, then $f^{\circ n}$ is the g.f. for balanced trees of depth $n$ in which each internal node has at least two child nodes, and $S$ is the g.f. for all such balanced trees, satisfying $S(z) = z + S(f(z))$.