4
$\begingroup$

There are well-known formulas for the coefficients resulting from multiplying two formal polynomials or generating functions (we define formal polynomial to be a generating function such that all coefficients of sufficiently high index are zero). Adding is even easier, as it is component-wise.

Question: What is the neatest formula for the coefficients of the composition $f\circ g$ where $f,g$ are formal polynomials or generating functions?

I tried approaching it by writing $(f\circ g)(x) = f(g(x))$ and substituting the expression for $g$ into the expression for $f$. Even with summation notation, the expansion just devolved into an mess involving the multinomial theorem that seems difficult to simplify. I am hopeful that combinatorial identities or other techniques such as exchanging the order of the summations will yield a somewhat satisfactory formula. I'll settle for pretty much any non-trivial simplification.

$\endgroup$
4
  • 1
    $\begingroup$ I don't know of any "nice" formula for the coefficients of the composite of two generating functions. In the case of exponential generating functions, we can relate composition to an operation on species (see the "composition" section of the linked wikipedia article), but in general I don't know of any results. A quick google brings up a paper of Kruchinin Composition of Ordinary Generating Functions, but I haven't read it so I'm not sure how neat a result it is. $\endgroup$ Feb 1, 2023 at 3:52
  • 2
    $\begingroup$ It's called Faa di Bruno's formula and yes, it is terrible (en.wikipedia.org/wiki/Fa%C3%A0_di_Bruno%27s_formula). It's better not to think about these things directly but conceptually in terms of operations on combinatorial species as HallaSurvivor says. $\endgroup$ Feb 1, 2023 at 4:33
  • $\begingroup$ What I am doing is to express composition of functions $f(x)$ and $g(x)$ (having a power series) as matrix-multiplication $F \cdot G$ after each function has a "Carleman"-matrix $F$ resp $G$ assigned. The evolution of coefficients in the matrix-operation is now schematic, but is of course nothing else than the explicite coefficients by the Faa di Bruno - formula. But working with it seems to be more transparent to me ... but it is too much to explain this (and its limits and so on ... ) in a comment. $\endgroup$ Feb 21, 2023 at 17:07
  • $\begingroup$ Perhaps an interesting introductory discussion might be in go.helms-net.de/math/tetdocs/ContinuousfunctionalIteration.pdf while the main focus is not function-composition but iteration. But well, perhaps useful anyway... $\endgroup$ Feb 21, 2023 at 17:41

1 Answer 1

4
$\begingroup$

for OGF, let $[x^i] f(x) = f_i$ and $[x^j] g(x) = g_j$. Then you can rewrite the composition as $$ [x^k]f(g(x)) = \sum\limits_i f_i [x^k] g^i(x) = \boxed{\sum\limits_i f_i \sum\limits_{j_1 + \dots + j_i = k} g_{j_1} \dots g_{j_i}} $$

For EGF, let $\left[\frac{x^i}{i!}\right] f(x) = f_i$ and $\left[\frac{x^j}{j!}\right] g(x) = g_j$, then $$ \left[\frac{x^k}{k!}\right] f(g(x)) = \sum\limits_i \frac{f_i}{i!} \left[\frac{x^k}{k!}\right] g^i(x) = \boxed{\sum\limits_i \frac{f_i}{i!} \sum\limits_{j_1+\dots+j_i=k} \binom{k}{j_1,\dots,j_i} g_{j_1} \dots g_{j_i}} $$ I think it doesn't really get prettier than that, and it's indeed better to interpret combinatorially. Informally, if $f(x)$ is the genfunc of species $A$, and $g(x)$ is the genfunc of species $B$, then $f(g(x))$ is the genfunc of species obtained by taking instances of species $A$ and replacing their "atoms" by instances of species $B$.

For example, if $A$ is species of "sets" and $B$ is species of "cycles", then $f(g(x))$ is the genfunc for the species of "sets of cycles", aka "permutations". The meaning of the composition formula for EGFs is then interpreted as "take an instance of $A$ on $i$ atoms, and replace its atoms with instances of $B$ with total of $k$ atoms across them". Then the multinomial coefficient accounts for the number of ways to distribute $k$ new atoms between $i$ instances of species $B$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .