= Composition coefficients of power series
{title2=$[x^n]f(g(x))=\sum_{m=0}^nf_m[x^n]g(x)^m\quad(g(0)=0)$}
For <power series> $f(z)=\sum_{m\geq0}f_mz^m$ and $g(x)=\sum_{j\geq1}g_jx^j$, their <function composition> is well defined as a <formal power series>: the coefficient of $x^n$ receives contributions only from $m\leq n$, since $g$ has zero <constant term>. For $m\geq1$, expand the coefficient as
$$
[x^n]g(x)^m=\sum_{\substack{j_1+\cdots+j_m=n\\j_1,\ldots,j_m\geq1}}g_{j_1}\cdots g_{j_m}.
$$
The $m=0$ term is one for $n=0$ and zero otherwise. The first four coefficients of the <function composition> are therefore $f_0$, $f_1g_1$, $f_1g_2+f_2g_1^2$, and $f_1g_3+2f_2g_1g_2+f_3g_1^3$. For convergent <power series>, the same calculation holds wherever $g(x)$ lies inside the <radius of convergence> of $f$.
Back to article page
