# Euler transform without generating functions

Roughly speaking, if $$a_n$$ is the number of graphs with some property and $$b_n$$ is the number of multisets of graphs with the same property, then these numbers are related via a transform of integer sequences which is sometimes called Euler transform. In particular, if $$a_n$$ is the number of connected graphs with $$n$$ vertices then $$b_n$$ is the number of not necessarily connected graphs with $$n$$ vertices. Or, if $$a_n$$ is the number of trees then $$b_n$$ is the number of forests. Or, if $$a_n=1$$ is the number of totally disconnected graphs with $$n$$ vertices then $$b_n$$ is the number of partitions of $$n$$.

For the description of that transform, see MathWorld, starting from the words "The third type". It is also discussed in section 4.2 of Harary & Palmer's Graphical Enumeration, and the 2nd volume of Stanley's Enumerative combinatorics discusses many variations of the relation between sequences $$\{a_n\}$$ and $$\{b_n\}$$.

The explicit formula for this transform is (combining eqs. (7) and (8) from MathWorld and setting $$b_0=1$$): $$b_n = \frac{1}{n} \sum_{k=1}^n b_{n-k} \sum_{d|k} d \, a_d$$

It is usually proved using generating functions.

My question is: can this formula be explained with purely combinatorial reasoning, without using generating functions?

It is clear that (using the first example) there are $$a_k$$ connected graphs with $$k$$ vertices and $$b_{n-k}$$ graphs that make use of the rest of the vertices, so we sum their product over $$k$$ (similarly to the Catalan numbers recurrence $$C_{n+1} = \sum_{k=0}^{n} C_{k} C_{n-k}$$), and $$\frac{1}{n}\sum_d d\times$$ compensates overcounting; but how exactly this compensates overcounting?

• Formula (5) at MathWorld can be proved with combinatorial reasoning, but then it requires some algebraic manipulations to derive the formula that you quoted in the question. Commented Jul 28, 2022 at 21:02

I think I figured it out.

First let's discuss the Catalan number recurrence. To obtain the formula for $$C_{n+1}$$ counting the number of correct strings of $$n+1$$ pairs of parentheses, we highlight the last external parentheses pair in such string and consider the parentheses strings $$s_1$$ before that pair and $$s_2$$ inside it: $$s_1(s_2)$$. Any nonempty correct parentheses string can be uniquely decomposed into $$s_1$$ and $$s_2$$, and we can unambiguously restore $$s_1(s_2)$$ from any two (possibly empty) correct strings $$s_1$$ and $$s_2$$. Note that $$s_1$$ and $$s_2$$ are independent in the sense that no relation between them is required except for containing $$n$$ parentheses pairs in total. So we denote the number of parentheses pairs in $$s_2$$ as $$k$$, go through all possible values of $$k$$, and get the recurrence $$C_{n+1} = \sum_{k=0}^n C_kC_{n-k}$$.

Now regarding the multisets of graphs (or, more generally, multisets of nonisomorphic structures on $$n$$-sets). In a multiset, we can naturally group graphs by their number of vertices $$i$$ (and order these groups by size), and within graphs of the same number of vertices we can also group isomorphic graphs together and enumerate these groups somehow (introducing index $$j$$ for a given $$i$$; there are $$a_i$$ such groups, some of them possibly empty). Isomorphic graphs within each group can also be enumerated and ordered somehow.

Although the graphs are now ordered within any multiset, we cannot do what we did with parentheses strings and split the multiset into two independent parts (two multisets or maybe a multiset and a graph): even if we highlight, say, the last graph, or the last group of isomorphic graphs, or the last group of graphs with the same number of vertices, in any of these cases it would impose serious restrictions on the non-highlighted part. It spoils the independence of the parts and ruins the approach "count ways to construct each of the parts separately, multiply, and sum over the size of one part".

We'll do another way. In a nonempty multiset of graphs, pick one of the $$n$$ vertices. Set a rule that the whole graph containing that vertex is highlighted, together with graphs isomorphic to it coming after it (they are ordered, remember?). So we have split the multiset into two parts: the residual non-highlighted part, which is a (possibly empty) multiset of graphs, an the highlighted part, which is a block of some nonzero number of isomorphic graphs (on $$i$$ vertices, of $$j$$th kind). Denote the total number of vertices in the block as $$k$$.

For example, here we have a forest, in which the trees are ordered, and a vertex is picked, which determines the highlighted block of isomorphic trees starting from the one with the picked vertex and others to the right of it:

Note that we can unambiguously restore the original multiset from the residual multiset and the block, and it works for any residual multiset and any block, the only restriction is that the total number of vertices should be $$n$$. (Just like with Catalan numbers! However, now we need to learn how to count blocks.) On the other hand, any pair consisting of a residual multiset and a block of isomorphic graphs (with $$n$$ vertices total) can be obtained from some original $$n$$-vertex multiset in exactly $$i$$ ways (the number of vertices in a graph from the block). Therefore, if we go through all possible pairs of a multiset and a block with $$n$$ vertices total and count them with the weight $$i$$ (determined by the block), then we'll get exactly the number of ways to take an $$n$$-vertex multiset, order its vertices, and pick a vertex in it, which equals $$nb_n$$.

So for fixed $$k$$, $$i$$, and $$j$$, the block is determined unambiguously (although it only exists if $$i|k$$), while the residual multiset can be chosen in $$b_{n-k}$$ ways. Multiply by the weight factor $$i$$; sum over $$j$$ (since the summand does not depend on $$j$$, this only adds the factor $$a_i$$); sum over the allowed values of $$i$$ (i. e. the divisors of $$k$$; $$b_{n-k}$$ factors out of this sum); finally, sum over $$k$$ and divide by $$n$$ to get $$b_n$$. After replacement $$i\to d$$ we get the desired formula from the question.

• The same idea applied to the particular case of rooted unlabeled trees, i. e. $b_n = a_{n+1}$: mathoverflow.net/questions/409418/… Thanks to O. Kulkov for bringing that to my attention. Commented Nov 6, 2022 at 0:07