Let $f=\sum\limits_{n\geq 0}{f_n x^n}$ and $g=\sum\limits_{n\geq 1}{g_n x^n}$ be formal power series. The $x^n$ coefficient of $f(g)$ is $$ \sum\limits_{\mathbb{i} \in \mathcal{C}_{n}} {f_k \,g_{i_1}\cdots g_{i_k}} , $$ where $\mathcal{C}_{n} = \{ (i_1, \ldots, i_k) : 1 \leq k \leq n, i_1 + \cdots + i_k = n \}$ is the set of compositions of $n$ into $k$ parts.

Consider the power series $h=\sum\limits_{n\geq 0}{h_n x^n}$ with coefficient

$$ h_n = \sum\limits_{\mathbb{i} \in \mathcal{C}_{n}} {\binom{n}{k} f_k \,g_{i_1}\cdots g_{i_k}} . $$ Is there a "nice" way to express $h$ in terms of $f$ and $g$ or related generating series (eg. their e.g.f.s), where by "nice", I mean a formula that can be evaluated if $f$ and $g$ are at least rational functions with $g(0)=0$?


If we let $F=\sum\limits_{n\geq 0}{f_n \frac{x^n}{n!}}$ and $H=\sum\limits_{n\geq 0}{h_n \frac{x^n}{n!}}$ then, using the inverse Laplace transform $\mathcal{L}^{-1}$, we can write

$$H = \mathcal{L}^{-1}\{ F(s \,g(x/s))/s\}(1).$$

This is because $$\mathcal{L}^{-1}\{ s^{k-n}/s\}(1)=\frac{1}{(n-k)!}.$$

However this isn't what I want because

  1. I want $h$, not $H$, and;

  2. this formula is not "nice", as if $f=\frac{1}{1-x}$ (so $F=e^x$) and $g=\frac{x}{1-x}$, the expression for $H$ is an intractable integral, whereas $h=\frac{1}{2} + \frac{1}{2\sqrt{1-4x}}$.

  • 1
    $\begingroup$ It's not exactly what you want, but if you let $G = \sum b_n \frac{x^n}{n!}$ and $D(x) = f(G) = \sum d_n \frac{x^n}{n!}$, then you have $$ d_n = \sum\limits_{i \in \mathcal{C}_n}\binom{n}{i_1,i_2,\ldots,i_k}a_k b_{i_1}\cdots b_{i_k}. $$ $\endgroup$ – Marcus M Jun 19 '15 at 2:28
  • $\begingroup$ Thanks for the idea, but unfortunately this doesn't help me! Also I'm sorry that I changed notation in my question to make things clearer. $\endgroup$ – Nasos Evangelou-Oost Jun 21 '15 at 9:32
  • $\begingroup$ The $x^n$ coefficient of $f\circ g$ should be $\sum_{k=1}^nf_k\sum_{i\in C_{n,k}}g_{i_1}...g_{i_k}$, shouldn't it? If not, what does the $k$ refer to in your first formula ? I would also ask the same question about the $h_n$ you want to know, is there a sum over $k$ ? $\endgroup$ – Clément Guérin Jun 24 '15 at 7:53
  • $\begingroup$ @ClémentGuérin: Yes the sum is over $k$ in both cases--I think we can omit the summation sign as long as we write $\mathbb{i} \in \mathcal{C}_{n}$ instead of $\mathbb{i} \in \mathcal{C}_{n,k}$. $\endgroup$ – Nasos Evangelou-Oost Jun 24 '15 at 10:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.