Is there a conceptual derivation of the formula for the composition of two EGFs?

23 Views Asked by At

Exponential generating functions (EGFs) can be used to represent different classes of connected undirected graphs. Composition of EGFs has the following interpretation.

If $F(x)$ represents graphs of type I and $G(x)$ represents graphs of type II, then $F(G(x))$ represents the graphs that can be constructed by first constructing a graph of type I and then replacing each of its vertices with a graph of type II.

It is straightforward to prove this in terms of a formula. Let $F(x) = \sum_{n \geq 0} \frac{f_n}{n!} x^n$ and $G(x) = \sum_{n \geq 1} \frac{g_n}{n!} x^n$. Then

$$F(G(x)) = \sum_{n \geq 0}\frac{1}{n!}\left(\sum_{k \leq n} \frac{f_k}{k!} \sum_{\begin{matrix}n_1, \ldots, n_k \,\geq\, 1\\n_1 + \cdots + n_k \,=\, n\end{matrix}} \binom{n}{n_1, \ldots, n_k} g_{n_1} \cdots g_{n_k}\right) x^n \tag{1}\label{a}$$

Moreover, after studying the formula for a moment, one observes that it expresses the interpretation of $F(G(x))$ mentioned above.

Is there is there a conceptual proof that does this in reverse? That is, can we prove that $F(G(x))$ has the boxed interpretation above without deriving the formula first algebraically? If so, then the formula \ref{a} for $F(G(x))$ would be immediate and hopefully such an argument would also provide some intuition into why the composition of two EGFs has such a nice interpretation.


Here is a straightforward but unenlightening derivation of the formula for \ref{a}. We start by considering two ordinary generating functions (OGFs) $A(x) = \sum_{n \geq 0} a_n x^n$ and $B(x) = \sum_{n \geq 1} b_n x^n$. Then

$$(B(x))^k = \sum_{n \geq k} \sum_{\begin{matrix}n_1, \ldots, n_k \,\geq\, 1\\n_1 + \cdots + n_k \,=\, n\end{matrix}} b_{n_1} \cdots b_{n_k} x^n$$

Therefore,

\begin{align} A(B(x)) & = \sum_{k \geq 0} a_k \sum_{n \geq k} \sum_{\begin{matrix}n_1, \ldots, n_k \,\geq\, 1\\n_1 + \cdots + n_k \,=\, n\end{matrix}} b_{n_1} \cdots b_{n_k} x^n \\ {} & = \sum_{k, n \geq 0} \;\; [n \geq k] \; a_k \sum_{\begin{matrix}n_1, \ldots, n_k \,\geq\, 1\\n_1 + \cdots + n_k \,=\, n\end{matrix}} b_{n_1} \cdots b_{n_k} x^n \\ {} & = \sum_{n \geq 0}\left(\sum_{k \leq n} a_k \sum_{\begin{matrix}n_1, \ldots, n_k \,\geq\, 1\\n_1 + \cdots + n_k \,=\, n\end{matrix}} b_{n_1} \cdots b_{n_k} \right) x^n \label{b} \tag{2} \end{align}

Now, consider the EGFs $F(x) = \sum_{n \geq 0} \frac{f_n}{n!} x^n$ and $G(x) = \sum_{n \geq 1} \frac{g_n}{n!} x^n$. Then by applying \ref{b}, we see that

\begin{align} F(G(x)) & = \sum_{n \geq 0}\left(\sum_{k \leq n} \frac{f_k}{k!} \sum_{\begin{matrix}n_1, \ldots, n_k \,\geq\, 1\\n_1 + \cdots + n_k \,=\, n\end{matrix}} \frac{g_{n_1}}{n_1!} \cdots \frac{g_{n_k}}{n_k!}\right) x^n\\ {} & = \sum_{n \geq 0}\frac{1}{n!}\left(\sum_{k \leq n} \frac{f_k}{k!} \sum_{\begin{matrix}n_1, \ldots, n_k \,\geq\, 1\\n_1 + \cdots + n_k \,=\, n\end{matrix}} \binom{n}{n_1, \ldots, n_k} g_{n_1} \cdots g_{n_k}\right) x^n \end{align}

which is precisely the formula \ref{a}.