# The Euler characteristic of the moduli space of graphs

Michael Borinsky and Karen Vogtmann  Michael Borinsky
Institute for Theoretical Studies
ETH Zürich
8092 Zürich, Switzerland  Karen Vogtmann
Mathematics Institute
University of Warwick
Coventry CV4 7AL, United Kingdom

###### Abstract.

The moduli space of rank $n$ graphs, the outer automorphism group of the free
group of rank $n$ and Kontsevich’s Lie graph complex have the same rational
cohomology. We show that the associated Euler characteristic grows like
$-e^{-1/4}\,(n/e)^{n}/(n\log n)^{2}$ as $n$ goes to infinity, and thereby
prove that the total dimension of this cohomology grows rapidly with $n$.

##  1\. Introduction

The moduli space $\mathcal{MG}_{n}$ of finite metric graphs with fundamental
group $F_{n}$ was introduced in [17] as a tool for studying the group
${\operatorname{Out}}(F_{n})$ of outer automorphisms of a free group. By the
main result in that paper $\mathcal{MG}_{n}$ is the quotient of a contractible
space, called Outer space, on which ${\operatorname{Out}}(F_{n})$ acts with
finite stabilizers. Thus the homology of ${\operatorname{Out}}(F_{n})$ with
trivial rational coefficients is equal to the homology of $\mathcal{MG}_{n}$.

Kontsevich showed in [22, 23] that the homology of $\mathcal{MG}_{n}$ can also
be identified with the cohomology of his Lie graph complex, which can in turn
be identified with the primitive part of the cohomology of the Lie algebra of
symplectic derivations of a free Lie algebra (see [15] for a detailed
exposition of Kontsevich’s results). In [5] Berglund and Madsen found this Lie
algebra in a very different context, and proved that its cohomology is a sub-
algebra of the cohomology of the block diffeomorphism group of even-
dimensional products of spheres. In more recent years, algebraic geometers
have studied $\mathcal{MG}_{n}$ as a _tropical analog_ of the classical moduli
space $\mathcal{M}_{n}$ of smooth complex curves of genus $n$. The simplicial
completion of Outer space descends to a natural compactification of
$\mathcal{MG}_{n}$, which the tropical geometers have dubbed the _moduli space
of tropical curves,_ by analogy with the Deligne-Mumford compactification of
$\mathcal{M}_{n}$ (see, e.g., [13]). In yet another context,
$\mathcal{MG}_{n}$ may be considered a natural parameter space for the
$n$-loop contribution to certain Feynman amplitudes. This direction has been
explored, for example, by Bloch, Berghoff and Kreimer [6, 4].

In this paper we prove a formula for the Euler characteristic of
$\mathcal{MG}_{n}$, and then determine its asymptotic growth rate. The
asymptotic result depends on our results in [10], where we determined the
asymptotic growth rate of the rational or virtual Euler characteristic
$\chi({\operatorname{Out}}(F_{n}))$. This is a rational number closely related
to the alternating sum of the Betti numbers, but which has better group-
theoretic properties, making it easier to compute. The rational Euler
characteristic of ${\operatorname{Out}}(F_{n})$ coincides with the number
Kontsevich referred to as the orbifold Euler characteristic of his Lie graph
complex. The actual alternating sum of the Betti numbers is denoted
$e({\operatorname{Out}}(F_{n}))$ in this paper to distinguish it from
$\chi({\operatorname{Out}}(F_{n}))$, and is called the integral Euler
characteristic to conform with other terminology in the literature.

If we are primarily interested in the cohomology of the space
$\mathcal{MG}_{n}$ or (equivalently) the group ${\operatorname{Out}}(F_{n})$,
then the number $e({\operatorname{Out}}(F_{n}))$ is clearly more relevant.
Brown [12] showed that the rational and integral Euler characteristics of a
group $\Gamma$ are closely related, namely $e(\Gamma)$ can be calculated from
the rational Euler characteristics of centralizers of finite-order elements by
the formula

$e(\Gamma)=\sum_{[\alpha]}\chi(C(\alpha)).$

Here the sum is over representatives $\alpha$ for the conjugacy classes of
finite-order elements (including the identity), and $C(\alpha)$ is the
centralizer of $\alpha$.

The number $e({\operatorname{Out}}(F_{n}))$ was calculated for $n\leq 11$ by
Morita, Sakasai and Suzuki [25], using methods from symplectic representation
theory. In the present paper we use Brown’s formula, results on centralizers
from [24], an adaptation of Joyal’s theory of species [20] and further
development of the asymptotic methods of [10] to first give an effective
formula for $e({\operatorname{Out}}(F_{n}))$ and then to determine its
asymptotic growth rate.

The effective formula is developed in Sections 2-3 and summarized in Theorem
3.13. Based on it, we wrote a computer program to compute
$e({\operatorname{Out}}(F_{n}))$ for $n\leq 15$. The results are listed in
Appendix A. Further optimizations of this program enabled the computation of
the numbers $e({\operatorname{Out}}(F_{n}))$ for all $n\leq 100$ [9].

Section 4 is devoted to proving the following asymptotic result.

######  Theorem 1.1.

The integral Euler characteristic $e({\operatorname{Out}}(F_{n}))$ has the
asymptotic behavior

$\displaystyle
e({\operatorname{Out}}(F_{n}))\sim-{e^{-\frac{1}{4}}}\left(\frac{n}{e}\right)^{n}\frac{1}{(n\log
n)^{2}}\text{ as }n\rightarrow\infty.$

Here the notation $a_{n}\sim b_{n}$ means that
$\lim_{n\rightarrow\infty}a_{n}/b_{n}=1$. In particular this verifies the
fact, suggested by our results on the rational Euler characteristic in [10],
that there is a huge amount of cohomology in odd dimensions. Since the
cohomology of ${\operatorname{Out}}(F_{n})$ is a direct summand of the
cohomology of ${\operatorname{Aut}}(F_{n})$, we reach the same conclusion for
${\operatorname{Aut}}(F_{n})$. The cohomology
$H^{k}({\operatorname{Out}}(F_{n});{\mathbb{Q}})$ is known to vanish for both
$k<4n/5$ and $k>2n-3$ (see [14] and the references there), thus all of this
cohomology must be concentrated in dimensions $4n/5\leq k\leq 2n-3$. The only
odd-dimensional class known to date occurs in
$H_{11}({\operatorname{Out}}(F_{7}))$ [2]. It is interesting to note that this
is the largest possible dimension, the virtual cohomological dimension of
${\operatorname{Out}}(F_{7})$. This is in contrast to the fact that the groups
${\operatorname{GL}}_{n}({\mathbb{Z}})$ and mapping class groups of punctured
surfaces, both of which are often considered analogs of
${\operatorname{Out}}(F_{n})$, have no rational cohomology in their virtual
cohomological dimension.

Comparing Theorem 1.1 with our results in [10] on
$\chi({\operatorname{Out}}(F_{n}))$ gives

######  Corollary 1.2.

The ratio
$\lim_{n\rightarrow\infty}e({\operatorname{Out}}(F_{n}))/\chi({\operatorname{Out}}(F_{n}))=e^{-\frac{1}{4}}\approx
0.78.$

###### Proof.

Use Theorem 1.1, [10, Thm. A] and Stirling’s formula (see, e.g., [1, Eq.
(3.9)]). ∎

This solves Problem 6.5 of the paper [25] by Morita, Sakasai and Suzuki. More
precise asymptotic statements and comments about the rate of convergence are
given in Section 4.2.

In his original paper [22] Kontsevich introduced commutative and associative
graph complexes in addition to the Lie graph complex. The methods of the
present paper can be modified to compute the Euler characteristics for both of
these other graph complexes as well as to determine their asymptotic behavior
(see [8]); they can also be used to do the same for other moduli spaces of
graphs, such as colored graphs or graphs with leaves. As Kontsevich noted, the
associative graph complex computes the homology of mapping class groups of
punctured surfaces. Both the rational and integral Euler characteristics of
these groups for a once-punctured surface were originally computed by Harer
and Zagier [19]. They also computed the asymptotics and deduced the existence
of lots of cohomology. Getzler and Kapranov partially extended this to
surfaces with more than one puncture (without determining the asymptotics) as
an application of their general theory of modular operads [18], and we remark
that our method of finding the generating function is similar to theirs.

In [22] Kontsevich also defined odd versions of his graph complexes, and noted
that in the Lie case the primitive part of the homology computes the
cohomology of ${\operatorname{Out}}(F_{n})$ with twisted coefficients
$\widetilde{\mathbb{Q}}$, where the twisting is given by composing the natural
map from ${\operatorname{Out}}(F_{n})$ to
${\operatorname{GL}}_{n}({\mathbb{Z}})$ with the determinant map. This odd
version of Lie graph homology occurs, for example, in the study of groups of
homotopy equivalences of odd-dimensional products of spheres [27]. In a final
section, Section 5, we explain how to modify our results to compute the Euler
characteristic of this odd Lie graph complex, which we denote
$e^{\mathrm{odd}}({\operatorname{Out}}(F_{n}))$. The results also extend to
the analysis of the asymptotics, and we find

######  Theorem 1.3.

The ratio
$\lim_{n\rightarrow\infty}e^{\mathrm{odd}}({\operatorname{Out}}(F_{n}))/\chi({\operatorname{Out}}(F_{n}))=e^{\frac{1}{4}}\approx
1.28.$

## Acknowledgments

We are grateful to Jos Vermaseren for generous FORM programming help and to
Thomas Willwacher for illuminating discussions. MB was supported by Dr. Max
Rössler, the Walter Haefner Foundation and the ETH Zürich Foundation.

##  2\. A first formula for $e({\operatorname{Out}}(F_{n}))$

###  2.1. The rational Euler characteristic

As noted in the introduction, Brown’s theorem says we can compute
$e({\operatorname{Out}}(F_{n}))$ by adding up the rational Euler
characteristics of centralizers of finite-order elements. One way to compute
the rational Euler characteristic of a group $\Gamma$ is to find a
contractible cell complex $Y$ on which $\Gamma$ acts properly and cocompactly;
the rational Euler characteristic $\chi(\Gamma)$ is then given by the formula

$\chi(\Gamma)=\sum_{[\sigma]}\frac{(-1)^{\dim(\sigma)}}{|{\operatorname{Stab}}(\sigma)|},$

where we sum over all orbits $[\sigma]$ of cells, $\sigma$ is a representative
from the orbit and ${\operatorname{Stab}}(\sigma)$ is its stabilizer under the
group action. Fortunately, we have such complexes $Y$ for centralizers of
finite-order elements of ${\operatorname{Out}}(F_{n})$.

The entire group ${\operatorname{Out}}(F_{n})$ centralizes the identity.
Recall from [17] that ${\operatorname{Out}}(F_{n})$ acts properly and
cocompactly on the spine $K_{n}$ of Outer space. $K_{n}$ is a contractible
cube complex with one $k$-dimensional cube for each equivalence class
$[G,\Phi,g]$ of triples $(G,\Phi,g)$, where

  * •

$G$ is a connected admissible graph,

  * •

$\Phi$ is a subforest of $G$ with $k$ edges and

  * •

$g\colon F_{n}\to\pi_{1}(G)$ is an isomorphism, called a marking.

Here by a _graph_ we mean a CW-complex of dimension $0$ or $1$, a _forest_ is
a graph without cycles, and a subforest of $G$ is a subcomplex that is a
forest and contains all of the vertices of $G$. We say a graph is of _rank_
$n$ if its fundamental group has rank $n$. A graph is admissible if it has no
isolated, univalent or bivalent vertices. Two triples $(G,\Phi,g)$ and
$(G^{\prime},\Phi^{\prime},g^{\prime})$ are equivalent if there is a graph
isomorphism $h\colon G\to G^{\prime}$ sending $\Phi$ to $\Phi^{\prime}$ and
inducing an isomorphism $h_{*}\colon\pi_{1}(G)\rightarrow\pi_{1}(G^{\prime})$,
such that $g^{-1}h_{*}g=\operatorname{id}.$ A pair $(G,\Phi)$ consisting of an
admissible graph $G$ and a subforest $\Phi$ will be called a forested graph.

The spine $K=K_{n}$ is contractible, and the action of
${\operatorname{Out}}(F_{n})$ on $K$ simply changes the marking $g$. Thus
there is one orbit for each isomorphism class $[G,\Phi]$ of connected forested
graphs. The stabilizer of a cube $[G,\Phi,g]$ is isomorphic to
${\operatorname{Aut}}(G,\Phi)$, the automorphisms of $G$ that preserve $\Phi.$
Thus,

$\chi({\operatorname{Out}}(F_{n}))=\chi(C(\operatorname{id}))=\sum_{\begin{subarray}{c}[G,\Phi]\\\
G\,\mathrm{connected}\\\
\mathrm{rank}(G)=n\end{subarray}}\frac{(-1)^{e(\Phi)}}{|{\operatorname{Aut}}(G,\Phi)|},$

where $e(\Phi)$ is the number of edges in $\Phi$.

###  2.2. The equivariant spine

In [24] an equivariant version of $K$ was introduced, which can be used to
study the centralizer of any finite order element of
${\operatorname{Out}}(F_{n})$ (in fact the centralizer of any finite-order
subgroup). We briefly summarize the construction. A graph $G$ is said to
realize a finite-order automorphism $\alpha$ if there is some marking $g\colon
F_{n}\to\pi_{1}(G)$ and automorphism $f_{\alpha}$ of $G$ such that
$g^{-1}(f_{\alpha})_{*}g=\alpha.$ Every finite-order element of
${\operatorname{Out}}(F_{n})$ can be realized on some admissible graph $G,$
[16, 21]. This translates to the statement that the action of $\alpha$ on $K$
has at least one fixed point. The centralizer $C(\alpha)$ acts on the entire
fixed-point set $K_{\alpha}$ of $\alpha$. It follows from [24] that this fixed
point set is contractible, cocompact and has the structure of a cube complex.
Specifically, $K_{\alpha}$ has one cube for each equivalence class of triples
$(G,\Phi,g)_{\alpha}$ where $(G,g)$ realizes $\alpha$ and $\Phi$ is a
(possibly empty) forest in $G$ that is invariant under the action of $\alpha$.
Here $(G,\Phi,g)_{\alpha}$ is equivalent to
$(G^{\prime},\Phi^{\prime},g^{\prime})_{\alpha}$ if there is an
$\alpha$-invariant automorphism $h\colon G\to G^{\prime}$ sending $\Phi$ to
$\Phi^{\prime}$ such that $g^{-1}h_{*}g=\operatorname{id}$, and again we write
$[G,\Phi,g]_{\alpha}$ for the equivalence class. The dimension of the cube
$[G,\Phi,g]_{\alpha}$ is the number $e_{\alpha}(\Phi)$ of edge-orbits in
$\Phi$.

The stabilizer ${\operatorname{Stab}}[G,\Phi,g]_{\alpha}$ is isomorphic to
${\operatorname{Aut}}_{\alpha}(G,\Phi),$ the automorphisms of $G$ that commute
with the action of $\alpha$ and send $\Phi$ to itself, so

$\chi(C(\alpha))=\sum_{\begin{subarray}{c}[G,\Phi]_{\alpha}\\\
G\,\mathrm{connected}\\\
\mathrm{rank}(G)=n\end{subarray}}\frac{(-1)^{e_{\alpha}(\Phi)}}{|{\operatorname{Aut}}_{\alpha}(G,\Phi)|},$

where $[G,\Phi]_{\alpha}$ runs over isomorphism classes of pairs that realize
$\alpha$ on a connected graph $G$ of rank $n$. Brown’s theorem [12] then gives

$e({\operatorname{Out}}(F_{n}))=\sum_{[\alpha]}\sum_{\begin{subarray}{c}[G,\Phi]_{\alpha}\\\
G\,\mathrm{connected}\\\
\mathrm{rank}(G)=n\end{subarray}}\frac{(-1)^{e_{\alpha}(\Phi)}}{|{\operatorname{Aut}}_{\alpha}(G,\Phi)|},$

where $[\alpha]$ runs over conjugacy classes of finite-order elements
$\alpha$.

The group ${\operatorname{Aut}}(G,\Phi)$ acts on itself by conjugation, so the
orbit-stabilizer theorem gives $|{\operatorname{Aut}}(G,\Phi)|=|(\hbox{orbit
of
}\alpha)|\cdot|{\operatorname{Stab}}_{{\operatorname{Aut}}(G,\Phi)}(\alpha)|$.
Since
${\operatorname{Stab}}_{{\operatorname{Aut}}(G,\Phi)}(\alpha)={\operatorname{Aut}}_{\alpha}(G,\Phi)$
this gives:

######  Theorem 2.1.

$e({\operatorname{Out}}(F_{n}))=\sum_{\begin{subarray}{c}[G,\Phi]\\\
G\,\mathrm{connected}\\\
\mathrm{rank}(G)=n\end{subarray}}\frac{1}{|{\operatorname{Aut}}(G,\Phi)|}\sum_{\alpha\in{\operatorname{Aut}}(G,\Phi)}(-1)^{e_{\alpha}(\Phi)},$

where we sum over the set of isomorphism classes $[G,\Phi]$ of connected
forested graphs of rank $n$.

###  2.3. Disconnected graphs

Recall that the Euler characteristic of a connected graph of rank $n$ is
$\chi(G)=1-n$. The graph’s Euler characteristic is often better behaved than
its rank. For instance, the formula in Theorem 2.1 is easier to work with if
we drop the requirement that $G$ be connected and shift the index by one, i.e.
define

(1) $\displaystyle\operatorname{\widehat{e}}_{n}$
$\displaystyle=\sum_{\begin{subarray}{c}[G,\Phi]\\\
\chi(G)=-n\end{subarray}}\frac{1}{|{\operatorname{Aut}}(G,\Phi)|}\sum_{\alpha\in{\operatorname{Aut}}(G,\Phi)}(-1)^{e_{\alpha}(\Phi)},$

where we sum over all isomorphism classes $[G,\Phi]$ of (not necessarily
connected) forested graphs with $\chi(G)=-n$. In this subsection we show how
to recover $e({\operatorname{Out}}(F_{n+1}))$ once the numbers
$\operatorname{\widehat{e}}_{n}$ are known.

We begin by deriving new formulas for $e({\operatorname{Out}}(F_{n+1}))$ and
$\operatorname{\widehat{e}}_{n}$. Define a forested graph $(G,\Phi)$ to be
even if $G$ has no automorphisms that induce an odd permutation of the edges
of $\Phi$.

######  Proposition 2.2.

If we sum over all isomorphism classes $[G,\Phi]$ —

  1. (1)

— of even forested graphs with $\chi(G)=-n$, then

$\sum_{\begin{subarray}{c}[G,\Phi]\,\mathrm{even}\\\
\chi(G)=-n\end{subarray}}(-1)^{e(\Phi)}=\operatorname{\widehat{e}}_{n}.$

  2. (2)

— of _connected_ even forested graphs with $\chi(G)=-n$, then

$\sum_{\begin{subarray}{c}[G,\Phi]\,\mathrm{even}\\\ G\,\mathrm{connected}\\\
\chi(G)=-n\end{subarray}}(-1)^{e(\Phi)}=e({\operatorname{Out}}(F_{n+1})).$

######  Remark 2.3.

Conant and Vogtmann showed in [15] that Kontsevich’s Lie graph complex, as
defined in [22] is quasi-isomorphic to the complex spanned by even forested
graphs. Thus this proposition shows that $e({\operatorname{Out}}(F_{n}))$ is
equal to the Euler characteristic of the Lie graph complex.

Proposition 2.2 is an immediate consequence of the following lemma.

######  Lemma 2.4.

The sum $\sum_{\alpha\in{\operatorname{Aut}}(G,\Phi)}(-1)^{e_{\alpha}(\Phi)}$
vanishes if $(G,\Phi)$ has an automorphism that induces an odd permutation on
$\Phi$ and is equal to $(-1)^{e(\Phi)}|{\operatorname{Aut}}(G,\Phi)|$
otherwise.

###### Proof.

An element $\alpha\in{\operatorname{Aut}}(G,\Phi)$ induces a permutation
$\alpha_{\Phi}\in\operatorname{{\mathfrak{S}}}_{e(\Phi)}$ on the set of edges
of $\Phi$. By definition, the number $e_{\alpha}(\Phi)$ is equal to the number
of cycles in the cycle decomposition of $\alpha_{\Phi}$. The sign of a
permutation is the parity of the number of its even cycles. Since the parity
of the number of odd cycles of a permutation on an $n$-element set is equal to
the parity of $n$, we have
$(-1)^{e_{\alpha}(\Phi)}={\operatorname{sign}}(\alpha_{\Phi})(-1)^{e(\Phi)}$.
The sign function gives a homomorphism from ${\operatorname{Aut}}(G,\Phi)$ to
the cyclic group of order 2, which is surjective if and only if
${\operatorname{Aut}}(G,\Phi)$ contains an odd permutation. If it is
surjective, then half of the elements of ${\operatorname{Aut}}(G,\Phi)$ have
each sign, so
$\sum_{\alpha\in{\operatorname{Aut}}(G,\Phi)}{\operatorname{sign}}(\alpha_{\Phi})=0;$
otherwise
$\sum_{\alpha\in{\operatorname{Aut}}(G,\Phi)}{\operatorname{sign}}(\alpha_{\Phi})=(-1)^{e(\Phi)}|{\operatorname{Aut}}(G,\Phi)|.$∎

###### Proof of Proposition 2.2.

Use Lemma 2.4, Eq. (1) and Theorem 2.1. ∎

Each pair consisting of a forested graph and an automorphism contributes to
the sum in the definition of $\operatorname{\widehat{e}}_{n}$, so evaluating
this sum means doing a weighted count of forested graphs and their
automorphisms. We will do this counting by means of generating functions, i.e.
formal power series whose coefficients encode the counts we are interested in.

We can also use formal power series to describe the relation between
$\operatorname{\widehat{e}}_{n}$ and $e({\operatorname{Out}}(F_{n+1}))$. By
standard topological quantum field theory convention, we use the symbol
$\hbar$ as the formal variable that marks the negative Euler characteristic of
the graphs.

######  Theorem 2.5.

$\displaystyle\sum_{n\geq
0}\operatorname{\widehat{e}}_{n}\hbar^{n}=\prod_{n=1}^{\infty}\left(\frac{1}{1-\hbar^{n}}\right)^{e({\operatorname{Out}}(F_{n+1}))}.$

###### Proof.

For any (possibly disconnected) admissible graph $G$ and subforest
$\Phi\subset G$, set $\theta(G,\Phi)=(-1)^{e(\Phi)}\hbar^{-\chi(G)}$. Since an
admissible graph is either trivial or has strictly negative Euler
characteristic, $\theta(G,\Phi)\in{\mathbb{Q}}[[\hbar]]$. The function
$\theta$ factors over connected components, i.e.

$\theta((G_{1},\Phi_{1})\sqcup(G_{2},\Phi_{2}))=\theta(G_{1},\Phi_{1})\theta(G_{2},\Phi_{2}).$

By Proposition 2.2(1),

$\sum_{n\geq
0}\operatorname{\widehat{e}}_{n}\hbar^{n}=\sum_{[G,\Phi]\,\text{even}}\theta(G,\Phi),$

where we sum over all isomorphism classes of (possibly disconnected) even
forested graphs $[G,\Phi]$.

Each isomorphism class $[G,\Phi]$ can be described by giving a set of
isomorphism classes of connected graphs together with the multiplicity with
which each connected class appears in the disconnected class. In the sum
above, a component $[g,\varphi]$ of $[G,\Phi]$ such that $\varphi$ has an odd
number of edges can appear at most once, as otherwise $[G,\Phi]$ would have an
odd automorphism. Components with an even number of edges in the forest can
appear with any multiplicity. The sum of the function $\theta$ over all even
admissible forested graphs hence satisfies the following identity:

$\displaystyle\sum_{n\geq
0}\operatorname{\widehat{e}}_{n}\hbar^{n}=\sum_{[G,\Phi]\,\text{even}}\theta(G,\Phi)=\left(\prod_{\begin{subarray}{c}[g,\varphi]\\\
e(\varphi)\,\text{odd}\end{subarray}}\left(1+\theta(g,\varphi)\right)\right)\left(\prod_{\begin{subarray}{c}[g,\varphi]\\\
e(\varphi)\,\text{even}\end{subarray}}\sum_{m\geq
0}\theta(g,\varphi)^{m}\right),$

where the $[g,\varphi]$ are isomorphism classes of connected forested graphs
and $e(\varphi)$ denotes the number of edges of $\varphi$.

Using the fact that $\theta(g,\varphi)$ is $-\hbar^{-\chi(g)}$ if
$[g,\varphi]$ is odd and $\hbar^{-\chi(g)}$ if $[g,\varphi]$ is even and
evaluating the sum over $m$, we obtain

$\displaystyle\sum_{n\geq
0}\operatorname{\widehat{e}}_{n}\hbar^{n}=\left(\prod_{\begin{subarray}{c}[g,\varphi]\\\
e(\varphi)\,\text{odd}\end{subarray}}\left(1-\hbar^{-\chi(g)}\right)\right)\left(\prod_{\begin{subarray}{c}[g,\varphi]\\\
e(\varphi)\,\text{even}\end{subarray}}\frac{1}{1-\hbar^{-\chi(g)}}\right)=\prod_{n\geq
1}\frac{(1-\hbar^{n})^{\beta_{\text{odd}}^{n}}}{(1-\hbar^{n})^{\beta_{\text{even}}^{n}}},$

where $\beta_{\text{odd}}^{n}$ and $\beta_{\text{even}}^{n}$ are the numbers
of connected forested admissible graphs without odd edge-automorphisms with
Euler characteristic $-n$ with an odd or even number of edges in the forest. A
connected graph with Euler characteristic $-n$ has rank $n+1$. Hence, by
Proposition 2.2(2),
$\beta_{\text{even}}^{n}-\beta_{\text{odd}}^{n}=e({\operatorname{Out}}(F_{n+1}))$.
∎

We can now explain how to calculate the numbers
$e({\operatorname{Out}}(F_{n}))$ recursively from the numbers
$\operatorname{\widehat{e}}_{n}$. Recall that the classical Möbius function
$\mu$ is defined recursively for positive integers by $\mu(1)=1$ and
$\sum_{d\mid n}\mu(d)=0$ for all $n\geq 2$.

######  Corollary 2.6.

Let $\sum_{n\geq 1}\operatorname{e}_{n}\hbar^{n}=\log f(\hbar)$ be the
logarithm of the series $f(\hbar)=\sum_{n\geq
0}\operatorname{\widehat{e}}_{n}\hbar^{n}$. The numbers $\operatorname{e}_{n}$
for $n\geq 1$ are given recursively by

$\displaystyle\operatorname{e}_{n}=\operatorname{\widehat{e}}_{n}-\frac{1}{n}\sum_{k=1}^{n-1}k\operatorname{e}_{k}\operatorname{\widehat{e}}_{n-k}$

and $e({\operatorname{Out}}(F_{n+1}))$ for $n\geq 1$ by

$\displaystyle e({\operatorname{Out}}(F_{n+1}))=\sum_{d\mid
n}\frac{\mu(d)}{d}\operatorname{e}_{n/d}.$

###### Proof.

The recursive expression for $\operatorname{e}_{n}$ in terms of
$\operatorname{\widehat{e}}_{n}$ follows by taking the derivative of $\log
f(x)$ with respect to $\hbar$ and using $(\log
f(x))^{\prime}={f^{\prime}(x)/f(x)}$. Taking the logarithm of the statement of
Theorem 2.5, using $\log(1/(1-x))=\sum_{n=1}^{\infty}x^{n}/n$ and the
definition of the Möbius function gives the second formula. ∎

##  3\. An effective formula for $e({\operatorname{Out}}(F_{n}))$

###  3.1. Admissible trees

In the last section we reduced the problem of computing
$e({\operatorname{Out}}(F_{n}))$ to the problem of doing a weighted count of
forested graphs. In order to count forested graphs we will first count trees,
then forests, then ways of matching the leaves of the forests to form forested
graphs. Throughout the rest of the paper we fix the following conventions and
terminology. By a tree we mean a connected graph with no cycles. A forest is a
disjoint union of trees. We give univalent vertices of trees and forests a
special role and call them _leaves_ ; other vertices are called internal
vertices. A tree or forest is admissible if it has no isolated or bivalent
vertices. A _rooted tree_ is a tree where one univalent vertex is
distinguished as the _root_ while the other univalent vertices are still
called leaves. We require admissible trees to have either a root or at least
one internal vertex, so a single 1-cell which connects two non-root leaves is
not allowed. The internal edges of a tree or forest are the $1$-cells that are
not attached to leaves or the root. Our trees, rooted trees, and forests will
be _labeled_. That means each leaf shall be decorated with a unique element
from some given finite set $U$.

The set of all admissible labeled (or labeled rooted) trees forms a
combinatorial species in the sense of Joyal [20] (see also [3]). Since our
counting problems fit neatly into the theory of species, we review the
relevant parts of this theory in the next subsection.

###  3.2. Species and generating functions

A combinatorial species is a functor from the groupoid of finite sets to
itself. More explicitly, a species $\mathcal{S}$ associates to every finite
set $U$ of _labels_ , a finite set $\mathcal{S}[U]$ of _combinatorial objects_
such that every bijection $U\rightarrow V$ gives rise to a bijection of sets
$\mathcal{S}[U]\rightarrow\mathcal{S}[V]$ in a way compatible with
composition. In the case $U=\\{1,\ldots,n\\}$ we write $\mathcal{S}[n]$ for
$\mathcal{S}[U]$. An element of $\mathcal{S}[U]$ for some $U$ is an
$\mathcal{S}$-object, or more informally, an object of $\mathcal{S}$.

For every species $\mathcal{S}$ there is a natural action of
$\operatorname{{\mathfrak{S}}}_{n}$ on $\mathcal{S}[n]$ that permutes the
labels. The orbit of an element $\phi\in\mathcal{S}[n]$ under this action is
an isomorphism class of combinatorial objects. We will also call such a class
an _unlabeled object_. The _stabilizer_ of an element $\phi\in\mathcal{S}[n]$
is the group of relabelings that leaves the object invariant. We will denote
this stabilizer by ${\operatorname{Aut}}(\phi)$.

A _set partition_ of $U$ with $k$ _blocks_ is a collection
$\pi=\\{B_{1},\ldots,B_{k}\\}$ of $k$ mutually disjoint subsets of $U$ such
that $\bigcup_{B\in\pi}B=U$. From a given species $\mathcal{S}$ we can
construct a new species ${\operatorname{Set}}^{k}(\mathcal{S})$ by associating
to a set $U$ all collections of objects $\\{\phi_{1},\ldots,\phi_{k}\\}$ such
that $\phi_{1}\in\mathcal{S}[B_{1}],\ldots,\phi_{k}\in\mathcal{S}[B_{k}]$ for
some partition of $U$ into blocks $B_{1},\ldots,B_{k}$. The functor
${\operatorname{Set}}^{k}(\mathcal{S})$ is the species of sets of size $k$
which contain objects of $\mathcal{S}$. To make the formulas more compact we
agree that ${\operatorname{Set}}^{0}(\mathcal{S})[0]$ contains one element,
the empty set, and that ${\operatorname{Set}}^{k}(\mathcal{S})[0]$ is empty
for all $k\geq 1$.

Let $\mathbb{A}$ be an algebra and
$\omega:\mathcal{S}[U]\rightarrow\mathbb{A}$ a weight function that associates
some element of $\mathbb{A}$ to each object of $\mathcal{S}[U]$ in a way that
is independent of the labeling. We can extend the weight function $\omega$ to
${\operatorname{Set}}^{k}(\mathcal{S})$ by setting the weight of the empty set
to $1$ and
$\omega(\\{\phi_{1},\ldots,\phi_{k}\\})=\prod_{\ell=1}^{k}\omega(\phi_{\ell})$.

When working with a formal power series $F(x)=\sum a_{i}x^{i}$, we will
frequently use the coefficient extraction operator $[x^{n}]$ to extract the
coefficient of $x^{n}$, so $[x^{n}]F(x)=a_{n}$. We now define two formal power
series, in $\mathbb{A}[[x]]$ and $\mathbb{A}[[x,y]]$ respectively, by

(2) $\displaystyle S(x)$ $\displaystyle=\sum_{n\geq
1}\frac{x^{n}}{n!}\sum_{\phi\in\mathcal{S}[n]}\omega(\phi)$ and $\displaystyle
S_{{\operatorname{Set}}}(x,y)$ $\displaystyle=\sum_{n,k\geq
0}\frac{x^{n}}{n!}y^{k}\sum_{\Phi\in{\operatorname{Set}}^{k}(\mathcal{S})[n]}\omega(\Phi).$

These are exponential generating functions for weighted counts: $[x^{n}]S(x)$
is ${1/n!}$ times the number of objects $\phi\in\mathcal{S}[n]$, counted with
weight $\omega(\phi)$, and $[x^{n}y^{k}]S(x,y)$ is ${1/n!}$ times the number
of elements $\Phi\in{\operatorname{Set}}^{k}(\mathcal{S})[n]$, counted with
weight $\omega(\Phi)$. We will make frequent use of the following _exponential
formula_ , a standard lemma that relates the power series $S$ and
$S_{\operatorname{Set}}$.

######  Lemma 3.1.

$\displaystyle S_{{\operatorname{Set}}}(x,y)=\exp\left(y\,S(x)\right).$

###### Proof.

Use the expansion $\exp(X)=\sum_{n\geq 0}X^{n}/n!$ and the fact that the
number of set partitions of a set of cardinality $n$ into $k$ blocks with
sizes $m_{1},\ldots,m_{k}$ is given by ${n!/(k!m_{1}!\ldots m_{k}!)}$. ∎

We next want to count labeled combinatorial objects while keeping track of
automorphisms. For this, we will need more sophisticated generating functions,
called _cycle index series_. The terminology comes from the notion of cycle
type for a permutation, which we now review.

Let $n\in\mathbb{N}$ be a positive integer. An integer partition of $n$ is a
sequence of positive integers
$\lambda=(\lambda_{1},\lambda_{2},\ldots,\lambda_{\ell})$ such that
$\lambda_{1}\geq\lambda_{2}\geq\ldots\geq\lambda_{\ell}>0$ and
$n=\lambda_{1}+\ldots+\lambda_{\ell}$. The $\lambda_{i}$ are called _parts_ of
$\lambda$. We write $\lambda\vdash n$ or $|\lambda|=n$. The integer $n$ is the
size of the partition and $\ell$, the number of parts, is the length of the
partition. We will often use the more compact notation
$\lambda=[1^{m_{1}}\cdots n^{m_{n}}],$ indicating that $\lambda$ has $m_{k}$
parts of size $k$ (the terms with $m_{i}=0$ are usually omitted; for example,
$\lambda=(4,4,1,1,1)$ is written $[1^{3}4^{2}]$). In this notation the length
of $\lambda$ is $\ell(\lambda)=m_{1}+\cdots+m_{\ell}$, the size is
$|\lambda|=m_{1}+2m_{2}+\cdots+nm_{n}$. Each permutation
$\pi\in\operatorname{{\mathfrak{S}}}_{n}$ factors uniquely as a product of
disjoint cycles. If the orders of these cycles are
$\lambda_{1},\ldots,\lambda_{\ell}$, where
$\lambda_{1}\geq\ldots\geq\lambda_{\ell}$, then
$\lambda(\pi)=(\lambda_{1},\ldots,\lambda_{\ell})$ is a partition of $n$
called the _cycle type_ of $\pi$.

Given an integer partition $\lambda=[1^{m_{1}}2^{m_{2}}\ldots n^{m_{n}}]$ let
$x^{\lambda}$ denote the monomial $x_{1}^{m_{1}}x_{2}^{m_{2}}\cdots
x_{n}^{m_{n}}$. A formal power series in the variables
${\overline{x}}=\\{x_{1},x_{2},\ldots\\}$ is an infinite sum of terms
$a_{\lambda}x^{\lambda}$, with $a_{\lambda}\in\mathbb{A}$, such that, for all
$n$, we only have a finite number of terms if restrict to partitions with
$|\lambda|\leq n$. If $\alpha$ is a permutation of cycle type $\lambda$ we
also define $x^{\alpha}=x^{\lambda}$.

For a given species $\mathcal{S}$, let $\mathcal{AS}$ be the species of pairs
$(\phi,\alpha)$, where $\phi$ is an object of $\mathcal{S}$ and $\alpha$ an
automorphism of $\phi$:

$\displaystyle\mathcal{AS}[n]=$
$\displaystyle\\{(\phi,\alpha)|\phi\in\mathcal{S}[n]\text{ and
}\alpha\in{\operatorname{Aut}}(\phi)\leq\mathfrak{S}_{n}\\}.$

Let $\omega$ be a weight function that attaches to an object $(\phi,\alpha)$
of $\mathcal{AS}$ an element $\omega(\phi,\alpha)\in\mathbb{A}$ that does not
depend on the labeling. The cycle index series for $\mathcal{S}$ weighted by
$\omega$ is the formal power series $\mathbf{S}$ in ${\overline{x}}$ whose
terms mark the cycle type of the automorphism, i.e.

$\displaystyle{\mathbf{S}}({\overline{x}})=\sum_{n\geq
1}\frac{1}{n!}\sum_{(\phi,\alpha)\in\mathcal{AS}[n]}\omega(\phi,\alpha)\,x^{\alpha}.$

In other words, $[x^{\lambda}]{\mathbf{S}}({\overline{x}})$ is
${1/|\lambda|!}$ times the weighted count of pairs
$(\phi,\alpha)\in\mathcal{AS}$ such that $\alpha$ has cycle type $\lambda$.
The cycle index series ${\mathbf{S}}({\overline{x}})$ generalizes the
generating function of labeled objects in Eq. (2), as we recover $S(x)$ by
setting $\omega(\phi,\operatorname{id})=\omega(\phi)$, $x_{1}=x$ and all other
$x_{k}$-variables to $0$.

We now want to extend our cycle index series on $\mathcal{S}$ to one for
${\operatorname{Set}}^{k}(\mathcal{S})$, and show how to compute it from
${\mathbf{S}}({\overline{x}})$. An element
$\Phi\in{\operatorname{Set}}^{k}(\mathcal{S})[n]$ is a set of $k$ elements of
$\mathcal{S}$ with a total of $n$ labels. An element
$\gamma\in{\operatorname{Aut}}(\Phi)$ permutes the labels but preserves the
set. If some elements of $\mathcal{S}$ are isomorphic then $\gamma$ may
permute them, so $\gamma$ induces a permutation
$\gamma_{\Phi}\in\mathfrak{S}_{k}$. We introduce a new infinite set of
variables ${\overline{y}}=\\{y_{1},y_{2},\ldots\\}$ to mark the cycle type of
$\gamma_{\Phi}$, and define

$\displaystyle{\mathbf{S}}_{\operatorname{Set}}({\overline{x}},{\overline{y}})=\sum_{n,k\geq
0}\frac{1}{n!}\sum_{(\Phi,\gamma)\in{\mathcal{A}}{\operatorname{Set}}^{k}(\mathcal{S})[n]}\omega(\Phi,\gamma)\,x^{\gamma}y^{\gamma_{\Phi}}.$

Here
$\omega(\Phi,\gamma)=\omega(\phi_{1},\gamma_{1})\ldots\omega(\phi_{\ell},\gamma_{\ell})$,
where

  * •

$\gamma_{\Phi}$ has cycle type
$\lambda=(\lambda_{1},\lambda_{2},\ldots,\lambda_{\ell})$ of length $\ell$

  * •

$\phi_{i}\in\Phi$ is a representative of the $i$th cycle, which has size
$\lambda_{i}$

  * •

$\gamma_{i}$ is the restriction of $\gamma^{\lambda_{i}}$ to $\phi_{i}.$

######  Proposition 3.2.

Let ${\mathbf{S}}({\overline{x}}_{[k]})$ be the series obtained from
${\mathbf{S}}({\overline{x}})$ by replacing each occurrence of $x_{i}$ by
$x_{ki}$. Then

$\displaystyle{\mathbf{S}}_{\operatorname{Set}}({\overline{x}},{\overline{y}})=\exp\left(\sum_{k\geq
1}y_{k}\frac{{\mathbf{S}}({\overline{x}}_{[k]})}{k}\right),$

Ultimately, this proposition goes back to Pólya [26]. It follows from Lemma
3.1 combined with the generating function for _wreaths_ of $\mathcal{S}$
structures. We give a proof below, but refer to [3] Chapter 4.3 for a more
detailed argument, using a slightly different type of weight function
$\omega$.

To prove Proposition 3.2 we first introduce a new species
${\mathcal{A}{\operatorname{Cyc}}}^{k}\mathcal{S}$. An element of
${\mathcal{A}{\operatorname{Cyc}}}^{k}\mathcal{S}[n]$ is a pair
$(\Phi,\gamma)$ where $\Phi=\\{\phi_{1},\ldots,\phi_{k}\\}$ is a collection of
objects in $\mathcal{S}$ with a total of $n$ labels, and
$\gamma\in{\operatorname{Aut}}(\Phi)$ is a permutation of the labels of $\Phi$
that cyclically permutes the $\phi_{i}$, i.e. $\gamma_{\Phi}$ is a $k$-cycle
in $\mathfrak{S}_{k}$. In particular, all of the $\phi_{i}$ must be
isomorphic, i.e. equivalent as unlabeled objects.

######  Lemma 3.3.

$\displaystyle\sum_{n\geq
1}\frac{1}{n!}\sum_{(\Phi,\gamma)\in{\mathcal{A}{\operatorname{Cyc}}}^{k}(\mathcal{S})[n]}\omega(\Phi,\gamma)x^{\gamma}=\frac{{\mathbf{S}}({\overline{x}}_{[k]})}{k}.$

###### Proof.

Let $(\Phi,\gamma)$ be an element of
${\mathcal{A}{\operatorname{Cyc}}}^{k}\mathcal{S}[n]$. We claim that
$(\Phi,\gamma)$ is equivalent to a tuple
$(\kappa,\pi,\phi,\alpha,\gamma_{1},\ldots,\gamma_{k-1}),$ where

  * •

$\kappa$ is a $k$-cycle in $\mathfrak{S}_{k},$

  * •

$\pi$ is a partition of $\\{1,\ldots,n\\}$ into $k$ blocks, each of size $d$,

  * •

$\phi$ is an object of $\mathcal{S}[d],$

  * •

$\alpha$ is an element of ${\operatorname{Aut}}(\phi),$ and

  * •

$\gamma_{i}$ is an element of $\mathfrak{S}_{d}$ for each $i=1,\ldots,k-1.$

By definition $\Phi=\\{\phi_{1},\ldots,\phi_{k}\\},$ where
$\phi_{i}\in\mathcal{S}[B_{i}]$ for some $B_{i}\subset\\{1,\ldots,n\\}$, and
$\gamma_{\Phi}$ is a $k$-cycle, so we take $\kappa=\gamma_{\Phi}$ and
$\pi=\\{B_{1},\ldots,B_{k}\\}$. Since $\gamma$ acts cyclically on $\Phi$, all
of the $\phi_{i}$ are isomorphic, so in particular they all have the same
number $d$ of labels. The unique order-preserving bijection
$B_{i}\to\\{1,\ldots,d\\}$ identifies each $\phi_{i}$ with an element
$\widehat{\phi}_{i}\in\mathcal{S}[d]$; set $\phi=\widehat{\phi}_{k}$. The
permutation $\gamma^{k}$ sends each $\phi_{i}$ to itself, so determines an
automorphism $\alpha_{i}$ of $\phi_{i}$ and therefore of $\widehat{\phi}_{i}$;
set $\alpha=\alpha_{k}$. Note that all of the $\alpha_{i}$ have the same cycle
type $\lambda=(\lambda_{1},\ldots,\lambda_{\ell})$, so the cycle type of
$\gamma$ is $k\lambda=(k\lambda_{1},\ldots,k\lambda_{\ell})$. For each
$i=1,\ldots,k-1$, the $i$th power of the $k$-cycle $\gamma_{\Phi}$ maps
$\phi_{k}$ to $\phi_{\gamma^{i}_{\Phi}(k)}$; let $\gamma_{i}$ be the induced
isomorphism
$\gamma_{i}\colon\widehat{\phi}_{k}\to\widehat{\phi}_{\gamma^{i}_{\Phi}(k)}$
in $\mathfrak{S}_{d}$.

Finally, note that
$\omega(\Phi,\gamma)=\omega(\phi_{k},\gamma^{k})=\omega(\phi,\alpha)$. Since
${\mathcal{A}{\operatorname{Cyc}}}^{k}(\mathcal{S})[n]$ is empty unless $k|n$,
we can now write the left hand side of the equation in the statement of the
lemma as,

(3) $\sum_{n=dk\geq
1}\frac{1}{n!}C_{n,k}\sum_{(\phi,\alpha)\in\mathcal{AS}[d]}\omega(\phi,\alpha)x^{k\circ\alpha},$

where $k\circ\alpha$ has cycle type $k\lambda$ and $C_{n,k}$ is the number of
partitions $\pi$ of $n$ into $k$ equal parts times the number of cyclic
permutations $\kappa$ in $\mathfrak{S}_{k}$ times the number of permutations
$\gamma_{1},\ldots,\gamma_{k-1}$ in $(\mathfrak{S}_{d})^{k-1}$, i.e.

$C_{n,k}=\frac{1}{k!}\frac{n!}{(d!)^{k}}\cdot(k-1)!\cdot(d!)^{k-1}=\frac{n!}{d!k}.$

Plugging this into Eq. (3) gives the statement of the lemma. ∎

###### Proof of Proposition 3.2.

We have

$\displaystyle\mathcal{A}{\operatorname{Set}}(\mathcal{S})[n]=$
$\displaystyle\\{(\Phi,\gamma)|\Phi\text{ is a finite set of objects of
$\mathcal{S}$ with a total of $n$ distinct labels, }$ $\displaystyle\text{ and
}\gamma\in{\operatorname{Aut}}(\Phi)\leq\mathfrak{S}_{n}\\}.$

Since every permutation $\gamma$ can be uniquely decomposed into a product of
cycles, we have an isomorphism of species

$\mathcal{A}{\operatorname{Set}}(\mathcal{S})\cong\bigcup_{\ell\geq
1}{\operatorname{Set}}^{\ell}\left(\bigcup_{k\geq
1}{\mathcal{A}{\operatorname{Cyc}}}^{k}(\mathcal{S})\right).$

Therefore the statement follows from an application of Lemma 3.1 to the right
hand side, using the generating function of the species
${\mathcal{A}{\operatorname{Cyc}}}^{k}(\mathcal{S})$ given by Lemma 3.3 and
summation over all $k$, using the variables ${\overline{y}}$ to keep track of
the cycle type of the permutation. ∎

###  3.3. Matchings

In order to form a forested graph with an automorphism preserving the forest,
we will start with a forest equipped with an automorphism $\alpha$, then pair
its leaves by a fixed-point free involution that commutes with $\alpha$. In
this subsection we apply the counting methods from the previous subsection to
count the number of such involutions.

A fixed-point free involution is also called a matching; it divides the set
into orbits of size $2$, so we will use the species $\mathcal{E}$ of sets of
cardinality $2$, i.e. $\mathcal{E}[2]=\\{1,2\\}$ and
$\mathcal{E}[n]=\emptyset$ for $n\neq 2$. The generating function (with
trivial weight) is $E(x)={x^{2}/2}$. Matchings on a set of $2k$ elements
correspond to elements of ${\operatorname{Set}}^{k}(\mathcal{E})[2k]$; for
example the elements of ${\operatorname{Set}}^{2}\mathcal{E}[4]$ are
$\\{\\{1,2\\},\\{3,4\\}\\},\\{\\{1,3\\},\\{2,4\\}\\}$ and
$\\{\\{1,4\\},\\{2,3\\}\\}$. By Lemma 3.1 we have

$\displaystyle
E_{{\operatorname{Set}}}(x,y)=\exp\left(y\frac{x^{2}}{2}\right)=\sum_{k\geq
0}(2k-1)!!\frac{x^{2k}}{(2k)!}y^{k},$

where the second equality is obtained using the expansion $\exp(X)=\sum_{n\geq
0}{X^{n}/n!}$ and the formula $(2k-1)!!={(2k)!/(k!2^{k})}.$ Thus we recover
the (easy) fact that the number of matchings of a set of cardinality $2k$ is
$(2k-1)!!$, and there are none if the cardinality is odd.

Now consider the species $\mathcal{AE}=\mathcal{AE}[2]$ of sets of cardinality
$2$ with automorphisms on them. A set of cardinality $2$ has only two
automorphisms, the trivial one (marked by $x_{1}x_{1}=x_{1}^{2}$) and the
transposition (marked by $x_{2}$). The cycle index series of $\mathcal{E}$
with trivial weight is therefore

${\mathbf{E}}({\overline{x}})=\frac{1}{2!}\sum_{(\phi,\alpha)\in\mathcal{AE}[2]}x^{\alpha}=\frac{1}{2}\left(x_{1}^{2}+x_{2}\right).$

A matching of $2k$ elements corresponds to an element
$\Phi\in{\operatorname{Set}}^{k}(\mathcal{E})[2k]$. The automorphisms of such
an element $\Phi$ are permutations that commute with the corresponding fixed-
point free involution $\iota=\iota_{\Phi}$. We may count such permutations
using Proposition 3.2, which gives

(4)
$\displaystyle{\mathbf{E}}_{{\operatorname{Set}}}({\overline{x}},{\overline{y}})=\exp\left(\sum_{k\geq
1}\frac{y_{k}}{2k}\left(x_{k}^{2}+x_{2k}\right)\right).$

######  Proposition 3.4.

$\displaystyle\sum_{n\geq
0}\frac{1}{(2n)!}\sum_{(\iota,\alpha)}x^{\alpha}=\exp\left(\sum_{k\geq
1}\frac{1}{2k}\left(x_{k}^{2}+x_{2k}\right)\right),$

where the sum is over all pairs $(\iota,\alpha)$ consisting of a matching
$\iota$ of $\\{1,\ldots,2n\\}$ and a permutation
$\alpha\in\operatorname{{\mathfrak{S}}}_{2n}$ that commutes with $\iota$.

###### Proof.

By definition we have

${\mathbf{E}}_{{\operatorname{Set}}}({\overline{x}},{\overline{y}})=\sum_{n,k\geq
0}\frac{1}{n!}\sum_{(\Phi,\alpha)\in\mathcal{A}{\operatorname{Set}}^{k}(\mathcal{E})[n]}x^{\alpha}y^{\alpha_{\phi}}.$

Since ${\operatorname{Set}}^{k}\mathcal{E}[n]$ is empty unless $n$ is even and
$k=n/2$ we can rewrite this as

${\mathbf{E}}_{{\operatorname{Set}}}({\overline{x}},{\overline{y}})=\sum_{n\geq
0}\frac{1}{(2n)!}\sum_{(\Phi,\alpha)\in\mathcal{A}{\operatorname{Set}}^{n}\mathcal{E}[2n]}x^{\alpha}y^{\alpha_{\phi}}.$

As noted previously, we may identify the pairs $(\iota,\alpha)$ in the
statement of the proposition with elements $(\Phi,\alpha)$ of
$\mathcal{A}{\operatorname{Set}}^{n}(\mathcal{E})[2n]$. Using Eq. (4) and
setting $y_{k}=1$ for all $k$ gives the result. ∎

######  Corollary 3.5.

The number $\eta_{\lambda}$ of matchings that commute with a given permutation
$\alpha\in\operatorname{{\mathfrak{S}}}_{n}$ of cycle type
$\lambda=[1^{m_{1}}2^{m_{2}}\ldots n^{m_{n}}]$ is given by the formula

$\eta_{\lambda}=\prod_{k=1}^{n}\eta_{k,m_{k}},$

where

$\eta_{k,2s}=\begin{cases}k^{s}(2s-1)!!&\text{if $k$ is odd}\\\
\sum_{r=0}^{s}\binom{2s}{2r}k^{r}(2r-1)!!&\text{if $k$ is even}\end{cases}$

and

$\eta_{k,2s+1}=\begin{cases}0&\text{if $k$ is odd}\\\
\sum_{r=0}^{s}\binom{2s+1}{2r}k^{r}(2r-1)!!&\text{if $k$ is even}\end{cases}.$

######  Remark 3.6.

This statement can also be proved without the theory of species by elementary
combinatorial means. We have used species here as an easy example of the
method, which we use heavily in the next sections. Moreover, the extension to
the analogous Corollary 5.8 is done effortlessly using species.

###### Proof.

Since $\iota$ commutes with $\alpha$ if and only if $\alpha$ commutes with
$\iota$, the left hand side of Proposition 3.4 can be written

$\sum_{n\geq
0}\frac{1}{(2n)!}\sum_{\alpha\in\operatorname{{\mathfrak{S}}}_{2n}}\\#\\{\iota\in\operatorname{{\mathfrak{S}}}_{2n}|\iota\circ\alpha=\alpha\circ\iota\\}x^{\alpha}.$

Now note that the number of matchings that commute with $\alpha$ depends only
on the cycle type of $\alpha$. If we denote the set of permutations in
$\mathfrak{S}_{n}$ with cycle type $\lambda$ by $\mathfrak{S}_{n}^{\lambda}$,
the formula becomes

$=\sum_{n\geq 0}\frac{1}{(2n)!}\sum_{\lambda\vdash
2n}|\operatorname{{\mathfrak{S}}}_{2n}^{\lambda}|\eta_{\lambda}x^{\lambda}=\sum_{n\geq
0}\frac{1}{n!}\sum_{\lambda\vdash
n}|\operatorname{{\mathfrak{S}}}_{n}^{\lambda}|\eta_{\lambda}x^{\lambda},$

where we used the fact that $\eta_{\lambda}=0$ if $|\lambda|$ is odd. For
$\lambda=[1^{m_{1}}2^{m_{2}}\ldots n^{m_{n}}]$ it is easy to check that the
number of permutations in $\mathfrak{S}_{n}^{\lambda}$ is

$|\operatorname{{\mathfrak{S}}}_{n}^{\lambda}|=\frac{n!}{1^{m_{1}}m_{1}!2^{m_{2}}m_{2}!\cdots
n^{m_{n}}m_{n}!},$

so the left hand side of Proposition 3.4 is equal to

(5) $\sum_{n\geq 0}\sum_{\lambda\vdash
n}\frac{\eta_{\lambda}}{1^{m_{1}}m_{1}!2^{m_{2}}m_{2}!\cdots
n^{m_{n}}m_{n}!}x^{\lambda}.$

We now turn to the right hand side of the equation stated in Proposition 3.4.
Using $e^{X}=\sum_{s\geq 0}X^{s}/s!$, $(2s-1)!!={(2s)!/(s!2^{s})}$ and
$(x+2)^{s}=\sum_{r=0}^{s}\binom{s}{r}2^{s-r}x^{r}$ and the definition of the
numbers $\eta_{k,m}$ above, we find that for even $k$,

$\displaystyle\exp\left(\frac{x^{2}}{2k}\right)$ $\displaystyle=\sum_{s\geq
0}\frac{x^{2s}}{2^{s}k^{s}s!}=\sum_{s\geq
0}k^{s}(2s-1)!!\frac{x^{2s}}{k^{2s}(2s)!}=\sum_{m\geq
0}\eta_{k,m}\frac{x^{m}}{k^{m}m!}$ and for $k$ odd, we have
$\displaystyle{\exp\left(\frac{x^{2}+2x}{2k}\right)}$
$\displaystyle=\sum_{s\geq 0}\frac{x^{s}(x+2)^{s}}{2^{s}k^{s}s!}=\sum_{s\geq
0}\sum_{r\geq 0}\binom{s}{r}2^{-r}\frac{x^{s+r}}{k^{s}s!}=\sum_{r\geq
0}\sum_{s\geq r}\frac{1}{r!(s-r)!}2^{-r}\frac{x^{s+r}}{k^{s}}$
$\displaystyle=\sum_{r\geq 0}\sum_{s\geq
2r}\frac{1}{r!(s-2r)!}2^{-r}\frac{x^{s}}{k^{s-r}}=\sum_{s\geq 0}\sum_{s/2\geq
r\geq
0}\frac{s!}{(2r)!(s-2r)!}k^{r}\frac{(2r)!}{2^{r}r!}\frac{x^{s}}{k^{s}s!}$
$\displaystyle=\sum_{m\geq 0}\eta_{k,m}\frac{x^{m}}{k^{m}m!}.$

Using these two equations together with the fact that

$\sum_{k\geq 1}\frac{1}{2k}\left(x_{k}^{2}+x_{2k}\right)=\sum_{k\geq
1}\left(\frac{x_{2k-1}^{2}}{2(2k-1)}+\frac{x_{2k}^{2}+2x_{2k}}{4k}\right)$

the right hand side of Proposition 3.4 becomes

(6) $\prod_{k\geq 1}\left(\sum_{m\geq
0}\frac{\eta_{k,m}}{k^{m}m!}x_{k}^{m}\right).$

Equating coefficients of (5) and (6) now gives the proposition. ∎

###  3.4. Rooted trees

In order to count forested graphs with automorphisms, we begin by counting
forests with automorphisms. In order to count forests with automorphisms, we
begin by counting trees with automorphisms, and in order to count trees with
automorphisms, we begin by counting rooted trees with automorphisms.

$\displaystyle\leavevmode\hbox to45.81pt{\vbox
to65.92pt{\pgfpicture\makeatletter\hbox{\hskip
17.21393pt\lower-52.73601pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }
{}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{{}}{{}}{{}}}{}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{}}{}{}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{{}}{{}}{{}}}{}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{}}{}{}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}{}{{}}{}{{}}{}\pgfsys@moveto{0.0pt}{11.38092pt}\pgfsys@stroke\pgfsys@invoke{
}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{
{}{}}{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{0.0pt}{11.38092pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}{} {} {} {} {}
{{}{}\pgfsys@moveto{-1.6pt}{9.78091pt}\pgfsys@lineto{1.6pt}{12.98093pt}\pgfsys@moveto{-1.6pt}{12.98093pt}\pgfsys@lineto{1.6pt}{9.78091pt}\pgfsys@stroke\pgfsys@invoke{
} }} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} {{}}{}{{}}{}{{}}
{}{}{}\pgfsys@moveto{0.0pt}{11.38092pt}\pgfsys@lineto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} {{}}{}{{}}{}{{}}
{}{}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{-11.38092pt}{-19.71278pt}\pgfsys@stroke\pgfsys@invoke{
} {{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.8pt}\pgfsys@invoke{
}\color[rgb]{0.390625,0.5625,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.390625,0.5625,1}\pgfsys@color@rgb@stroke{0.390625}{0.5625}{1}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0.390625}{0.5625}{1}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0.390625,0.5625,1}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{11.38092pt}{-19.71278pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{}}{}{{}}{}{{}}
{}{}{}\pgfsys@moveto{11.38092pt}{-19.71278pt}\pgfsys@lineto{0.0pt}{-39.42557pt}\pgfsys@stroke\pgfsys@invoke{
} {{}}{}{{}}{}{{}}
{}{}{}\pgfsys@moveto{11.38092pt}{-19.71278pt}\pgfsys@lineto{22.76184pt}{-39.42557pt}\pgfsys@stroke\pgfsys@invoke{
} {{}}{}{{}}{}{{{}}{}{}{}{}{}{}{}{}}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0.390625,0.5625,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.390625,0.5625,1}\pgfsys@color@rgb@stroke{0.390625}{0.5625}{1}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0.390625}{0.5625}{1}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0.390625,0.5625,1}\definecolor[named]{pgffillcolor}{rgb}{0.390625,0.5625,1}\pgfsys@color@rgb@fill{0.390625}{0.5625}{1}\pgfsys@invoke{
}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{1.7pt}{0.0pt}\pgfsys@curveto{1.7pt}{0.93889pt}{0.93889pt}{1.7pt}{0.0pt}{1.7pt}\pgfsys@curveto{-0.93889pt}{1.7pt}{-1.7pt}{0.93889pt}{-1.7pt}{0.0pt}\pgfsys@curveto{-1.7pt}{-0.93889pt}{-0.93889pt}{-1.7pt}{0.0pt}{-1.7pt}\pgfsys@curveto{0.93889pt}{-1.7pt}{1.7pt}{-0.93889pt}{1.7pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{}}{}{{}}{}{{{}}{}{}{}{}{}{}{}{}}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0.390625,0.5625,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.390625,0.5625,1}\pgfsys@color@rgb@stroke{0.390625}{0.5625}{1}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0.390625}{0.5625}{1}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0.390625,0.5625,1}\definecolor[named]{pgffillcolor}{rgb}{0.390625,0.5625,1}\pgfsys@color@rgb@fill{0.390625}{0.5625}{1}\pgfsys@invoke{
}{}\pgfsys@moveto{11.38092pt}{-19.71278pt}\pgfsys@moveto{13.08092pt}{-19.71278pt}\pgfsys@curveto{13.08092pt}{-18.7739pt}{12.31981pt}{-18.01279pt}{11.38092pt}{-18.01279pt}\pgfsys@curveto{10.44203pt}{-18.01279pt}{9.68092pt}{-18.7739pt}{9.68092pt}{-19.71278pt}\pgfsys@curveto{9.68092pt}{-20.65167pt}{10.44203pt}{-21.41278pt}{11.38092pt}{-21.41278pt}\pgfsys@curveto{12.31981pt}{-21.41278pt}{13.08092pt}{-20.65167pt}{13.08092pt}{-19.71278pt}\pgfsys@closepath\pgfsys@moveto{11.38092pt}{-19.71278pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{}}{}{{}}{}{{{}}{}{}{}{}{}{}{}{}}{{}}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{1,1,1}\pgfsys@color@gray@fill{1}\pgfsys@invoke{
}{}\pgfsys@moveto{-11.38092pt}{-19.71278pt}\pgfsys@moveto{-11.38092pt}{-19.71278pt}\pgfsys@curveto{-11.38092pt}{-19.71278pt}{-11.38092pt}{-19.71278pt}{-11.38092pt}{-19.71278pt}\pgfsys@curveto{-11.38092pt}{-19.71278pt}{-11.38092pt}{-19.71278pt}{-11.38092pt}{-19.71278pt}\pgfsys@curveto{-11.38092pt}{-19.71278pt}{-11.38092pt}{-19.71278pt}{-11.38092pt}{-19.71278pt}\pgfsys@curveto{-11.38092pt}{-19.71278pt}{-11.38092pt}{-19.71278pt}{-11.38092pt}{-19.71278pt}\pgfsys@closepath\pgfsys@moveto{-11.38092pt}{-19.71278pt}\pgfsys@fillstroke\pgfsys@invoke{
}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-13.88092pt}{-29.69022pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$1$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{}}{}{{}}{}{{{}}{}{}{}{}{}{}{}{}}{{}}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{1,1,1}\pgfsys@color@gray@fill{1}\pgfsys@invoke{
}{}\pgfsys@moveto{0.0pt}{-39.42557pt}\pgfsys@moveto{0.0pt}{-39.42557pt}\pgfsys@curveto{0.0pt}{-39.42557pt}{0.0pt}{-39.42557pt}{0.0pt}{-39.42557pt}\pgfsys@curveto{0.0pt}{-39.42557pt}{0.0pt}{-39.42557pt}{0.0pt}{-39.42557pt}\pgfsys@curveto{0.0pt}{-39.42557pt}{0.0pt}{-39.42557pt}{0.0pt}{-39.42557pt}\pgfsys@curveto{0.0pt}{-39.42557pt}{0.0pt}{-39.42557pt}{0.0pt}{-39.42557pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{-39.42557pt}\pgfsys@fillstroke\pgfsys@invoke{
}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-49.403pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$2$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{}}{}{{}}{}{{{}}{}{}{}{}{}{}{}{}}{{}}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{1,1,1}\pgfsys@color@gray@fill{1}\pgfsys@invoke{
}{}\pgfsys@moveto{22.76184pt}{-39.42557pt}\pgfsys@moveto{22.76184pt}{-39.42557pt}\pgfsys@curveto{22.76184pt}{-39.42557pt}{22.76184pt}{-39.42557pt}{22.76184pt}{-39.42557pt}\pgfsys@curveto{22.76184pt}{-39.42557pt}{22.76184pt}{-39.42557pt}{22.76184pt}{-39.42557pt}\pgfsys@curveto{22.76184pt}{-39.42557pt}{22.76184pt}{-39.42557pt}{22.76184pt}{-39.42557pt}\pgfsys@curveto{22.76184pt}{-39.42557pt}{22.76184pt}{-39.42557pt}{22.76184pt}{-39.42557pt}\pgfsys@closepath\pgfsys@moveto{22.76184pt}{-39.42557pt}\pgfsys@fillstroke\pgfsys@invoke{
}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{20.26184pt}{-49.403pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$3$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}=\leavevmode\hbox
to45.81pt{\vbox to65.92pt{\pgfpicture\makeatletter\hbox{\hskip
17.21393pt\lower-52.73601pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }
{}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{{}}{{}}{{}}}{}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{}}{}{}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{{}}{{}}{{}}}{}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{}}{}{}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}{}{{}}{}{{}}{}\pgfsys@moveto{0.0pt}{11.38092pt}\pgfsys@stroke\pgfsys@invoke{
}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{
{}{}}{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{0.0pt}{11.38092pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}} {} {} {} {}
{{}\pgfsys@moveto{-1.6pt}{9.78091pt}\pgfsys@lineto{1.6pt}{12.98093pt}\pgfsys@moveto{-1.6pt}{12.98093pt}\pgfsys@lineto{1.6pt}{9.78091pt}\pgfsys@stroke\pgfsys@invoke{
} }} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} {{}}{}{{}}{}{{}}
{}{}{}\pgfsys@moveto{0.0pt}{11.38092pt}\pgfsys@lineto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} {{}}{}{{}}{}{{}}
{}{}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{-11.38092pt}{-19.71278pt}\pgfsys@stroke\pgfsys@invoke{
} {{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.8pt}\pgfsys@invoke{
}\color[rgb]{0.390625,0.5625,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.390625,0.5625,1}\pgfsys@color@rgb@stroke{0.390625}{0.5625}{1}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0.390625}{0.5625}{1}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0.390625,0.5625,1}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{11.38092pt}{-19.71278pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{}}{}{{}}{}{{}}
{}{}{}\pgfsys@moveto{11.38092pt}{-19.71278pt}\pgfsys@lineto{0.0pt}{-39.42557pt}\pgfsys@stroke\pgfsys@invoke{
} {{}}{}{{}}{}{{}}
{}{}{}\pgfsys@moveto{11.38092pt}{-19.71278pt}\pgfsys@lineto{22.76184pt}{-39.42557pt}\pgfsys@stroke\pgfsys@invoke{
} {{}}{}{{}}{}{{{}}{}{}{}{}{}{}{}{}}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0.390625,0.5625,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.390625,0.5625,1}\pgfsys@color@rgb@stroke{0.390625}{0.5625}{1}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0.390625}{0.5625}{1}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0.390625,0.5625,1}\definecolor[named]{pgffillcolor}{rgb}{0.390625,0.5625,1}\pgfsys@color@rgb@fill{0.390625}{0.5625}{1}\pgfsys@invoke{
}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{1.5pt}{0.0pt}\pgfsys@curveto{1.5pt}{0.82843pt}{0.82843pt}{1.5pt}{0.0pt}{1.5pt}\pgfsys@curveto{-0.82843pt}{1.5pt}{-1.5pt}{0.82843pt}{-1.5pt}{0.0pt}\pgfsys@curveto{-1.5pt}{-0.82843pt}{-0.82843pt}{-1.5pt}{0.0pt}{-1.5pt}\pgfsys@curveto{0.82843pt}{-1.5pt}{1.5pt}{-0.82843pt}{1.5pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{}}{}{{}}{}{{{}}{}{}{}{}{}{}{}{}}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0.390625,0.5625,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.390625,0.5625,1}\pgfsys@color@rgb@stroke{0.390625}{0.5625}{1}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0.390625}{0.5625}{1}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0.390625,0.5625,1}\definecolor[named]{pgffillcolor}{rgb}{0.390625,0.5625,1}\pgfsys@color@rgb@fill{0.390625}{0.5625}{1}\pgfsys@invoke{
}{}\pgfsys@moveto{11.38092pt}{-19.71278pt}\pgfsys@moveto{12.88092pt}{-19.71278pt}\pgfsys@curveto{12.88092pt}{-18.88435pt}{12.20935pt}{-18.21278pt}{11.38092pt}{-18.21278pt}\pgfsys@curveto{10.55249pt}{-18.21278pt}{9.88092pt}{-18.88435pt}{9.88092pt}{-19.71278pt}\pgfsys@curveto{9.88092pt}{-20.54121pt}{10.55249pt}{-21.21278pt}{11.38092pt}{-21.21278pt}\pgfsys@curveto{12.20935pt}{-21.21278pt}{12.88092pt}{-20.54121pt}{12.88092pt}{-19.71278pt}\pgfsys@closepath\pgfsys@moveto{11.38092pt}{-19.71278pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{}}{}{{}}{}{{{}}{}{}{}{}{}{}{}{}}{{}}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{1,1,1}\pgfsys@color@gray@fill{1}\pgfsys@invoke{
}{}\pgfsys@moveto{-11.38092pt}{-19.71278pt}\pgfsys@moveto{-11.38092pt}{-19.71278pt}\pgfsys@curveto{-11.38092pt}{-19.71278pt}{-11.38092pt}{-19.71278pt}{-11.38092pt}{-19.71278pt}\pgfsys@curveto{-11.38092pt}{-19.71278pt}{-11.38092pt}{-19.71278pt}{-11.38092pt}{-19.71278pt}\pgfsys@curveto{-11.38092pt}{-19.71278pt}{-11.38092pt}{-19.71278pt}{-11.38092pt}{-19.71278pt}\pgfsys@curveto{-11.38092pt}{-19.71278pt}{-11.38092pt}{-19.71278pt}{-11.38092pt}{-19.71278pt}\pgfsys@closepath\pgfsys@moveto{-11.38092pt}{-19.71278pt}\pgfsys@fillstroke\pgfsys@invoke{
}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-13.88092pt}{-29.69022pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$1$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{}}{}{{}}{}{{{}}{}{}{}{}{}{}{}{}}{{}}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{1,1,1}\pgfsys@color@gray@fill{1}\pgfsys@invoke{
}{}\pgfsys@moveto{0.0pt}{-39.42557pt}\pgfsys@moveto{0.0pt}{-39.42557pt}\pgfsys@curveto{0.0pt}{-39.42557pt}{0.0pt}{-39.42557pt}{0.0pt}{-39.42557pt}\pgfsys@curveto{0.0pt}{-39.42557pt}{0.0pt}{-39.42557pt}{0.0pt}{-39.42557pt}\pgfsys@curveto{0.0pt}{-39.42557pt}{0.0pt}{-39.42557pt}{0.0pt}{-39.42557pt}\pgfsys@curveto{0.0pt}{-39.42557pt}{0.0pt}{-39.42557pt}{0.0pt}{-39.42557pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{-39.42557pt}\pgfsys@fillstroke\pgfsys@invoke{
}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-49.403pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$3$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{}}{}{{}}{}{{{}}{}{}{}{}{}{}{}{}}{{}}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{1,1,1}\pgfsys@color@gray@fill{1}\pgfsys@invoke{
}{}\pgfsys@moveto{22.76184pt}{-39.42557pt}\pgfsys@moveto{22.76184pt}{-39.42557pt}\pgfsys@curveto{22.76184pt}{-39.42557pt}{22.76184pt}{-39.42557pt}{22.76184pt}{-39.42557pt}\pgfsys@curveto{22.76184pt}{-39.42557pt}{22.76184pt}{-39.42557pt}{22.76184pt}{-39.42557pt}\pgfsys@curveto{22.76184pt}{-39.42557pt}{22.76184pt}{-39.42557pt}{22.76184pt}{-39.42557pt}\pgfsys@curveto{22.76184pt}{-39.42557pt}{22.76184pt}{-39.42557pt}{22.76184pt}{-39.42557pt}\pgfsys@closepath\pgfsys@moveto{22.76184pt}{-39.42557pt}\pgfsys@fillstroke\pgfsys@invoke{
}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{20.26184pt}{-49.403pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$2$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}},$
$\displaystyle\leavevmode\hbox to45.81pt{\vbox
to65.92pt{\pgfpicture\makeatletter\hbox{\hskip
17.21393pt\lower-52.73601pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }
{}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{{}}{{}}{{}}}{}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{}}{}{}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{{}}{{}}{{}}}{}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{}}{}{}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}{}{{}}{}{{}}{}\pgfsys@moveto{0.0pt}{11.38092pt}\pgfsys@stroke\pgfsys@invoke{
}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{
{}{}}{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{0.0pt}{11.38092pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}} {} {} {} {}
{{}\pgfsys@moveto{-1.6pt}{9.78091pt}\pgfsys@lineto{1.6pt}{12.98093pt}\pgfsys@moveto{-1.6pt}{12.98093pt}\pgfsys@lineto{1.6pt}{9.78091pt}\pgfsys@stroke\pgfsys@invoke{
} }} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} {{}}{}{{}}{}{{}}
{}{}{}\pgfsys@moveto{0.0pt}{11.38092pt}\pgfsys@lineto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} {{}}{}{{}}{}{{}}
{}{}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{-11.38092pt}{-19.71278pt}\pgfsys@stroke\pgfsys@invoke{
} {{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.8pt}\pgfsys@invoke{
}\color[rgb]{0.390625,0.5625,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.390625,0.5625,1}\pgfsys@color@rgb@stroke{0.390625}{0.5625}{1}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0.390625}{0.5625}{1}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0.390625,0.5625,1}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{11.38092pt}{-19.71278pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{}}{}{{}}{}{{}}
{}{}{}\pgfsys@moveto{11.38092pt}{-19.71278pt}\pgfsys@lineto{0.0pt}{-39.42557pt}\pgfsys@stroke\pgfsys@invoke{
} {{}}{}{{}}{}{{}}
{}{}{}\pgfsys@moveto{11.38092pt}{-19.71278pt}\pgfsys@lineto{22.76184pt}{-39.42557pt}\pgfsys@stroke\pgfsys@invoke{
} {{}}{}{{}}{}{{{}}{}{}{}{}{}{}{}{}}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0.390625,0.5625,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.390625,0.5625,1}\pgfsys@color@rgb@stroke{0.390625}{0.5625}{1}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0.390625}{0.5625}{1}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0.390625,0.5625,1}\definecolor[named]{pgffillcolor}{rgb}{0.390625,0.5625,1}\pgfsys@color@rgb@fill{0.390625}{0.5625}{1}\pgfsys@invoke{
}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{1.5pt}{0.0pt}\pgfsys@curveto{1.5pt}{0.82843pt}{0.82843pt}{1.5pt}{0.0pt}{1.5pt}\pgfsys@curveto{-0.82843pt}{1.5pt}{-1.5pt}{0.82843pt}{-1.5pt}{0.0pt}\pgfsys@curveto{-1.5pt}{-0.82843pt}{-0.82843pt}{-1.5pt}{0.0pt}{-1.5pt}\pgfsys@curveto{0.82843pt}{-1.5pt}{1.5pt}{-0.82843pt}{1.5pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{}}{}{{}}{}{{{}}{}{}{}{}{}{}{}{}}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0.390625,0.5625,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.390625,0.5625,1}\pgfsys@color@rgb@stroke{0.390625}{0.5625}{1}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0.390625}{0.5625}{1}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0.390625,0.5625,1}\definecolor[named]{pgffillcolor}{rgb}{0.390625,0.5625,1}\pgfsys@color@rgb@fill{0.390625}{0.5625}{1}\pgfsys@invoke{
}{}\pgfsys@moveto{11.38092pt}{-19.71278pt}\pgfsys@moveto{12.88092pt}{-19.71278pt}\pgfsys@curveto{12.88092pt}{-18.88435pt}{12.20935pt}{-18.21278pt}{11.38092pt}{-18.21278pt}\pgfsys@curveto{10.55249pt}{-18.21278pt}{9.88092pt}{-18.88435pt}{9.88092pt}{-19.71278pt}\pgfsys@curveto{9.88092pt}{-20.54121pt}{10.55249pt}{-21.21278pt}{11.38092pt}{-21.21278pt}\pgfsys@curveto{12.20935pt}{-21.21278pt}{12.88092pt}{-20.54121pt}{12.88092pt}{-19.71278pt}\pgfsys@closepath\pgfsys@moveto{11.38092pt}{-19.71278pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{}}{}{{}}{}{{{}}{}{}{}{}{}{}{}{}}{{}}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{1,1,1}\pgfsys@color@gray@fill{1}\pgfsys@invoke{
}{}\pgfsys@moveto{-11.38092pt}{-19.71278pt}\pgfsys@moveto{-11.38092pt}{-19.71278pt}\pgfsys@curveto{-11.38092pt}{-19.71278pt}{-11.38092pt}{-19.71278pt}{-11.38092pt}{-19.71278pt}\pgfsys@curveto{-11.38092pt}{-19.71278pt}{-11.38092pt}{-19.71278pt}{-11.38092pt}{-19.71278pt}\pgfsys@curveto{-11.38092pt}{-19.71278pt}{-11.38092pt}{-19.71278pt}{-11.38092pt}{-19.71278pt}\pgfsys@curveto{-11.38092pt}{-19.71278pt}{-11.38092pt}{-19.71278pt}{-11.38092pt}{-19.71278pt}\pgfsys@closepath\pgfsys@moveto{-11.38092pt}{-19.71278pt}\pgfsys@fillstroke\pgfsys@invoke{
}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-13.88092pt}{-29.69022pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$2$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{}}{}{{}}{}{{{}}{}{}{}{}{}{}{}{}}{{}}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{1,1,1}\pgfsys@color@gray@fill{1}\pgfsys@invoke{
}{}\pgfsys@moveto{0.0pt}{-39.42557pt}\pgfsys@moveto{0.0pt}{-39.42557pt}\pgfsys@curveto{0.0pt}{-39.42557pt}{0.0pt}{-39.42557pt}{0.0pt}{-39.42557pt}\pgfsys@curveto{0.0pt}{-39.42557pt}{0.0pt}{-39.42557pt}{0.0pt}{-39.42557pt}\pgfsys@curveto{0.0pt}{-39.42557pt}{0.0pt}{-39.42557pt}{0.0pt}{-39.42557pt}\pgfsys@curveto{0.0pt}{-39.42557pt}{0.0pt}{-39.42557pt}{0.0pt}{-39.42557pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{-39.42557pt}\pgfsys@fillstroke\pgfsys@invoke{
}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-49.403pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$1$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{}}{}{{}}{}{{{}}{}{}{}{}{}{}{}{}}{{}}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{1,1,1}\pgfsys@color@gray@fill{1}\pgfsys@invoke{
}{}\pgfsys@moveto{22.76184pt}{-39.42557pt}\pgfsys@moveto{22.76184pt}{-39.42557pt}\pgfsys@curveto{22.76184pt}{-39.42557pt}{22.76184pt}{-39.42557pt}{22.76184pt}{-39.42557pt}\pgfsys@curveto{22.76184pt}{-39.42557pt}{22.76184pt}{-39.42557pt}{22.76184pt}{-39.42557pt}\pgfsys@curveto{22.76184pt}{-39.42557pt}{22.76184pt}{-39.42557pt}{22.76184pt}{-39.42557pt}\pgfsys@curveto{22.76184pt}{-39.42557pt}{22.76184pt}{-39.42557pt}{22.76184pt}{-39.42557pt}\pgfsys@closepath\pgfsys@moveto{22.76184pt}{-39.42557pt}\pgfsys@fillstroke\pgfsys@invoke{
}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{20.26184pt}{-49.403pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$3$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}},$
$\displaystyle\leavevmode\hbox to45.81pt{\vbox
to65.92pt{\pgfpicture\makeatletter\hbox{\hskip
17.21393pt\lower-52.73601pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }
{}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{{}}{{}}{{}}}{}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{}}{}{}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{{}}{{}}{{}}}{}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{}}{}{}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}{}{{}}{}{{}}{}\pgfsys@moveto{0.0pt}{11.38092pt}\pgfsys@stroke\pgfsys@invoke{
}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{
{}{}}{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{0.0pt}{11.38092pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}} {} {} {} {}
{{}\pgfsys@moveto{-1.6pt}{9.78091pt}\pgfsys@lineto{1.6pt}{12.98093pt}\pgfsys@moveto{-1.6pt}{12.98093pt}\pgfsys@lineto{1.6pt}{9.78091pt}\pgfsys@stroke\pgfsys@invoke{
} }} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} {{}}{}{{}}{}{{}}
{}{}{}\pgfsys@moveto{0.0pt}{11.38092pt}\pgfsys@lineto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} {{}}{}{{}}{}{{}}
{}{}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{-11.38092pt}{-19.71278pt}\pgfsys@stroke\pgfsys@invoke{
} {{}}{}{{}}{}{{}} {}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.8pt}\pgfsys@invoke{
}\color[rgb]{0.390625,0.5625,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.390625,0.5625,1}\pgfsys@color@rgb@stroke{0.390625}{0.5625}{1}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0.390625}{0.5625}{1}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0.390625,0.5625,1}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{11.38092pt}{-19.71278pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{}}{}{{}}{}{{}}
{}{}{}\pgfsys@moveto{11.38092pt}{-19.71278pt}\pgfsys@lineto{0.0pt}{-39.42557pt}\pgfsys@stroke\pgfsys@invoke{
} {{}}{}{{}}{}{{}}
{}{}{}\pgfsys@moveto{11.38092pt}{-19.71278pt}\pgfsys@lineto{22.76184pt}{-39.42557pt}\pgfsys@stroke\pgfsys@invoke{
} {{}}{}{{}}{}{{{}}{}{}{}{}{}{}{}{}}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0.390625,0.5625,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.390625,0.5625,1}\pgfsys@color@rgb@stroke{0.390625}{0.5625}{1}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0.390625}{0.5625}{1}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0.390625,0.5625,1}\definecolor[named]{pgffillcolor}{rgb}{0.390625,0.5625,1}\pgfsys@color@rgb@fill{0.390625}{0.5625}{1}\pgfsys@invoke{
}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@moveto{1.5pt}{0.0pt}\pgfsys@curveto{1.5pt}{0.82843pt}{0.82843pt}{1.5pt}{0.0pt}{1.5pt}\pgfsys@curveto{-0.82843pt}{1.5pt}{-1.5pt}{0.82843pt}{-1.5pt}{0.0pt}\pgfsys@curveto{-1.5pt}{-0.82843pt}{-0.82843pt}{-1.5pt}{0.0pt}{-1.5pt}\pgfsys@curveto{0.82843pt}{-1.5pt}{1.5pt}{-0.82843pt}{1.5pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{}}{}{{}}{}{{{}}{}{}{}{}{}{}{}{}}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0.390625,0.5625,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.390625,0.5625,1}\pgfsys@color@rgb@stroke{0.390625}{0.5625}{1}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0.390625}{0.5625}{1}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0.390625,0.5625,1}\definecolor[named]{pgffillcolor}{rgb}{0.390625,0.5625,1}\pgfsys@color@rgb@fill{0.390625}{0.5625}{1}\pgfsys@invoke{
}{}\pgfsys@moveto{11.38092pt}{-19.71278pt}\pgfsys@moveto{12.88092pt}{-19.71278pt}\pgfsys@curveto{12.88092pt}{-18.88435pt}{12.20935pt}{-18.21278pt}{11.38092pt}{-18.21278pt}\pgfsys@curveto{10.55249pt}{-18.21278pt}{9.88092pt}{-18.88435pt}{9.88092pt}{-19.71278pt}\pgfsys@curveto{9.88092pt}{-20.54121pt}{10.55249pt}{-21.21278pt}{11.38092pt}{-21.21278pt}\pgfsys@curveto{12.20935pt}{-21.21278pt}{12.88092pt}{-20.54121pt}{12.88092pt}{-19.71278pt}\pgfsys@closepath\pgfsys@moveto{11.38092pt}{-19.71278pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{}}{}{{}}{}{{{}}{}{}{}{}{}{}{}{}}{{}}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{1,1,1}\pgfsys@color@gray@fill{1}\pgfsys@invoke{
}{}\pgfsys@moveto{-11.38092pt}{-19.71278pt}\pgfsys@moveto{-11.38092pt}{-19.71278pt}\pgfsys@curveto{-11.38092pt}{-19.71278pt}{-11.38092pt}{-19.71278pt}{-11.38092pt}{-19.71278pt}\pgfsys@curveto{-11.38092pt}{-19.71278pt}{-11.38092pt}{-19.71278pt}{-11.38092pt}{-19.71278pt}\pgfsys@curveto{-11.38092pt}{-19.71278pt}{-11.38092pt}{-19.71278pt}{-11.38092pt}{-19.71278pt}\pgfsys@curveto{-11.38092pt}{-19.71278pt}{-11.38092pt}{-19.71278pt}{-11.38092pt}{-19.71278pt}\pgfsys@closepath\pgfsys@moveto{-11.38092pt}{-19.71278pt}\pgfsys@fillstroke\pgfsys@invoke{
}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-13.88092pt}{-29.69022pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$3$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{}}{}{{}}{}{{{}}{}{}{}{}{}{}{}{}}{{}}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{1,1,1}\pgfsys@color@gray@fill{1}\pgfsys@invoke{
}{}\pgfsys@moveto{0.0pt}{-39.42557pt}\pgfsys@moveto{0.0pt}{-39.42557pt}\pgfsys@curveto{0.0pt}{-39.42557pt}{0.0pt}{-39.42557pt}{0.0pt}{-39.42557pt}\pgfsys@curveto{0.0pt}{-39.42557pt}{0.0pt}{-39.42557pt}{0.0pt}{-39.42557pt}\pgfsys@curveto{0.0pt}{-39.42557pt}{0.0pt}{-39.42557pt}{0.0pt}{-39.42557pt}\pgfsys@curveto{0.0pt}{-39.42557pt}{0.0pt}{-39.42557pt}{0.0pt}{-39.42557pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{-39.42557pt}\pgfsys@fillstroke\pgfsys@invoke{
}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-49.403pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$1$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{}}{}{{}}{}{{{}}{}{}{}{}{}{}{}{}}{{}}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{1,1,1}\pgfsys@color@gray@fill{1}\pgfsys@invoke{
}{}\pgfsys@moveto{22.76184pt}{-39.42557pt}\pgfsys@moveto{22.76184pt}{-39.42557pt}\pgfsys@curveto{22.76184pt}{-39.42557pt}{22.76184pt}{-39.42557pt}{22.76184pt}{-39.42557pt}\pgfsys@curveto{22.76184pt}{-39.42557pt}{22.76184pt}{-39.42557pt}{22.76184pt}{-39.42557pt}\pgfsys@curveto{22.76184pt}{-39.42557pt}{22.76184pt}{-39.42557pt}{22.76184pt}{-39.42557pt}\pgfsys@curveto{22.76184pt}{-39.42557pt}{22.76184pt}{-39.42557pt}{22.76184pt}{-39.42557pt}\pgfsys@closepath\pgfsys@moveto{22.76184pt}{-39.42557pt}\pgfsys@fillstroke\pgfsys@invoke{
}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{20.26184pt}{-49.403pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$2$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}},$ $1$$2$$3$ Figure 1.
All admissible rooted trees with $3$ leaves, i.e. all elements of
$\mathcal{R}[3]$. The first three rooted trees have two internal vertices each
and the fourth has one internal vertex. Internal edges are colored in blue.
The automorphism groups of the first, second and third rooted tree are
generated by the transpositions $(2,3)$, $(1,3)$ and $(1,2)$ respectively. The
automorphism group of the fourth rooted tree is the full symmetric group
$\operatorname{{\mathfrak{S}}}_{3}$, i.e. it includes all permutations of the
labels.

Let $\mathcal{R}$ be the species of leaf-labeled admissible rooted trees
$\rho$, i.e. all internal vertices of $\rho$ must have valence at least $3$
and $\mathcal{R}[n]$ is the set of all such rooted trees with $n$ leaves. The
elements of $\mathcal{R}[3]$ are depicted in Figure 1. The rooted tree
$\rho_{0}$ with one root, one leaf and one 1-cell has no internal vertices so
satisfies the definition, but it plays a special role so we call it the
special rooted tree. $\mathcal{AR}$ is then the species of pairs
$(\rho,\alpha)$, where $\rho\in\mathcal{R}$ and
$\alpha\in{\operatorname{Aut}}(\rho).$ Recall that an automorphism of a tree
is determined by what it does to the leaves. So, for a rooted tree
$\rho\in\mathcal{R}[n]$ we can (and will) identify the group
${\operatorname{Aut}}(\rho)\leq\operatorname{{\mathfrak{S}}}_{n}$ with the
usual simplicial automorphisms of the tree $\rho$. To each pair
$(\rho,\alpha)\in\mathcal{AR}$ we assign the weight
$\omega(\rho,\alpha)=(-1)^{v_{\alpha}(\rho)},$ where $v_{\alpha}(\rho)$ is the
number of $\alpha$-orbits of internal vertices. The special rooted tree
$\rho_{0}$ has only the identity automorphism, and the pair
$(\rho_{0},\operatorname{id})$ has weight $(-1)^{0}=1$. The associated
generating function

$\displaystyle{\mathbf{R}}({\overline{x}})$ $\displaystyle=\sum_{n\geq
1}\frac{1}{n!}\sum_{(\rho,\alpha)\in\mathcal{AR}[n]}(-1)^{v_{\alpha}(\rho)}x^{\alpha}$

is the _Frobenius characteristic of rooted trees_. The first few terms are

$\displaystyle{\mathbf{R}}({\overline{x}})$
$\displaystyle=x_{1}-\frac{1}{2}(x_{1}^{2}+x_{2})+\frac{1}{6}3(x_{1}^{3}+x_{1}x_{2})-\frac{1}{6}(x_{1}^{3}+3x_{1}x_{2}+2x_{3})+\ldots$

The first term comes from the special rooted tree $\rho_{0}$. The second term
comes from the rooted tree with one internal vertex and two leaves branching
from it. We have two automorphisms that either switch the leaf-labels or do
not. The third and fourth terms in this sum come from the rooted trees in
Figure 1 and their automorphisms.

######  Remark 3.7.

The name _Frobenius characteristic_ comes from an interpretation of these
generating functions in the context of the representation theory of the
symmetric group: We can think of ${\mathbf{R}}({\overline{x}})$ as an element
of the ring of _symmetric functions_ and each homogeneous part of
${\mathbf{R}}({\overline{x}})$ as the image of a certain representation of the
symmetric group under the Frobenius characteristic map. These representations
are the vector spaces generated by the elements of $\mathcal{R}[n]$ with the
action of $\operatorname{{\mathfrak{S}}}_{n}$ which alternates with
$(-1)^{v_{\alpha}(\rho)}$ as above. However, in this paper we will not make
use of this representation theoretical interpretation of these objects.

The next proposition shows that the characteristic
${\mathbf{R}}({\overline{x}})$ has a remarkably simple form.

######  Proposition 3.8.

$\displaystyle{\mathbf{R}}({\overline{x}})=\sum_{n\geq
1}\frac{\mu(n)}{n}\log(1+x_{n}),$

where $\mu$ is the Möbius function.

###### Proof.

The formula will be established by relating pairs $(\rho,\alpha)$ recursively
to pairs $(\Phi,\gamma)$ consisting of a set of rooted trees $\Phi$ and an
automorphism $\gamma\in{\operatorname{Aut}}(\Phi)$.

Let $\Phi$ be a collection of two or more admissible rooted trees and
$\gamma\in{\operatorname{Aut}}(\Phi)$. Set
$\omega(\Phi,\gamma)=(-1)^{v_{\gamma}(\Phi)}$. We can form a new admissible
rooted tree $\rho_{\Phi}$ by gluing the roots of the trees in $\Phi$ together
and growing a new root from the resulting vertex. The resulting rooted tree
has one new internal vertex, which is fixed by any automorphism, and at least
$2$ leaves. The natural map
${\operatorname{Aut}}(\Phi)\to{\operatorname{Aut}}(\rho_{\Phi})$ is a
bijection, so we will use the same name $\gamma$, and we have
$\omega(\rho_{\Phi},\gamma)=-\omega(\Phi,\gamma)$. The only pair
$(\rho,\alpha)$ which cannot be obtained in this way is
$(\rho_{0},\operatorname{id})$, so

(7) $\displaystyle{\mathbf{R}}({\overline{x}})$
$\displaystyle=x_{1}-\sum_{k\geq 2}\sum_{n\geq
k}\frac{1}{n!}\sum_{(\Phi,\gamma)\in\mathcal{A}{\operatorname{Set}}^{k}(\mathcal{R})[n]}(-1)^{v_{\gamma}(\Phi)}x^{\gamma},$

Proposition 3.2 tells us

$\displaystyle{\mathbf{R}}_{\operatorname{Set}}({\overline{x}},{\overline{y}})$
$\displaystyle=\sum_{k\geq 0}\sum_{n\geq
k}\frac{1}{n!}\sum_{(\Phi,\gamma)\in\mathcal{A}{\operatorname{Set}}^{k}(\mathcal{R})[n]}(-1)^{v_{\gamma}(\Phi)}x^{\gamma}y^{\gamma_{\Phi}}=\exp\left(\sum_{k\geq
1}y_{k}\frac{{\mathbf{R}}({\overline{x}}_{[k]})}{k}\right),$

Setting $y_{k}=1$ for all $k$ and subtracting the terms with $k=0$ or $k=1$
gives the summation term in Eq. (7) above, i.e.

(8) $\displaystyle{\mathbf{R}}({\overline{x}})$
$\displaystyle=x_{1}-\left(\exp\left(\sum_{k\geq
1}\frac{{\mathbf{R}}({\overline{x}}_{[k]})}{k}\right)-1-{\mathbf{R}}({\overline{x}}_{[1]})\right).$

Since ${\mathbf{R}}({\overline{x}}_{[1]})={\mathbf{R}}({\overline{x}})$ this
gives $\sum_{k\geq 1}{{\mathbf{R}}({\overline{x}}_{[k]})/k}=\log(1+x_{1})$ and
because ${\overline{x}}_{[k]}=(x_{k},x_{2k},\ldots)$, we also have
$\sum_{k\geq 1}{{\mathbf{R}}({\overline{x}}_{[kn]})/k}=\log(1+x_{n})$ for all
$n\geq 1$. Multiplying both sides of this equation with $\mu(n)/n$, summing
over $n\geq 1$ and using the defining recursion of the Möbius function results
in the statement. ∎

###  3.5. Unrooted trees

We next use this generating function for rooted trees (weighted by the parity
of internal vertex orbits) to find the Frobenius characteristic
${\mathbf{V}}({\overline{x}})$ for the species $\mathcal{T}$ of unrooted
admissible trees, weighted by the parity of internal edge-orbits. Here
$\mathcal{T}[n]$ consists of labeled trees with $n$ leaves, and to a pair
$(t,\alpha)\in\mathcal{AT},$ where $t\in\mathcal{T}$ and
$\alpha\in{\operatorname{Aut}}(t),$ we assign the weight
$\omega(t,\alpha)=(-1)^{e_{\alpha}(t)}$, where $e_{\alpha}(t)$ is the number
of internal edge-orbits of $\alpha$ in $t$, and define

(9) $\displaystyle{\mathbf{V}}({\overline{x}})=\sum_{n\geq
3}\frac{1}{n!}\sum_{(t,\alpha)\in\mathcal{AT}[n]}(-1)^{e_{\alpha}(t)}x^{\alpha},$

######  Proposition 3.9.

$\displaystyle{\mathbf{V}}({\overline{x}})$
$\displaystyle=x_{1}+\frac{x_{1}^{2}}{2}-\frac{x_{2}}{2}-(1+x_{1}){\mathbf{R}}({\overline{x}}).$

###### Proof.

Suppose $t$ is an unrooted tree and $\alpha\in{\operatorname{Aut}}(t)$. The
set of points fixed by $\alpha$ is connected, so is either a subtree
$t^{\alpha}$ or an isolated point in the middle of an internal edge.

Suppose first that there is a fixed subtree $t^{\alpha}$. For each internal
vertex $v\in t^{\alpha}$, we can think of $(t,\alpha)$ as a collection $\Phi$
of at least $3$ rooted trees, with $v$ as their root, and of $\alpha$ as an
automorphism of $\Phi$. Note that
$e_{\alpha}(t)=v_{\alpha}(t)-1=v_{\alpha}(\Phi)$. Using Proposition 3.2 and
setting $y_{k}=1$ for all $k$, the generating functions of such collections
$\Phi$ is

$\displaystyle\exp\left(\sum_{k\geq
1}\frac{{\mathbf{R}}({\overline{x}}_{[k]})}{k}\right)-1-{\mathbf{R}}({\overline{x}}_{[1]})-\frac{{\mathbf{R}}({\overline{x}}_{[2]})}{2}-\frac{{\mathbf{R}}({\overline{x}}_{[1]})^{2}}{2},$

where we have subtracted the terms that correspond to collections with fewer
than 3 trees. By Eq. (8) in the proof of Proposition 3.8 this is the same as

(10) $\displaystyle
x_{1}-{\mathbf{R}}({\overline{x}})-\frac{{\mathbf{R}}({\overline{x}}_{[2]})}{2}-\frac{{\mathbf{R}}({\overline{x}})^{2}}{2}.$

If we place a root in the middle of an internal edge of $t^{\alpha}$, we can
view $t$ as a pair $\\{\rho_{1},\rho_{2}\\}$ of rooted trees and $\alpha$ as a
pair $\\{\alpha_{1},\alpha_{2}\\}$ of automorphisms of $\rho_{1}$ and
$\rho_{2}$ respectively. Since $e$ is not adjacent to a leaf neither rooted
tree is the special rooted tree. The generating function of such rooted trees
is therefore

(11) $\displaystyle\frac{({\mathbf{R}}({\overline{x}})-x_{1})^{2}}{2}.$

Here we have
$e_{\alpha}(t)=v_{\alpha}(t)-1=v_{\alpha}(\\{\rho_{1},\rho_{2}\\})$. The sum
of expressions (10) and (11) counts the pair $(t,\alpha)$ multiple times, once
for each internal vertex of $t^{\alpha}$ with sign $(-1)^{e_{\alpha}(t)},$ and
once for each internal edge of $t^{\alpha}$ with the opposite sign. Since
$t^{\alpha}$ has one more internal vertex than internal edge, this sum leaves
us with exactly one contribution from each $(t,\alpha)$, with sign
$(-1)^{e_{\alpha}(t)}$, i.e. the sum gives the contribution to
${\mathbf{V}}({\overline{x}})$ from all such pairs.

We still have to account for pairs $(t,\alpha)$ with no fixed vertices, i.e.
the only fixed point is at the midpoint of an internal edge. The tree $t$ can
then be viewed as the union of two identical rooted trees
$\\{\rho_{1},\rho_{2}\\}$ rooted at this midpoint, which are exchanged by
$\alpha$. By Lemma 3.3 these are counted by
${\mathbf{R}}({\overline{x}}_{[2]})/2$. Since in this case
$e_{\alpha}(t)=v_{\alpha}(\\{\rho_{1},\rho_{2}\\})$, these contribute

(12)
$\displaystyle\frac{{\mathbf{R}}({\overline{x}}_{[2]})}{2}-\frac{x_{2}}{2}$

to ${\mathbf{V}}({\overline{x}})$, where we have subtracted the term
corresponding to the interval since that is not an admissible unrooted tree.
The sum of formulas (10), (11) and (12) now has one term for each pair
$(t,\alpha),$ weighted by $(-1)^{e_{\alpha}(t)}$, i.e. the sum is equal to
${\mathbf{V}}({\overline{x}})$. ∎

As an immediate corollary of Proposition 3.9 and Proposition 3.8 we have

######  Corollary 3.10.

$\displaystyle{\mathbf{V}}({\overline{x}})$
$\displaystyle=x_{1}+\frac{x_{1}^{2}}{2}-\frac{x_{2}}{2}-(1+x_{1})\sum_{k\geq
1}\frac{\mu(k)}{k}\log(1+x_{k}).$

Using $\log(1+x)=\sum_{n\geq 1}(-1)^{n+1}x^{n}/n$, and the definition of the
Möbius function, we can expand this power series. As $\mu(1)=1$,
$\mu(2)=\mu(3)=-1$ and $\mu(4)=0$, the first coefficients are

$\displaystyle{\mathbf{V}}({\overline{x}})$
$\displaystyle=x_{1}+\frac{x_{1}^{2}}{2}-\frac{x_{2}}{2}$
$\displaystyle\phantom{=}-(1+x_{1})\left(\left(x_{1}-\frac{x_{1}^{2}}{2}+\frac{x_{1}^{3}}{3}-\frac{x_{1}^{4}}{4}+\ldots\right)-\frac{1}{2}\left(x_{2}-\frac{x_{2}^{2}}{2}+\ldots\right)-\frac{1}{3}\left(x_{3}+\ldots\right)+\ldots\right)$
$\displaystyle=\frac{x_{1}^{3}}{6}+\frac{x_{1}x_{2}}{2}+\frac{x_{3}}{3}-\frac{x_{1}^{4}}{12}-\frac{x_{2}^{2}}{4}+\frac{x_{1}x_{3}}{3}+\ldots$

where we omitted terms of total degree higher than $4$. As expected there are
no terms of degree smaller than $3$, as such terms would correspond to trees
with fewer than $3$ leaves.

We recall from Section 3.2 that setting ${\overline{x}}=(x,0,0,\ldots)$ in the
Frobenius characteristic $\mathbf{V}({\overline{x}})$ for unrooted trees
recovers the generating function $V(x)$ for unrooted trees $t$ weighted by
$(-1)^{e(t)}$, where $e(t)$ is the number of (internal) edges of $t$, i.e.

(13) $V(x)=x+\frac{x^{2}}{2}-(1+x)\log(1+x).$

For a detailed exposition of this formula see [11].

As forests are just collections of trees, Proposition 3.2 gives us the
following expression for the alternating cycle index series for the species
$\mathcal{F}$ of forests:

(14)
$\displaystyle{\mathbf{V}}_{\operatorname{Set}}({\overline{x}},{\overline{y}})=\sum_{n}\frac{1}{n!}\sum_{(\Phi,\gamma)\in\mathcal{AF}[n]}(-1)^{e_{\gamma}(\Phi)}{x^{\gamma}}y^{\gamma_{\Phi}}=\exp\left(\sum_{k\geq
1}y_{k}\frac{{\mathbf{V}}({\overline{x}}_{[k]})}{k}\right).$

###  3.6. Forested graphs

What we want to do with these forests is to glue their leaves together in
pairs to form admissible graphs (which we can only do if there is an even
number of leaves). We also want to keep track of the Euler characteristic of
the resulting graph $G$; this is the number of trees in the forest minus half
the total the number of leaves. It is equivalent to keep track of
$-2\chi(G)=\\#\\{\text{leaves}\\}-2\\#\\{\text{trees}\\}$ (which is always a
positive integer) so we mark this number with a new variable $u$, and define
the Frobenius characteristic of admissible forests

(15) $\displaystyle\begin{aligned} {\mathbf{F}}(u,{\overline{x}})&=\sum_{s\geq
0}\frac{1}{s!}\sum_{(\Phi,\gamma)\in\mathcal{AF}[s]}(-1)^{e_{\gamma}(\Phi)}x^{\gamma}u^{s-2k(\Phi)},\end{aligned}$

where $\mathcal{F}$ is the species of forests and $k(\Phi)$ is the number of
trees in the forest $\Phi$.

######  Proposition 3.11.

$\displaystyle{\mathbf{F}}(u,{\overline{x}})=\exp\left(\sum_{k\geq
1}u^{-2k}\frac{{\mathbf{V}}((u\cdot{\overline{x}})_{[k]})}{k}\right),$

where ${\mathbf{V}}((u\cdot{\overline{x}})_{[k]})$ means that we replace each
variable $x_{i}$ in ${\mathbf{V}}({\overline{x}})$ with $u^{ki}x_{ki}$.

By Eq. (9) the lowest term of ${\mathbf{V}}(u\cdot x)$ is of order $u^{3}$,
and hence the lowest term of ${\mathbf{V}}((u\cdot{\overline{x}})_{[k]})$ is
of order $u^{3k}$. Hence, ${\mathbf{F}}(u,{\overline{x}})$ is the exponential
of a power series in only positive powers of $u$.

###### Proof.

Starting with the definition of
${\mathbf{V}}_{\operatorname{Set}}({\overline{x}},{\overline{y}})$, the
substitution $x_{i}\mapsto u^{i}x_{i}$ sends $x^{\lambda}$ to
$u^{|\lambda|}x^{\lambda}$, and the substitution $y_{i}\mapsto u^{-2i}$ sends
$y^{\gamma_{\Phi}}$ to $u^{2k(\Phi)}$ where $k(\Phi)$ is the number of trees
in $\Phi$. Doing both substitutions gives ${\mathbf{F}}(u,{\overline{x}})$. ∎

######  Proposition 3.12.

$\displaystyle\sum_{\lambda}\eta_{\lambda}[u^{2n}x^{\lambda}]{\mathbf{F}}(u,{\overline{x}})=\operatorname{\widehat{e}}_{n},$

where we sum over all integer partitions $\lambda$ and $\eta_{\lambda}$ is the
number of matchings that commute with a permutation of cycle type $\lambda$.
The sum is finite since $[u^{2n}x^{\lambda}]{\mathbf{F}}(u,{\overline{x}})=0$
unless $2n\leq|\lambda|\leq 6n$.

$1$$2$$3$$4$$5$$6$$7$$8$$9$$10$$1$$2$$3$$4$$5$$6$$7$$8$$9$$10$ Figure 2. A
forest with automorphism $\gamma=(13)(24)(57)(68)(9\,10)$ and matching
$\iota=(13)(25)(47)(68)(9\,10)$ that commutes with $\gamma$, corresponds to a
forested graph with the automorphism that flips the graph over the horizontal
axis.

###### Proof.

Our generating function ${\mathbf{F}}(u,{\overline{x}})$ counts forests
together with automorphisms, i.e. if we set

$\displaystyle\mathcal{F}_{r,\lambda}=\\{(\Phi,\gamma)|\Phi\hbox{ has
}|\lambda|\hbox{ leaves and }k=\frac{|\lambda|-r}{2}\hbox{ components and
}\gamma\hbox{ has cycle type }\lambda\\},$

then

$\displaystyle[u^{r}x^{\lambda}]{\mathbf{F}}(u,{\overline{x}})=\frac{1}{|\lambda|!}\sum_{(\Phi,\gamma)\in\mathcal{F}_{r,\lambda}}(-1)^{e_{\gamma}(\Phi)}.$

Because a nonempty forest has at least one component, we have
$[u^{r}x^{\lambda}]{\mathbf{F}}(u,{\overline{x}})=0$ if $|\lambda|<r$, and
because every connected component of an admissible forest must have at least
three leaves we have $[u^{r}x^{\lambda}]{\mathbf{F}}(u,{\overline{x}})=0$ if
$|\lambda|>3r$. In particular, for a given $r$ there are only finitely many
integer partitions $\lambda$ such that
$[u^{r}x^{\lambda}]{\mathbf{F}}(u,{\overline{x}})$ is nonzero, i.e. the terms
in the sum

$\sum_{\lambda}\eta_{\lambda}[u^{r}x^{\lambda}]{\mathbf{F}}({\overline{x}},u)$

are only nonzero when $r\leq|\lambda|\leq 3r$.

Let $M_{r}\subset\operatorname{{\mathfrak{S}}}_{r}$ be the set of fixed-point
free involutions on the set $\\{1,\ldots,r\\}$ and
$\mathcal{IF}_{r,\lambda}=\\{(\Phi,\gamma,\iota)|(\Phi,\gamma)\in\mathcal{F}_{r,\lambda}\hbox{
and }\iota\in M_{r}\hbox{ commutes with }\gamma\\}.$ Then
$\eta_{\lambda}[u^{r}x^{\lambda}]{\mathbf{F}}({\overline{x}},u)$ is equal to
$1/|\lambda|!$ times the sum of elements in $\mathcal{IF}_{r,\lambda}$
weighted by $(-1)^{e_{\gamma}(t)}$. We can make a forested graph equipped with
an automorphism from an element
$(\Phi,\gamma,\iota)\in\mathcal{IF}_{r,\lambda}$ by using $\iota$ to identify
the leaves of $\Phi$ in pairs, provided $r=2n$ is even (see Figure 2). The
result will be a forested graph $(G,\Phi_{0})$ with $\chi(G)=-n$, where
$\Phi_{0}$ is the subforest of $G$ consisting of just the internal edges and
vertices of $\Phi$, and the leaves of $\Phi$ have become (labeled) half-edges
in $G\setminus\Phi_{0}$. This gives us a one-to-one correspondence between
elements of $\mathcal{IF}_{2n,\lambda}$ and pairs $((G,\Phi_{0}),\gamma)$
consisting of a forested graph $(G,\Phi_{0})$ with $\chi(G)=-n$ and an
automorphism $\gamma\in{\operatorname{Aut}}(G,\Phi_{0})$, where the half-edges
of $G\setminus\Phi_{0}$ are labeled by $\\{1,\ldots,|\lambda|\\}$. The
symmetric group $\operatorname{{\mathfrak{S}}}_{|\lambda|}$ acts on
$\mathcal{IF}_{2n,\lambda}$ by permuting the labels. The stabilizer of
$((G,\Phi_{0}),\gamma)$ is ${\operatorname{Aut}}_{\gamma}(G,\Phi_{0})$, the
automorphisms of $(G,\Phi_{0})$ that commute with $\gamma$, and the orbit is
the unlabeled pair $[G,\Phi_{0}]$ together with a conjugacy class $[\gamma]$
of the automorphism group ${\operatorname{Aut}}(G,\Phi_{0})$. If we now take
the sum over all integer partitions $\lambda$, the orbit-stabilizer theorem
gives

$\displaystyle\sum_{\lambda}\eta_{\lambda}[u^{2n}x^{\lambda}]{\mathbf{F}}({\overline{x}},u)$
$\displaystyle=\frac{1}{|\lambda|!}\sum_{\lambda}\sum_{(\Phi,\gamma,\iota)\in\mathcal{IF}_{2n,\lambda}}(-1)^{e_{\gamma}(\Phi)}$
$\displaystyle=\sum_{\begin{subarray}{c}[G,\Phi_{0}]\\\
\chi(G)=-n\end{subarray}}\sum_{[\gamma]\in{\operatorname{Aut}}(G,\Phi_{0})}\frac{1}{|{\operatorname{Aut}}_{\gamma}(G,\Phi_{0})|}(-1)^{e_{\gamma}(\Phi_{0})}$
$\displaystyle=\sum_{\begin{subarray}{c}[G,\Phi_{0}]\\\
\chi(G)=-n\end{subarray}}\frac{1}{|{\operatorname{Aut}}(G,\Phi_{0})|}\sum_{\gamma\in{\operatorname{Aut}}(G,\Phi_{0})}(-1)^{e_{\gamma}(\Phi_{0})}.$

The second step uses the orbit stabilizer theorem again on the centralizer
${\operatorname{Aut}}_{\gamma}(G,\Phi_{0})$. Since the last line is the
definition of $\operatorname{\widehat{e}}_{n}$, the proposition is proved. ∎

The following theorem summarizes the steps needed for computing
$e({\operatorname{Out}}(F_{n}))$ for a given $n$.

######  Theorem 3.13.

For fixed $n\geq 2$, the numbers
$e({\operatorname{Out}}(F_{2})),\ldots,e({\operatorname{Out}}(F_{n}))$ can be
computed by the following steps:

  1. (1)

Calculate ${\mathbf{V}}({\overline{x}})$ up to homogeneous degree $6(n-1)$ in
${\overline{x}}$ using the formula in Corollary 3.10.

  2. (2)

Calculate the coefficients $[u^{2k}x^{\lambda}]{\mathbf{F}}(u,{\overline{x}})$
from ${\mathbf{V}}({\overline{x}})$ using the formula in Proposition 3.11 for
all pairs $k,\lambda$ with $k\leq n-1$ and $\lambda$ a partition of size $\leq
6k$.

  3. (3)

Calculate the numbers $\eta_{\lambda}$ using Corollary 3.5 for all $\lambda$
of size $\leq 6(n-1)$.

  4. (4)

Calculate the numbers
$\operatorname{\widehat{e}}_{0},\ldots,\operatorname{\widehat{e}}_{n-1}$ using
the formula

$\operatorname{\widehat{e}}_{k}=\sum_{\lambda}\eta_{\lambda}[u^{2k}x^{\lambda}]{\mathbf{F}}(u,{\overline{x}})$

from Proposition 3.12. Recall that this is a finite sum: the terms are nonzero
only for partitions $\lambda$ of size $2k\leq|\lambda|\leq 6k$.

  5. (5)

Recover $e({\operatorname{Out}}(F_{n}))$ from
$\operatorname{\widehat{e}}_{0},\ldots,\operatorname{\widehat{e}}_{n-1}$ using
the recursive formula in Corollary 2.6.

The most demanding part of the computation is the expansion of the generating
function ${\mathbf{F}}(u,{\overline{x}})$ for the Frobenius characteristic of
admissible forests. We used Jos Vermaseren’s FORM programming language [28] to
compute this expansion up to an appropriate order and calculated
$e({\operatorname{Out}}(F_{n}))$ for $n\leq 15$. The result is listed in
Appendix A. We report on an optimized program with which the numbers
$e({\operatorname{Out}}(F_{n}))$ were computed for all $n\leq 100$ in a
separate publication [9].

##  4\. Asymptotic behavior of $e({\operatorname{Out}}(F_{n}))$

###  4.1. Overview of the proof of Theorem 1.1

In this section, we will prove Theorem 1.1, which gives the asymptotic
behavior of the numbers $e({\operatorname{Out}}(F_{n}))$. The argument goes
through the following steps: In Section 4.2, we will show that
$\operatorname{\widehat{e}}_{n}$ and $e({\operatorname{Out}}(F_{n}))$ have the
same leading asymptotic behavior. Hence, it is sufficient to prove the
asymptotic expression for $\operatorname{\widehat{e}}_{n}$ that we state in
Theorem 4.2. The proof of Theorem 4.2 relies partly on asymptotic results from
[10]. In that paper we defined power series $T(\hbar)$ and
$\widehat{T}(\hbar)$ with coefficients $\chi_{n}$ and
$\operatorname{\widehat{\chi}}_{n}$ respectively by

(16) $\displaystyle\widehat{T}(\hbar)=\sum_{n\geq
1}\operatorname{\widehat{\chi}}_{n}\hbar^{n}=\exp\left(\sum_{n\geq
1}\chi_{n}\hbar^{n}\right)=\exp(T(\hbar)),$

where $\chi_{n}=\chi({\operatorname{Out}}(F_{n+1}))$ is the rational Euler
characteristic of ${\operatorname{Out}}(F_{n+1}).$ We recall the precise
formula for the asymptotic behavior of $\operatorname{\widehat{\chi}}_{n}$
from [10] in Proposition 4.3. We next find a new expression for the numbers
$\operatorname{\widehat{e}}_{n}$ that explicitly involves the generating
function $\widehat{T}(\hbar)$. For this we need a slight extension of the
combinatorial discussion from Section 3 that we give in Section 4.3. The new
expression for $\operatorname{\widehat{e}}_{n}$ is then derived in Section 4.4
and summarized in Theorem 4.10.

Theorem 4.10 expresses the number $\operatorname{\widehat{e}}_{n}$ as a sum
over partitions. We eventually show that the contribution to this sum from
many of these partitions is negligible for large $n$, and that the remaining
terms have the same asymptotic behavior as certain numbers $P_{n}$, which we
define in Eq. (31). We begin by proving some elementary estimates in Section
4.5. In Section 4.6, we use these together with some further estimates to
determine the asymptotic behavior of the numbers $P_{n}$ (see Proposition
4.25). It remains to prove that the numbers $P_{n}$ have the same asymptotic
behavior as the numbers $\operatorname{\widehat{e}}_{n}$ (stated precisely in
Proposition 4.18). This technical part of the argument also involves the
estimates from Section 4.5 as well as many further estimates. The argument is
split between Sections 4.7 and 4.8 and finishes the proof of Theorem 1.1.

###  4.2. Precise asymptotic statements

To discuss the asymptotic behavior of sequences we use the following standard
conventions.

######  Notation.

Let $\\{c_{n}\\}$ be a sequence defined for all but finitely many positive
integers $n$. The set $\mathcal{O}(c_{n})$ consists of all such sequences
$\\{a_{n}\\}$ for which
$\limsup_{n\rightarrow\infty}\left|a_{n}/c_{n}\right|<\infty.$ The notation
$a_{n}=b_{n}+\mathcal{O}(c_{n})$ means $a_{n}-b_{n}\in\mathcal{O}(c_{n})$.
Recall that the notation $a_{n}\sim b_{n}$ means
$\lim_{n\rightarrow\infty}a_{n}/b_{n}=1.$

To describe the asymptotic behavior of the numbers
$\operatorname{\widehat{e}}_{n}$ we will use the $\Gamma$ function, which is
defined by $\Gamma(x)=\int_{0}^{\infty}z^{x-1}e^{-z}\mathrm{d}z$ for all
$x>0$. At integer arguments it agrees with the factorial $n!=\Gamma(n+1)$. By
Stirling’s formula, we have $\Gamma(x)\sim\sqrt{2\pi}x^{x-\frac{1}{2}}e^{-x}$
[1, Eq. (3.9)], i.e. $\Gamma(x)$ grows more than exponentially. Explicitly, we
will quantify the asymptotic behavior of $\operatorname{\widehat{e}}_{n}$
using the sequences $B_{n}$ and $L_{n}$ defined by

$\displaystyle B_{n}$
$\displaystyle=-\frac{1}{\sqrt{2\pi}}\frac{\Gamma\left(n-\frac{1}{2}\right)}{\log^{2}n}$
and $\displaystyle L_{n}$ $\displaystyle=\frac{\log n}{\log\log n}.$

It follows from Stirling’s formula that

######  Lemma 4.1.

$B_{n}\sim-n^{n}e^{-n}/(n\log^{2}n).$

###### Proof.

$B_{n}/(-n^{n}e^{-n}/(n\log^{2}n))\sim
e^{\frac{1}{2}}(1-\frac{1}{2n})^{n-1}\sim 1$, where we used
$\lim_{n\rightarrow\infty}(1+\frac{x}{n})^{n}=e^{x}$. ∎

The remainder of the paper is devoted to proving the following theorem.

######  Theorem 4.2.

$\operatorname{\widehat{e}}_{n}$ has asymptotic behavior

$\operatorname{\widehat{e}}_{n}=e^{-\frac{1}{4}}B_{n}+\mathcal{O}(B_{n}/L_{n}).$

Note that $\lim_{n\rightarrow\infty}L_{n}=\infty$, so it follows that
$\operatorname{\widehat{e}}_{n}\sim e^{-\frac{1}{4}}B_{n}$. By applying
Stirling’s formula, i.e. Lemma 4.1, we moreover find that
$\operatorname{\widehat{e}}_{n}\sim-e^{-\frac{1}{4}}n^{n}e^{-n}/(n\log^{2}n)$.

The following statement from previous work by the authors is needed to prove
this theorem.

######  Proposition 4.3 (Proposition 8.1 and Lemma 8.7 in [10]).

$\operatorname{\widehat{\chi}}_{n}$, defined in Eq. (16), has the asymptotic
behavior,

$\operatorname{\widehat{\chi}}_{n}=B_{n}+\mathcal{O}(B_{n}/L_{n}).$

###### Proof.

We just have to substitute the asymptotic formula for the numbers $v_{k}$ in
[10, Lemma 8.7] (where we uncover an obvious typo: there should be no minus
sign in [10, equation (8.7)]) into the formula for
$\operatorname{\widehat{\chi}}_{n}$ from [10, Proposition 8.1]. ∎

As an immediate corollary we get

######  Corollary 4.4.

There exists a constant $C$, such that

$\displaystyle|\operatorname{\widehat{\chi}}_{n}|\leq
C~{}\Gamma\left(n-\frac{1}{2}\right)\text{ for all $n\geq 1$.}$

###### Proof.

This follows from
$\mathcal{O}(\operatorname{\widehat{\chi}}_{n})=\mathcal{O}(B_{n})=\mathcal{O}\left(\Gamma(n-\frac{1}{2})/\log^{2}n\right)\subset\mathcal{O}\left(\Gamma(n-\frac{1}{2})\right).$
Hence,
$\lim_{n\rightarrow\infty}|\operatorname{\widehat{\chi}}_{n}/\Gamma(n-\frac{1}{2})|$
is finite and as $\Gamma(n-\frac{1}{2})>0$ for $n\geq 1$,
$\operatorname{\widehat{\chi}}_{n}/\Gamma(n-\frac{1}{2})$ stays bounded. ∎

We also showed that the numbers $\chi_{n}$ have the same asymptotic behavior
as $\operatorname{\widehat{\chi}}_{n}$ [10, Proposition 8.6]. A slight
modification of the proof of this given in [10] gives the following statement.

######  Proposition 4.5.

The numbers $e({\operatorname{Out}}(F_{n+1}))$ have the same asymptotic
behavior as $\operatorname{\widehat{e}}_{n}$.

###### Proof.

Lemma 8.8 of [10] gives a criterion for showing the asymptotic behavior of the
coefficients of a series $\sum a_{n}x^{n}$ agrees with with that of the
coefficients of $\exp(\sum a_{n}x^{n})$. The proof of Proposition 8.6 in [10]
immediately following Lemma 8.8 applies almost verbatim to show that the
coefficients $\operatorname{e}_{n}$ defined by
$\sum_{n=1}^{\infty}\operatorname{e}_{n}\hbar^{n}=\log\left(\sum_{n=0}^{\infty}\operatorname{\widehat{e}}_{n}\hbar^{n}\right)$
have the same asymptotic behavior as $\operatorname{\widehat{e}}_{n}$, i.e.
$\operatorname{e}_{n}=e^{-\frac{1}{4}}B_{n}+\mathcal{O}(B_{n}/L_{n}).$ By
Corollary 2.6 of the present paper,
$e({\operatorname{Out}}(F_{n+1}))=\operatorname{e}_{n}+\sum_{\begin{subarray}{c}d\mid
n,d\neq 1\end{subarray}}\frac{\mu(d)}{d}\operatorname{e}_{n/d}$. As $n$ has
fewer than $n$ divisors and $|\mu(n)|\leq 1$, the sums
$\sum_{\begin{subarray}{c}d\mid n,d\neq
1\end{subarray}}\frac{\mu(d)}{d}\operatorname{e}_{n/d}$ form a sequence in
$\mathcal{O}(n\operatorname{e}_{n/2})=\mathcal{O}(nB_{n/2})\subset\mathcal{O}(n\Gamma(n/2-\frac{1}{2}))\subset\mathcal{O}(B_{n}/L_{n}),$
showing that $e({\operatorname{Out}}(F_{n+1}))$ also has the same asymptotic
behavior as $\operatorname{\widehat{e}}_{n}$. ∎

###### Proof of Theorem 1.1.

By Theorem 4.2 and Proposition 4.5

$e({\operatorname{Out}}(F_{n+1}))=e^{-\frac{1}{4}}B_{n}+\mathcal{O}(B_{n}/L_{n}).$

The result follows by applying Lemma 4.1 and from $\log(n-1)\sim\log n$ and
$(1-1/n)^{n-1}\sim e^{-1}$. ∎

######  Remark 4.6.

In fact, we prove a stronger statement than Theorem 1.1 which quantifies the
error term in the asymptotic behavior. By Propositions 4.3 and 4.5, we have
for large $n$

$e({\operatorname{Out}}(F_{n}))/\chi({\operatorname{Out}}(F_{n}))={e^{-\frac{1}{4}}}+\mathcal{O}(\log\log
n/\log n).$

The error term $\mathcal{O}(\log\log n/\log n)$ above appears to be too
pessimistic. Based on the computations of $e({\operatorname{Out}}(F_{n}))$ up
to $n=100$ from [9] and empirical comparison with
$\chi({\operatorname{Out}}(F_{n}))$, we conjecture

$e({\operatorname{Out}}(F_{n}))/\chi({\operatorname{Out}}(F_{n}))=e^{-\frac{1}{4}}\left(1-\frac{29}{32n}+\mathcal{O}\left(\frac{1}{n^{2}}\right)\right).$

###  4.3. Forested graphs with legs

In Section 3, we have only needed to consider forested graphs $(G,\Phi)$ such
that $G$ has no univalent vertices. However, to determine the asymptotic
behavior of the integral Euler characteristic we will need to do a finer
analysis, which involves studying pairs $(G,\Phi)$ where $G$ is allowed to
have univalent (but not bivalent) vertices, while $\Phi$ is not allowed to
contain any edges adjacent to univalent vertices. We call the edges of $G$
adjacent to univalent vertices legs and the pairs $(G,\Phi)$ forested graphs
with legs. In this subsection we point out that a minor modification of the
counting methods from Section 3 counts these more general graphs.

Recall that admissible graphs are constructed by pairing the leaves of an
admissible forest $\Phi$. The internal edges of the forest then become a
subforest $\Phi_{0}$ of the admissible graph $G$. To get the original forest
back you cut all the 1-cells of $G$ that are not in $\Phi_{0}$; the half-edges
that result are attached to the leaves of the original forest $\Phi$. If the
graph $G$ has legs we are not allowing the subforest $\Phi$ to contain them so
they must be cut, which results in components with one 0-cell and one half-
edge. These are not admissible trees, so we will call these special
components, and mark them with a new variable $w$. A forest which is allowed
to have both admissible and special components will be called an extended
forest. Matching the leaves of an extended forest results in a graph with a
univalent vertex for each special component.

Let ${\mathcal{F}}^{\star}$ denote the species of extended forests, and define
$F^{\star}(x,u,w)$ to be

$\displaystyle F^{\star}(x,u,w)$
$\displaystyle=\sum_{\Phi\in{\mathcal{F}}^{\star}}(-1)^{e(\Phi)}u^{s(\Phi)-2k(\Phi)}w^{j(\Phi)}\frac{x^{s(\Phi)}}{s(\Phi)!},$

where $e(\Phi)$ is the number of edges of $\Phi$, $s(\Phi)$ is the number of
leaves, $k(\Phi)$ is the total number of components and $j(\Phi)$ is the
number of special components, i.e. $[u^{r}x^{s}w^{j}]F^{\star}(u,x,w)$ is the
edge-weighted count of forests with $s$ leaves and $(s-r)/2$ components, of
which $j$ are special.

Recall that $V(x)$ is the generating function for unrooted trees, weighted by
the parity of their internal edges (see Eq. (13)).

######  Proposition 4.7.

$F^{\star}(u,x,w)=\exp(u^{-1}wx+u^{-2}V(ux)).$

###### Proof.

A special component has $1$ leaf, $0$ edges and $1$ component (which is
special!), so the term $u^{-1}wx$ accounts for special components. The term
$u^{-2}V(ux)$ accounts for admissible trees as before. Exponentiating gives
the generating function for collections, as per Lemma 3.1. ∎

In [10] we showed that the rational Euler characteristic
$\chi_{n}=\chi({\operatorname{Out}}(F_{n+1}))$ is given by

$\chi_{n}=\sum_{\begin{subarray}{c}[G,\Phi]\\\ G\,\mathrm{connected}\\\
\chi(G)=-n\end{subarray}}\frac{(-1)^{e(\Phi)}}{|{\operatorname{Aut}}(G,\Phi)|},$

where the sum is over isomorphism classes $[G,\Phi]$ of connected forested
graphs of Euler characteristic $-n$. We defined the corresponding generating
function, $T(\hbar)=\sum_{n\geq 1}\chi_{n}\hbar^{n}$, in Eq. (16).

In [10], we also defined an analogous generating function $T(\hbar,w)$ for
isomorphism classes $[G,\Phi]$ of connected forested graphs with legs, which
are weighted in the same way as in the formula above. Here the variable $w$
marks the legs of $G$, i.e. $[\hbar^{n}w^{s}]T(\hbar,w)$ is the weighted sum
over isomorphism classes $[G,\Phi]$ such that $G$ is connected, has Euler
characteristic $-n$, and has $s$ legs. We can relate $T(\hbar,w)$ to the
generating function $F^{\star}(u,x,w)$:

######  Lemma 4.8.

$\displaystyle\sum_{m\geq
0}(2m-1)!![x^{2m}]F^{\star}(u,x,w)=\exp\left(\frac{u^{-2}w^{2}}{2}+T(u^{2},w)\right).$

###### Proof.

The coefficient of $u^{2n}w^{s}$ in $(2m-1)!![x^{2m}]F^{\star}(u,x,w)$ gives
the weighted count of forested graphs with $s$ legs and $\chi=-n$ that can be
made by gluing the leaves of extended forests $\Phi$ with $2m$ leaves. Adding
up over all $m$ gives the count of all forested graphs with $s$ legs and
$\chi=-n$. The term $\exp(T(u^{2},w))$ counts forests, but misses components
with a single internal vertex and two legs. Those are taken care of by adding
the term $(u^{-2}w^{2})/2$ to $T(u^{2},w)$. ∎

Finally, we recall from [10] that $T(\hbar,w)$ and $T(\hbar)$ are related in
the following way.

######  Proposition 4.9 ([10], Proposition 3.1).

$T(\hbar,w)=T(\hbar
e^{-w})+\frac{w}{2}+\hbar^{-1}\left(e^{w}-1-w-\frac{w^{2}}{2}\right).$

Here $T(\hbar e^{-w})$ accounts for connected forested graphs with negative
Euler characteristic, the term $\frac{w}{2}$ accounts for those with Euler
characteristic zero, and the last term accounts for trees.

###  4.4. Relating the integral and rational Euler characteristics

Recall from Eq. (1) that each triple $[G,\Phi,\alpha]$ consisting of a
forested graph with $\chi(G)=-n$ and an automorphism $\alpha$ preserving
$\Phi$ contributes to $\operatorname{\widehat{e}}_{n}$. Restricting the sum to
only triples with $\alpha=\hbox{id}$ gives the exponentiated rational Euler
characteristic $\widehat{\chi}_{n}$ from Eq. (16). To prove Theorem 4.2 we
will exploit the fact that we already know the asymptotics of
$\widehat{\chi}_{n}$. We will eventually find that the contributions to
$\operatorname{\widehat{e}}_{n}$ from triples $[G,\Phi,\alpha]$ such that
$\alpha$ fixes $\Phi$ and has order at most $2$ dominate the asymptotics of
$\operatorname{\widehat{e}}_{n}$. In this subsection we manipulate our formula
for $\operatorname{\widehat{e}}_{n}$ to isolate these contributions, and in
the following subsections we will prove that they dominate by bounding the
relative size of the remaining terms.

We start with the formula

$\displaystyle\operatorname{\widehat{e}}_{n}=\sum_{\lambda}\eta_{\lambda}[u^{2n}x^{\lambda}]{\mathbf{F}}(u,{\overline{x}})$

from Proposition 3.12. From Proposition 3.11 we have an expression for
${\mathbf{F}}(u,{\overline{x}})$, so

$\displaystyle\operatorname{\widehat{e}}_{n}$
$\displaystyle=\sum_{\lambda}\eta_{\lambda}[u^{2n}x^{\lambda}]\exp\left(\sum_{k\geq
1}u^{-2k}\frac{{\mathbf{V}}((u\cdot{\overline{x}})_{[k]})}{k}\right).$

Recall that a permutation is called a derangement if it has no fixed points;
this is equivalent to saying that the corresponding cycle type has no parts of
size 1, so we call it a deranged partition. An integer partition $\lambda$ is
equivalent to a pair $(m,\delta)$ where $m$ is the number of parts of size $1$
in $\lambda$ and $\delta$ is the deranged partition obtained from $\lambda$ by
removing all parts of size $1$.

To make an admissible graph with an automorphism from a pair $(\Phi,\alpha)$
consisting of a forest and an automorphism, leaves of $\Phi$ that are permuted
by $\alpha$ in cycles of equal lengths must be paired with each other; in
particular, leaves that are fixed by $\alpha$ must be paired with each other.
By first pairing the fixed leaves we can reduce the expression for
$\operatorname{\widehat{e}}_{n}$ above to a sum over deranged partitions.
Specifically, if there are $2m$ fixed leaves there are $(2m-1)!!$ ways to pair
them, so if $\lambda=(2m,\delta)$ then $\eta_{\lambda}=(2m-1)!!\eta_{\delta}$
and

$\displaystyle\begin{aligned}
\operatorname{\widehat{e}}_{n}&=\sum_{\delta}\eta_{\delta}[u^{2n}x^{\delta}]\sum_{m=0}^{\infty}(2m-1)!![x_{1}^{2m}]\exp\left(\sum_{k\geq
1}u^{-2k}\frac{{\mathbf{V}}((u\cdot{\overline{x}})_{[k]})}{k}\right)\\\
&=\sum_{\delta}\eta_{\delta}[u^{2n}x^{\delta}]\exp\left(\sum_{k\geq
2}u^{-2k}\frac{{\mathbf{V}}((u\cdot{\overline{x}})_{[k]})}{k}\right)\sum_{m=0}^{\infty}(2m-1)!![x_{1}^{2m}]\exp\left(u^{-2}{\mathbf{V}}(u\cdot{\overline{x}})\right),\end{aligned}$

where we sum only over deranged integer partitions $\delta$. (Note that the
variable $x_{1}$ does not appear in the power series
${\mathbf{V}}((u\cdot{\overline{x}})_{[k]})$ for $k\geq 2$.) The expression in
the first exponential will not change in what follows, so we give it a name:

$\mathbf{h}_{1}(u,{\overline{x}})=\sum_{k\geq
2}u^{-2k}\frac{{\mathbf{V}}((u\cdot{\overline{x}})_{[k]})}{k}=\sum_{k\geq
2}\frac{u^{k}x^{3}_{k}}{6k}+\frac{u^{k}x_{k}{x_{2k}}}{2k}+\frac{u^{k}x_{3k}}{3k}-\frac{u^{2k}x_{k}^{4}}{12k}+\ldots$

and our expression reads

(17) $\displaystyle\begin{aligned}
\operatorname{\widehat{e}}_{n}=\sum_{\delta}\eta_{\delta}[u^{2n}x^{\delta}]\exp(\mathbf{h}_{1}(u,{\overline{x}}))\sum_{m=0}^{\infty}(2m-1)!![x_{1}^{2m}]\exp\left(u^{-2}{\mathbf{V}}(u\cdot{\overline{x}})\right).\end{aligned}$

Next we look more closely at the term
$\exp(u^{-2}\mathbf{V}(u\cdot{\overline{x}})).$ We first separate out the
contribution to ${\mathbf{V}}({\overline{x}})$ of pairs $(t,\alpha)$ with
$\alpha=\operatorname{id}$. This is obtained by setting $x_{i}=0$ in
${\mathbf{V}}({\overline{x}})$ for all $i\geq 2$; recall that this gives us
the generating function $V(x_{1})$ for trees without automorphisms. By
Corollary 3.10 we have

(18) $\displaystyle\begin{aligned}
{\mathbf{V}}({\overline{x}})&=x_{1}+\frac{x_{1}^{2}}{2}-\frac{x_{2}}{2}-(1+x_{1}){\mathbf{R}}({\overline{x}})\\\
&=x_{1}+\frac{x_{1}^{2}}{2}-\frac{x_{2}}{2}-(1+x_{1})\sum_{k\geq
1}\frac{\mu(k)}{k}\log(1+x_{k})\\\
&=x_{1}+\frac{x_{1}^{2}}{2}-(1+x_{1})\log(1+x_{1})-\frac{x_{2}}{2}-(1+x_{1})\sum_{k\geq
2}\frac{\mu(k)}{k}\log(1+x_{k})\\\
&=V(x_{1})-\frac{x_{2}}{2}+(1+x_{1}){\mathbf{W}}({\overline{x}}),\end{aligned}$

where ${\mathbf{W}}({\overline{x}})=-\sum_{k\geq
2}\frac{\mu(k)}{k}\log(1+x_{k})=-{\mathbf{R}}({\overline{x}})+(1+x_{1})\log(1+x_{1})$.
Note that ${\mathbf{W}}({\overline{x}})$ counts rooted trees with
automorphisms that do not fix any leaves, in particular it does not involve
the variable $x_{1}$. By Eq. (18) we have

$\displaystyle\exp\left(u^{-2}{\mathbf{V}}(u\cdot{\overline{x}})\right)$
$\displaystyle=\exp\left(u^{-2}\left(V(ux_{1})-u^{2}\frac{x_{2}}{2}+(1+ux_{1}){\mathbf{W}}(u\cdot{\overline{x}})\right)\right)$
$\displaystyle=\exp\left(\big{(}u^{-2}V(ux_{1})+u^{-1}x_{1}{\mathbf{W}}(u\cdot{\overline{x}})\big{)}+u^{-2}\left({\mathbf{W}}(u\cdot{\overline{x}})-u^{2}\frac{x_{2}}{2}\right)\right).$

By Proposition 4.7, $\exp\left(u^{-2}V(ux)+u^{-1}wx\right)=F^{\star}(u,x,w),$
where $[u^{2n}x^{s}w^{j}]F^{\star}(u,x,w)$ counts forests with $j$ special
components and $s$ leaves that glue up to graphs with $\chi=-n$ and $j$ legs.
Note that ${\mathbf{W}}(u\cdot{\overline{x}})$ can be interpreted as a power
series in $u$ whose coefficients are polynomials in $x_{1},x_{2},\ldots$. This
power series has no constant coefficient, so if $f(w)$ is another power
series, then the composition $f({\mathbf{W}}(u\cdot{\overline{x}}))$ is
convergent in the usual power series topology. Substituting $x_{1}$ for $x$
and ${\mathbf{W}}(u\cdot{\overline{x}})$ for $w$ in Proposition 4.7, our
formula for $\exp\left(u^{-2}{\mathbf{V}}(u\cdot{\overline{x}}\right))$
becomes

$\displaystyle\exp\left(u^{-2}{\mathbf{V}}(u\cdot{\overline{x}})\right)=F^{\star}(u,x_{1},{\mathbf{W}}(u\cdot{\overline{x}}))\exp\left(u^{-2}\left({\mathbf{W}}(u\cdot{\overline{x}})-u^{2}\frac{x_{2}}{2}\right)\right).$

Substituting the above into Eq. (17) gives the following expression:

(21)
$\displaystyle\begin{gathered}\operatorname{\widehat{e}}_{n}=\sum_{\delta}\eta_{\delta}[u^{2n}x^{\delta}]\exp(\mathbf{h}_{1}(u,{\overline{x}}))\times\\\
\sum_{m=0}^{\infty}(2m-1)!![x_{1}^{m}]F^{\star}(u,x_{1},{\mathbf{W}}(u\cdot{\overline{x}}))\exp\left(u^{-2}\left({\mathbf{W}}(u\cdot{\overline{x}})-u^{2}\frac{x_{2}}{2}\right)\right).\end{gathered}$

Now recall the statement of Lemma 4.8

$\displaystyle\sum_{m\geq
0}(2m-1)!![x^{2m}]F^{\star}(u,x,w)=\exp\left(\frac{u^{-2}w^{2}}{2}+T(u^{2},w)\right).$

After substituting $x_{1}$ for $x$ and ${\mathbf{W}}(u\cdot{\overline{x}})$
for $w$ in this statement, Eq. (21) becomes

(24)
$\displaystyle\begin{gathered}\operatorname{\widehat{e}}_{n}=\sum_{\delta}\eta_{\delta}[u^{2n}x^{\delta}]\exp(\mathbf{h}_{1}(u,{\overline{x}}))\times\\\
\exp\left(\frac{u^{-2}{\mathbf{W}}(u\cdot{\overline{x}})^{2}}{2}+T(u^{2},{\mathbf{W}}(u\cdot{\overline{x}}))+u^{-2}\left({\mathbf{W}}(u\cdot{\overline{x}})-u^{2}\frac{x_{2}}{2}\right)\right)\end{gathered}$

By Proposition 4.9 we have a relation between $T(\hbar,w)$ and $T(\hbar)$.
Substituting $u^{2}$ for $\hbar$ and ${\mathbf{W}}(u\cdot{\overline{x}})$ for
$w$, this relation becomes

$T(u^{2},{\mathbf{W}}(u\cdot{\overline{x}}))=T(u^{2}e^{-{\mathbf{W}}(u\cdot{\overline{x}})})+\frac{{\mathbf{W}}(u\cdot{\overline{x}})}{2}+u^{-2}\left(e^{{\mathbf{W}}(u\cdot{\overline{x}})}-1-{\mathbf{W}}(u\cdot{\overline{x}})-\frac{{\mathbf{W}}(u\cdot{\overline{x}})^{2}}{2}\right).$

Substituting this into Eq. (24) and simplifying turns our expression for
$\operatorname{\widehat{e}}_{n}$ into

(26)
$\displaystyle\begin{gathered}\sum_{\delta}\eta_{\delta}[u^{2n}x^{\delta}]\exp\left(\mathbf{h}_{1}(u,{\overline{x}})+T\left(u^{2}e^{-{\mathbf{W}}(u\cdot{\bar{x})}}\right)+\frac{{\mathbf{W}}(u\cdot{\overline{x}})}{2}+u^{-2}\left(e^{{\mathbf{W}}(u\cdot\bar{x})}-1-u^{2}\frac{x_{2}}{2}\right)\right).\end{gathered}$

Recall from Eq. (16) that $\widehat{T}(\hbar)=\exp(T(\hbar))$ and set

$\displaystyle\mathbf{h}_{2}(u,{\overline{x}})$
$\displaystyle=\frac{{\mathbf{W}}(u\cdot\overline{x})}{2}$
$\displaystyle\mathbf{h}_{3}(u,{\overline{x}})$
$\displaystyle=u^{-2}\left(e^{{\mathbf{W}}(u\cdot\bar{x})}-1-u^{2}\frac{x_{2}}{2}\right).$

We record Equation (26) formally as a theorem:

######  Theorem 4.10.

$\operatorname{\widehat{e}}_{n}=\sum_{\delta}\eta_{\delta}[u^{2n}x^{\delta}]\widehat{T}(u^{2}e^{-{\mathbf{W}}(u\cdot\bar{x})}){\mathbf{H}}(u,{\overline{x}}),$

where the sum is over all deranged integer partitions $\delta$ and

$\mathbf{H}(u,{\overline{x}})=\exp\left(\mathbf{h}_{1}(u,{\overline{x}})+\mathbf{h}_{2}(u,{\overline{x}})+\mathbf{h}_{3}(u,{\overline{x}})\right).$

$v$$w$$(G,\Phi,\alpha)$$1$$2$$3$$4$$5$$6$$G^{\prime}$$G{{}^{\prime\prime}}$$(\overline{G},\overline{\Phi})$
Figure 3. Reducing a forested graph $(G,\Phi)$ with automorphism $\alpha$
interchanging $v$ and $w$ to a forested graph with legs. The graph
$G^{\prime}$ is obtained by cutting edges not in $G^{\alpha}$ or $\Phi$, and
$\alpha$ induces the derangement $(14)(23)(56)$. The next graph
$G^{\prime\prime}$ replaces each set of trees at a vertex of $G^{\alpha}$ by a
single orange leg, and the final graph $\overline{G}$ results from contracting
all separating edges in $G^{\prime\prime}$ that are not legs.

Note that $\mu(2)=\mu(3)=-1$ and $\mu(4)=0$, hence the first few terms of
${\mathbf{W}}(u\cdot\bar{x})$ are

$\displaystyle{\mathbf{W}}(u\cdot\bar{x})=-\sum_{k\geq
2}\frac{\mu(k)}{k}\log(1+u^{k}x_{k})$
$\displaystyle=\frac{1}{2}\left(u^{2}x_{2}-\frac{u^{4}x_{2}^{2}}{2}\right)+\frac{u^{3}x_{3}}{3}+\ldots$
$\displaystyle=\frac{u^{2}x_{2}}{2}+\frac{u^{3}x_{3}}{3}-\frac{u^{4}x_{2}^{2}}{4}+\ldots$

where higher powers of $u$ were omitted. It follows that
$\mathbf{h}_{2}(u,{\overline{x}})={{\mathbf{W}}(u\cdot\bar{x})/2}$ and

$\mathbf{h}_{3}(u,{\overline{x}})=u^{-2}\left(e^{{\mathbf{W}}(u\cdot\bar{x})}-1-u^{2}\frac{x_{2}}{2}\right)=u\frac{x_{3}}{3}-u^{2}\frac{x_{2}^{2}}{8}+\ldots$

are power series in only positive powers of $u$ (as is
${\mathbf{h}}_{1}(u,{\overline{x}})$).

######  Remark 4.11.

Here is a combinatorial interpretation of Theorem 4.10. Given a triple
$(G,\Phi,\alpha)$, let $G^{\alpha}$ be the subgraph of $G$ fixed by $\alpha$,
and $\Phi^{\alpha}=\Phi\cap G^{\alpha}$. If we cut all edges of $G$ which are
not in $\Phi$ or in $G^{\alpha}$, we obtain a graph $G^{\prime}$ with leaves,
and $\alpha$ induces a derangement of these leaves (see Figure 3). The fixed
subgraph $G^{\alpha}$ is a subgraph of $G^{\prime}$. Components of
$G^{\prime}$ that do not intersect $G^{\alpha}$ are $k$-cycles of trees with
$k\geq 2$; these contribute the term $\mathbf{h}_{1}$ in Eq. (26). If $C$ is a
component that does intersect $G^{\alpha}$ then $(C\cap
G^{\alpha},C\cap\Phi^{\alpha})$ is a forested graph, and the rest of $C$
consists of $k$-cycles of rooted trees attached at various vertices of $C\cap
G^{\alpha}$, where $k\geq 2$. At each of these vertices, remove all of the
deranged trees that are attached there and replace them with a single orange
leg. Then contract all separating edges of the result that are not orange legs
to get an admissible forested graph $(\overline{C},\overline{\Phi})$ with
legs. We can count such forested graphs using the generating functions
$T(\hbar e^{-w})$ (if $\chi(\overline{C})<0)$, $\frac{w}{2}$ (if
$\chi(\overline{C})=0)$, and $\hbar^{-1}w-\frac{x_{2}}{2}$ (if $\overline{C}$
is a tree but $C$ is not a single vertex with two half-edges attached).
Replacing $\hbar$ by $u^{2}$ and $w$ by ${\mathbf{W}}(u\cdot{\overline{x}})$
has the effect of marking the negative Euler characteristic by $u^{2}$ instead
of $\hbar$ and reconstructing the components $C$ by adding rooted trees to the
forested graphs.

To determine the asymptotic behavior of $\operatorname{\widehat{e}}_{n}$ we
will estimate the size of the coefficients of $\mathbf{H}(u,{\overline{x}})$,
and show that their contribution to $\operatorname{\widehat{e}}_{n}$ is
dominated asymptotically by the contribution of
$\widehat{T}(u^{2}e^{-{\mathbf{W}}(u\cdot\bar{x})})$. We will also show that
the sum
$\sum_{\delta}\eta_{\delta}[u^{2n}x^{\delta}]\widehat{T}(u^{2}e^{-{\mathbf{W}}(u\cdot\bar{x})})$
is dominated by contributions of deranged partitions $\delta$ with all parts
of size $2$. We will then be able to determine the asymptotic behavior of
$\operatorname{\widehat{e}}_{n}$ using estimates on the size of
$\eta_{\lambda}$ and the fact that we know the behavior of the coefficients
$\operatorname{\widehat{\chi}}_{n}$ of $\widehat{T}(\hbar)$ from our previous
work in [10].

###  4.5. Splitting and merging $\Gamma$ functions and estimating the numbers
$\eta_{\lambda}$

In this subsection we show that the numbers $\eta_{\lambda}$ and $\eta_{k,m}$
defined in Corollary 3.5 are bounded by $\Gamma$ functions modulated by
exponentials. Recall that the $\Gamma$ function satisfies

  * •

$\Gamma(x+1)=x\Gamma(x)$ for all $x>0$,

  * •

$\Gamma(1/2)=\sqrt{\pi}$, and

  * •

$\Gamma$ is is _log-convex_ , i.e.

(27) $\displaystyle\log\Gamma\left(ta+\left(1-t\right)b+\frac{1}{2}\right)\leq
t\log\Gamma\left(a+\frac{1}{2}\right)+\left(1-t\right)\log\Gamma\left(b+\frac{1}{2}\right),$

for all $t\in[0,1]$ and $a,b\geq 0$.

In fact, these three properties determine the function $\Gamma$ completely [1,
Theorem 2.1]. Lemma 4.12, Corollary 4.13 and Lemma 4.14 below follow easily