\documentclass[12pt,reqno]{amsart}
\usepackage{amsfonts,amsmath,amssymb,amsthm}
\usepackage{graphicx}

\setlength{\parskip}{2pt plus 2pt minus 1pt}
\setlength{\textwidth}{155mm}
\setlength{\oddsidemargin}{5.6mm}
\setlength{\evensidemargin}{5.6mm}

\allowdisplaybreaks

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{prop}{Proposition}
\newtheorem{coroll}{Corollary}
\theoremstyle{remark}
\newtheorem{remark}{Remark}

\def\P{{\mathbb {P}}}
\def\E{{\mathbb {E}}}
\def\V{{\mathbb {V}}}
\def\M{{\mathbb {M}}}
\def\R{{\mathcal{R}}}
\def\B{{\mathcal{B}}}
\def\C{{\mathcal{C}}}
\def\S{{\mathcal{S}}}
\def\O{{\mathcal{O}}}
\newcommand{\N}{\ensuremath{\mathbb{N}}}

\newcommand{\Alt}{\operatorname{Alt}}
\newcommand{\iverl}{\ensuremath{[\hspace{-0.05cm}[}}
\newcommand{\iverr}{\ensuremath{]\hspace{-0.05cm}]}}

\newcommand{\kreis}{\ensuremath{\bigcirc\hspace*{-0.75em}\text{\small{$1$}}\hspace*{0.4em}}}

\newcommand{\ind}{\ensuremath{1 \hspace{-0.13cm}1}}


\begin{document}

\newbox\Adr
\setbox\Adr\vbox{
\centerline{\sc Markus Kuba and Stephan Wagner}
\vskip18pt
\centerline{Institut f{\"u}r Diskrete Mathematik und Geometrie}
\centerline{Technische Universit\"at Wien}
\centerline{Wiedner Hauptstr. 8-10/104, 1040 Wien, Austria}
\centerline{E-mail: {\tt\footnotesize Markus.Kuba@tuwien.ac.at}}
\vskip2mm
\centerline{and}
\vskip2mm
\centerline{Institut f\"ur Analysis und Computational Number Theory}
\centerline{Technische Universit\"at Graz}
\centerline{Steyrergasse 30, 8010 Graz, Austria}
\centerline{E-mail: {\tt\footnotesize wagner@finanz.math.tugraz.at}}
}

\title{Perfect matchings and $k$-decomposability of increasing trees}

\author[Markus Kuba and Stephan Wagner]%
{\box\Adr}

\thanks{This work was supported by
    the Austrian Science Foundation FWF, grants S9608 and S9611.}

\date{}

\begin{abstract}
A tree is called $k$-decomposable if it has a spanning forest whose
components are all of size $k$. In this paper, we study the number of
$k$-decomposable trees in families of increasing trees, i.e. labeled
trees in which the unique path from the root to an arbitrary vertex
forms an increasing sequence. Functional equations for the
corresponding counting series are provided, yielding asymptotic or
even exact formulas for the proportion of $k$-decomposable trees. In
particular, the case $k=2$ (trees with a perfect matching) and the
case of recursive trees are treated. For two cases, bijections to
alternating permutations and permutations with only odd-length cycles can be
given, thus providing alternative proofs for the respective counting
formulas. Furthermore, it turns out that $k$-decomposable recursive
trees become more numerous as $k$ grows to infinity, a behavior that
has also been observed for simply generated families of trees.
\end{abstract}
\keywords{ Increasing trees, decomposability of trees, perfect
matchings, permutations}
\subjclass[2000]{Primary 05A15; Secondary 05A16
05C05 05C30}

\maketitle

%First page headline in AmS-LaTeX for S\'eminaire Lotharingien de Combinatoire
%--first part
\thispagestyle{myheadings}
\font\rms=cmr8
\font\its=cmti8
\font\bfs=cmbx8
\markright{\its S\'eminaire Lotharingien de
Combinatoire \bfs 57 \rms (2007), Article~B57a\hfill}
\def\thepage{}
%
%

\section{Introduction}
An increasing tree is a labeled tree with the property that the
sequence of labels along any path starting from the root is
increasing. The enumeration of families of increasing trees has been
the topic of many papers in the past --- there is a variety of
bijections between certain families of increasing trees and other
combinatorial objects (in particular, permutations) --- see
\cite{KuzPakPos1994} and the references therein. Bergeron, Flajolet
and Salvy \cite{BerFlaSal1992} developed a general theory for the
asymptotic enumeration of increasing trees, based on the general
differential equation
\begin{equation}
\label{trees}
T'(x) = \Phi(T(x)).
\end{equation}
Here, $\Phi(t)$ is the so-called \emph{degree function} associated
with a family of increasing trees. Two major types of increasing trees
are distinguished: \emph{plane} (meaning that the subtrees stemming
from a node are ordered) and \emph{non-plane} increasing trees
(meaning that the subtrees are not ordered). Now, the \emph{variety}
of (plane or non-plane) increasing trees associated with a sequence
$\{s_j\}$ of non-negative integers (with $s_0 \neq 0$ and $s_j > 0$
for some $j>0$) is the family of all (plane or non-plane) increasing
trees with $s_j$ different sorts of nodes of degree $j$. The degree
function is then defined by
$$\Phi(t) = \sum_{j=0}^{\infty} s_j t^j\ \text{ and }\ \Phi(t) =
\sum_{j=0}^{\infty} \frac{s_j}{j!} t^j$$
in the plane and non-plane case respectively. Differential
equation~(\ref{trees}) for the counting series $T(x)$ of the
respective variety of increasing trees follows immediately from the
definition. Based on this equation, asymptotic formulas for the number
of increasing trees in a given variety can be found by means of the
Flajolet--Odlyzko singularity analysis \cite{FlaOd1990}.

Varieties of increasing trees which can be generated by a natural evolution
process are of special interest. The best-known example of a variety of
increasing trees is probably the variety of recursive trees, corresponding to
the sequence $\{1,1,\ldots\}$ in the non-plane case. A random recursive tree is
obtained in the following manner: starting with the root (label 1), the node
with label $i+1$ is attached to any previous node $v$ at step $i+1$, where the
probability is $p_i(v) = \frac{1}{i}$ for each of the nodes. Due to this
property recursive trees are sometimes called uniform recursive trees, in
contrast to non-uniform models such as plane-oriented recursive trees
(see \cite{BerFlaSal1992,MahSmy1995}).

%First page headline in AmS-LaTeX for S\'eminaire Lotharingien de Combinatoire
%--restoring the headers and pagenumbering
\pagenumbering{arabic}
\addtocounter{page}{1}
\markboth{\SMALL MARKUS KUBA UND STEPHAN WAGNER}{\SMALL PERFECT MATCHINGS
AND $k$-DECOMPOSABILITY OF INCREASING TREES}
%
%


The varieties of $d$-ary increasing trees and generalized plane-oriented
recursive trees (abbreviated gports) are defined in a similar way, although the
probability $p_i(v)$ depends on the outdegree $\deg^+(v)$ of the node $v$ as
well.
\begin{equation}
   p_i(v)  =
   \begin{cases}
      \displaystyle{\frac{1}{i}} & \quad \text{for recursive trees}, \\
      \displaystyle{\frac{d-\deg^+(v)}{(d-1)i+1}} & \quad \text{for $d$-ary increasing trees}, \\
      \displaystyle{\frac{\deg^+(v)+\alpha}{(\alpha+1)i-1}}
      \quad& \quad \text{for generalized plane oriented recursive trees}.
   \end{cases}
\end{equation}
The corresponding degree-weight generating functions
are $\Phi(t) = (1+t)^d$ and $\Phi(t) = (1-t)^{-\alpha}$ respectively (a little
more generally, one can use the functions $\Phi(t) = s_0\exp(c_1t/s_0)$,
$\Phi(t) = s_0(1+c_2t/s_0)^d$ and $\Phi(t) = s_0 (1-c_2t/s_0)^{1-c_1/c_2}$ with
certain constants $s_0,c_1,c_2$ to define recursive trees, $d$-ary increasing
trees and gports). In a recent paper of Panholzer and Prodinger it was proved
that only recursive trees, $d$-ary increasing trees and gports can be obtained
by a simple tree evolution process as given above, see \cite{PanPro2007} for
details.

Due to their simple growth rule random recursive trees have been
introduced as a probability model in several areas. For instance, they
are used to model the spread of epidemics \cite{MeiMo1974}, to aid in
the construction of the family trees of preserved copies of ancient
manuscripts \cite{NajHey1982}, or to model chain letter and pyramid
schemes \cite{GaBha1984}. Furthermore they are used to model the
stochastic growth of networks \cite{Chan2003}. For further information
on recursive trees, see also the survey paper \cite{MahSmy1995} and
the references therein.

Binary increasing trees ($d = 2$) are of special importance in computer
science, since they are isomorphic to binary search trees, which themselves serve as an analytic model for the Quicksort
algorithm. Plane-oriented recursive trees are a special instance of the
so-called Albert--Barab\'asi model for scale-free networks (see, for example,
\cite{BolRio2003}). They are used as a simplified growth model of the
world wide web.

Furthermore, it should be noted that the number of recursive trees on $n$
vertices is $(n-1)!$, and the number of binary increasing trees is $n!$.
As the numbers $(n-1)!$ and $n!$ suggest, these two tree families are closely related to permutations.
There are several well known bijections between recursive trees, binary increasing trees and permutations.
We refer the reader to the work of Bergeron, Flajolet and Salvy \cite{BerFlaSal1992}.
In this paper, we are going to study $k$-\emph{decomposable} trees in families
of increasing trees. Here, a tree is said to be $k$-decomposable if it has a
spanning forest whose components are all of size $k$.
Tree decompositions of a
very general nature are of interest in the theory of networks
(cf.\ \cite{AwGoLuPl1989,BarFou2006}) --- for a given partition $ \lambda =
\{\lambda_1,\ldots,\lambda_r\}$ of $n$, a graph with $n$ vertices is called
$\lambda$-decomposable if there exists a partition $\{V_1,\ldots,V_r\}$ of the
vertex set $V$ such that $|V_i| = \lambda_i$ and $V_i$ induces a connected
subgraph. Thinking of the graph as a network, the underlying problem is whether
one can split up the network into subunits of prescribed size. The problem
we are going to consider corresponds to the special case where all the parts
are of equal size. Since increasing trees (and in particular recursive trees)
are used as models for networks, it is natural to consider decomposability for
this kind of trees, even though the analysis is more difficult than for simply
generated families of trees (see the recent paper \cite{Wag2006}). In view of
our probabilistic model, enumerating $k$-decomposable increasing trees is
equivalent to determining the (asymptotic) probability that a tree (network)
evolving from that model can be divided into connected parts of equal size
$k$.

It should also be noted that the special case $k=2$ corresponds to the question
whether a tree has a perfect matching or not --- the enumeration of trees with
perfect matchings has been extensively studied by Moon \cite{Moon1987} and
Simion \cite{Sim1984,Sim1991}. Here, this special case will also be of major
interest, since the differential equations arising in the enumeration of
$k$-decomposable trees can be solved in this case,
yielding implicit solutions for the generating functions.
Furthermore, one obtains remarkable
explicit solutions for the number of $2$-decomposable trees in two cases, for
which we are going to give bijective proofs as well. In the general case $k >
2$, we are only able to give a complete solution of the enumeration problem for
recursive trees.

\section{Generating functions}
For now, let $k$ be a fixed natural number and let $A(x)$ denote the
exponential generating function for the number of $k$-decomposable
increasing trees from a variety determined by the degree function
$\Phi(t)$; the set of these trees is denoted by $\mathcal{T}$.
Furthermore, let $\mathcal{T}_l$ denote the set of increasing trees from our
variety with a spanning forest whose components are of size $k$, except for the component containing the root, which is of size $l$, and let $A_l(x)$ be its generating function. Note at this point that $A(x) = A_k(x)$ by definition.

Furthermore, define the bivariate generating function $B(x,y)=\sum_{l\ge 1}A_l(x)y^l$ for the union $\bigcup_l \mathcal{T}_l$, where the exponent of $x$ gives the size of a tree and the exponent of $y$ the size of the component containing the root in the associated spanning forest whose other components have size $k$.

The starting point of our investigation is the following differential equation for $B(x,y)$:
\begin{equation}
\label{maineq}
        \frac{\partial}{\partial x}B(x,y) = y\Phi(A(x)+B(x,y)),
\end{equation}
with initial condition $B(0,y)=0$. Despite its simple appearance, it
is not easy to give a general approach to this differential
equation. So far, we have only been able to treat two special cases
successfully --- namely, the case $k=2$ (which corresponds to perfect
matchings) and the case of recursive trees ($\Phi(t) = e^t$).

Let us briefly sketch the derivation of \eqref{maineq}: we think of a tree $T$ in the class
$\mathcal{T}_l$ as being decomposed into the root, followed by several subtrees $T_1,T_2,\ldots$ attached to it. Now note that the associated spanning forest $F$ whose components (with exception of the distinguished component that contains the root) all have size $k$ induces spanning forests of the same kind in $T_1,T_2,\ldots$: those $T_i$ whose roots belong to the component of $F$ that contains the root of $T$ belong to some $\mathcal{T}_{r_i}$, whereas the others have to belong to $\mathcal{T}$. Conversely, a collection of rooted trees from $\mathcal{T} \cup \bigcup_l \mathcal{T}_l$ whose roots are joined to a new common root yields a rooted tree from $\bigcup_l \mathcal{T}_l$. This decomposition translates directly to equation~\eqref{maineq} in analogy to \eqref{trees} --- we refer to the work of Bergeron, Labelle and Leroux \cite{BLL1998} for a detailed account on the algebraic equivalents of combinatorial relations of this kind.

Note that a similar argument was used in \cite{Wag2006} for the analysis of simply generated tree families, where one obtains a functional equation for $B(x,y)$ instead of a differential equation.

\subsection{Matchings: the case $k=2$}
\label{match}
In the special case $k=2$, \eqref{maineq} yields the system of differential equations
\begin{equation}
\begin{split}
A'(x) = A'_2(x)&=\Phi'(A(x))A_1(x),\\
A'_1(x)&=\Phi(A(x)).
\end{split}
\end{equation}
Multiplying the two equations, we obtain
$$A_1(x)A_1'(x) = \frac{\Phi(A(x))}{\Phi'(A(x))} A'(x)$$ and
thus $$\tfrac12 A_1(x)^2 = \int_0^{A(x)}
\frac{\Phi(t)}{\Phi'(t)}\,dt.$$
Using this formula for $A_1(x)$ in the first equation yields the implicit
solution for $A = A(x)$, which is given by
\begin{equation}
\label{matchings}
x=\int_0^{A}\frac{du}{\Phi'(u)\sqrt{2\int_{0}^u\frac{\Phi(t)}{\Phi'(t)}\,dt}}.
\end{equation}
Of course, the integral does not necessarily exist. To be precise, it
exists if and only if $s_1$, the coefficient of $t$ in $\Phi(t)$, is
positive. Equivalently, there exists at least one sort of vertices of
outdegree $1$. Not surprisingly, this is equivalent to the fact that
there exist $2$-decomposable trees within the corresponding variety of
increasing trees. It is easy to give a proof for this: if the root is
not allowed to have outdegree $1$, there is always at least one branch
in a tree with a perfect matching that has itself a perfect
matching. But this contradicts the existence of a smallest
$2$-decomposable tree. Thus, if one considers even trees ($\Phi(t) =
\cosh t$, i.e. all nodes have even outdegree) for instance, there are
no trees with a perfect matching (in this case, it is quite obvious,
since all even trees have an odd number of vertices).

Turning back to equation~(\ref{matchings}), we are especially
interested in those families of increasing trees which can
be generated by a (natural) tree evolution process:
recursive trees ($\Phi(t)=\exp(t)$), gports ($\Phi(t)=1/(1-t)^{\alpha}$,
$\alpha>0$), and $d$-ary increasing trees ($\Phi(t)=(1+t)^d$, $d>1$). We have
\begin{equation}
\label{int}
\begin{split}
x&=\int_{0}^{A} \frac{1}{\sqrt{2t}} e^{-t}\,dt,\quad \text{recursive trees},\\
x&=\int_0^{A}\frac{(1-u)^{\alpha+1}du}{\sqrt{\alpha}\sqrt{2u-u^2}},\quad \text{gports},\\
x&=\int_0^{A}\frac{du}{(1+u)^{d-1}\sqrt{d}\sqrt{2u+u^2}},\quad \text{$d$-ary increasing trees}.
\end{split}
\end{equation}

First we turn our attention to binary and ternary increasing trees ($d=2,3$), respectively, where
the corresponding integrals of \eqref{int} can be evaluated easily using the substitution $v = \sqrt{u/(2+u)}$.
For binary increasing trees we obtain
\begin{equation*}
\frac{x}{\sqrt{2}} = \arctan \sqrt{\frac{A}{2+A}},\qquad A(x) = \sec (\sqrt{2}x) - 1,
\end{equation*}
and for ternary increasing trees
\begin{equation*}
\frac{\sqrt{3}x}{2} = \frac{\sqrt{A(2+A)}}{2(1+A)},\qquad A(x) = \frac{1}{\sqrt{1-3x^2}} - 1.
\end{equation*}
This proves two remarkable combinatorial formulas:
the number of binary increasing trees on $2n$ vertices with a perfect
matching is exactly $2^nE_n$, where $E_n$ is a secant number, counting alternating permutations of $2n$ beginning with a rise. Note that $E_n$
counts alternating permutations of $2n$ beginning with a rise.
Similarly, the number of ternary increasing trees on $2n$
vertices with a perfect matching is $3^n(2n-1)!!^2$. The number
$(2n-1)!!^2$ counts permutations with odd-length cycles only (or
permutations with even-length cycles only). In Section~\ref{biject},
we are going to give bijective proofs of these formulas.

For gports (with $\alpha \in \N$) and arbitrary $d$-ary increasing trees, the integrals \eqref{int}
can also be computed explicitly. The substitutions $v = \sqrt{u/(2-u)}$
respectively $v = \sqrt{u/(2+u)}$
help to write them in a simpler form, which also shows an intimate connection between the two:
\begin{equation*}
\frac{\sqrt{\alpha}x}{2} = \int_0^{\sqrt{\frac{A}{2-A}}}
\frac{(1-v^2)^{\alpha+1}}{(1+v^2)^{\alpha+2}}\,dv
\end{equation*}
respectively
\begin{equation*}
\frac{\sqrt{d}x}{2} = \int_0^{\sqrt{\frac{A}{2+A}}}
\frac{(1-v^2)^{d-2}}{(1+v^2)^{d-1}}\,dv.
\end{equation*}

For an arbitrary integer $d > 1$ we have
\begin{equation}
\label{DECOexpansion1}
\begin{split}
\int_0^{\sqrt{\frac{A}{2+A}}}
\frac{(1-v^2)^{d-2}}{(1+v^2)^{d-1}}\,dv &= \int_0^{\sqrt{\frac{A}{2+A}}} \sum_{l=0}^{d-2}
\frac{\binom{d-2}{l}(-1)^{d-2-l}2^l}{(1+v^2)^{l+1}}\,dv \\
&=\sum_{l=0}^{d-2}\binom{d-2}{l}(-1)^{d-2-l}2^l
I_{l+1}\Big(\sqrt{\frac{A}{2+A}}\Big),
\end{split}
\end{equation}
where $I_l(z) :=\int_{0}^{z}1/(1+v^2)^l dv$. By partial integration, one obtains
a recurrence for $I_l(z)$:
\begin{equation*}
2lI_{l+1}(z)=\frac{z}{(1+z^2)^{l}}+(2l-1)I_l(z).
\end{equation*}
Together with $I_1(z) = \arctan z$, iteration gives
\begin{equation*}
I_l(z)=\frac{l\binom{2l}{l}}{4^l(2l-1)}\sum_{i=1}^{l-1}\frac{4^i v}{i\binom{2i}{i}(1+v^2)^{i}}
+\frac{2l \binom{2l}{l}}{4^l(2l-1)}\arctan(z).
\end{equation*}
Substituting the result for $I_l(z)$ into \eqref{DECOexpansion1} leads to the
following result:
\begin{equation*}
\int_0^{\sqrt{\frac{A}{2+A}}}\frac{(1-v^2)^{d-2}}{(1+v^2)^{d-1}}\,dv
= c_0\arctan(\sqrt{\frac{A}{2+A}})+\sum_{l=1}^{d-2}\frac{c_l\sqrt{\frac{A}{2+A}}}{(1+\frac{A}{2+A})^{l}},
\end{equation*}
where the coefficients are given by
\begin{equation*}
\begin{split}
c_0 &=
        \begin{cases}
        0 & d\,\,\text{odd},\\
        2^{-d+2}\binom{d-2}{d/2-1} & d\,\,\text{even},
        \end{cases}\\
c_l &=\frac{4^l}{2l\binom{2l}{l}}\sum_{i=l}^{d-2}(-1)^{d-2-i}\binom{d-2}{i}\frac{\binom{2i}{i}}{2^{i}}.
\end{split}
\end{equation*}
As a direct consequence $A$ is always an algebraic function if $d$ is odd (and
similarly if $\alpha$ is even). The formula or the coefficients $c_l$ is easily
obtained for $l \geq 0$. For $l=0$ we have to simplify the sum
\begin{equation*}
 c_0 =\sum_{i=0}^{d-2}(-1)^{d-2-i}\binom{d-2}{i}\frac{\binom{2i}{i}}{2^{i}},
\end{equation*}
which can be written in terms of hypergeometric functions. Applying
several hypergeometric identities leads to the stated result (we refer the
interested reader to the book of Graham, Knuth and Patashnik
\cite{GraKnuPat1994}, p.~259, Exercise~70, and p.~535).

Of course, one can easily obtain asymptotic formulas for the number of trees
with a perfect matchings in virtually every increasing family following the
lines of \cite{BerFlaSal1992}. As an example, let us consider the case of
``festoon'' trees, where the labels of a node's children form an alternating
permutation (cf.\ \cite{BerFlaSal1992}; there, however, all internal vertices
were supposed to have odd degree). In this case, we have $\Phi(t) =
(1+\sin t)/\cos t = \sec t + \tan t$. Then,
equation~(\ref{matchings}) gives us $$x = \int_0^{A}
\frac{(1-\sin u)\,du}{\sqrt{2\sin u}}.$$ It follows that the
dominating singularity of $A$ is given by $$\rho =
\int_0^{\pi/2} \frac{(1-\sin u)\,du}{\sqrt{2\sin u}} = \int_0^1
\sqrt{\frac{1-v}{2v(1+v)}}\,dv = 1.006862.$$ The value of $\rho$
can also be written in terms of elliptic integrals. Now, expanding
the integral around $\frac{\pi}{2}$, we obtain $$x = \rho -
\frac{1}{6\sqrt2} \left( \frac{\pi}{2} - A(x) \right)^3 + O
\left( \left(\frac{\pi}{2} - A(x) \right)^4 \right)$$
and hence
$$A(x) = \frac{\pi}{2} - (72\rho^2)^{1/6} \cdot
(1-x/\rho)^{1/3} + O \left( (1-x/\rho)^{2/3} \right).$$
Application of the Flajolet--Odlyzko
singularity analysis \cite{FlaOd1990} yields the asymptotics of the
coefficients $a_n$ of $A(x)$:
$$a_n \sim \frac{2(72\rho^2)^{1/6}}{-\Gamma(-1/3)}\,n^{-4/3}\,\rho^{-n} =
\left(\frac{8\rho^2}{3}\right)^{1/6} \cdot \frac{\Gamma(1/3)}{\pi}
\cdot n^{-4/3}\cdot \rho^{-n}$$ for even $n$, the numerical value
of the multiplicative factor being $1.006462$. The exponential
generating function for the number of festoon trees is easily seen
to be $\arcsin(e^x-1)$, from which the asymptotics of its
coefficients $t_n$ follow at once: $$t_n \sim \sqrt{\frac{\log
2}{\pi}} \cdot n^{-3/2} \cdot (\log 2)^{-n}.$$ Hence, the
proportion of trees with a perfect matching among festoon trees is
asymptotically $$\frac{a_n}{t_n} \sim \left(
\frac{8\rho^2}{3} \right)^{1/6} \cdot
\frac{\Gamma(1/3)}{\sqrt{\pi \log 2}} \cdot
n^{1/6} \cdot \left(\frac{\log 2}{\rho} \right)^n = 2.142692 \cdot
n^{1/6} \cdot (0.688423)^n.$$

\subsection{The general case for recursive trees}

Generally, one obtains a system of $k$ differential equations
from~(\ref{maineq}) that seems to be difficult to study. There is only
one case (essentially) for which a simple solution can be obtained,
namely the case of recursive trees, where $\Phi(t) = e^t$. For these
trees, we can proceed as follows. The differential equation
$$\frac{\partial}{\partial x}B(x,y) = y\exp(A(x)+B(x,y))$$
has the explicit solution
\begin{equation*}
        B(x,y) = \log\Big(\frac{1}{1-y\int_{0}^{x}\exp(A(t))dt}\Big).
\end{equation*}
Extracting the coefficient of $y^l$ leads to
\begin{equation*}
        A_l(x) = \frac{1}l \Big(\int_{0}^{x}\exp(A(t))dt\Big)^l,
\end{equation*}
and so we arrive at the equation
\begin{equation*}
        A_k(x) = A(x)= \frac{1}k \Big(\int_{0}^{x}\exp(A(t))dt\Big)^k.
\end{equation*}
Further simplification and differentiation with respect to $x$ gives
\begin{equation*}
        k^{\frac1k-1}A'(x)A(x)^{\frac1k-1}=\exp(A(x)),
\end{equation*}
which leads to the implicit solution
\begin{equation}
        x=\int_{0}^{A} (kt)^{\frac1k-1}e^{-t}\,dt.
\end{equation}
Note that $A$ has nonzero coefficients only for those powers $x^n$ for which $n$
is a multiple of $k$. Following \cite{BerFlaSal1992}, we see that $A(x) = B(x^k)$, where $B$ has a dominant
singularity at $\rho^k$ and $\rho$ is given by
$$\rho = \int_{0}^{\infty} (kt)^{\frac1k-1}e^{-t}\,dt = k^{\frac1k-1}
\Gamma\left(\tfrac{1}{k}\right).$$
Expanding around the singularity shows that $A$ behaves like
$$A(x) = \log \frac{1}{1-(x/\rho)^k} - \left(1 - \frac1k\right) \log \log \frac{1}{1-(x/\rho)^k} + O(1),$$
so that a simple singularity analysis gives us the behavior of the coefficients $[x^{kn}]A(x)$:
$$a_{kn} = [x^{kn}]A(x) \sim \frac{1}{n} \left(
  \frac{k^{1-\frac{1}{k}}}{\Gamma\left(\tfrac{1}{k}\right)} \right)^{kn}.$$
Since the number of recursive trees with $n$ vertices is well-known to be $(n-1)!$, we see that the ratio of $k$-decomposable recursive trees among all recursive trees is asymptotically
$$ k \cdot \left(
  \frac{k^{1-\frac{1}{k}}}{\Gamma\left(\tfrac{1}{k}\right)}
\right)^{kn}.$$
Note that $k^{1-1/k}\Gamma(1/k)^{-1}$
tends to $1$ as $k \to \infty$, a behavior that was also observed in
\cite{Wag2006} --- we expect this to be true for arbitrary classes of
increasing trees, but a proof has to involve some deeper
understanding of the analytic behavior of equation~(\ref{maineq}).

\section{Bijections for binary and ternary increasing trees with a perfect
  matching}
\label{biject}

In this section, we are going to give bijective proofs of two
identities observed in Section~\ref{match}. A lot of similar
bijections are known between various types of increasing trees and
alternating permutations (which are enumerated by the secant and the
tangent numbers) --- the interested reader is referred to
\cite{FoaSch1973,FoaStr1974,KuzPakPos1994}. 

First of all, we define \emph{equivalence classes} on binary and
ternary increasing trees with a perfect matching. Let $\B_0$ and
$\C_0$ denote the sets of binary respectively ternary increasing trees with a
perfect matching. Now, we consider the following operation: let a
tree $T \in \B_{0}$ on $2n$ vertices be given together with
its unique perfect matching $M$. For every vertex $v$ that is joined to its
left child in $M$, we flip the branches attached to $v$, obtaining a
new tree $T' \in \B_0$. Similarly, if a tree $T \in
\C_0$ on $2n$ vertices is given together with its unique
perfect matching $M$, we perform a right-rotation on the branches of
every vertex $v$ that is joined to one of its children in $M$, in such
a way that this child becomes the right child. Again, we obtain a new tree $T'
\in \C_0$. Figure~\ref{rightrot} shows two examples of this procedure --- the
edges of the perfect matching are represented by broken lines.
\begin{figure}[htbp]
\label{rightrot}
\begin{center}
\includegraphics[width=90mm]{BinInc.pdf}
\end{center}
\begin{center}
\includegraphics[width=90mm]{TernInc.pdf}
\end{center}
\caption{Constructing $T'$ from $T$.}
\end{figure}

Obviously, the resulting tree $T'$ is characterized by the condition
that all edges of the unique perfect matching link a parent and its
right child. Two trees are called \emph{equivalent} if they yield the
same tree $T'$. Since $M$ contains $n$ edges, the number of trees in
each equivalence class is $2^n$ respectively $3^n$, as there are two
respectively three possible directions for each of the edges of $M$.

In an analogous manner, we define equivalence classes on $\B_1$ and
$\C_1$, the classes of binary respectively ternary increasing trees with a
matching that covers all vertices except the root. Again, the number
of trees in an equivalence class is $2^n$ respectively $3^n$ if the number of
vertices is $2n+1$.

Now, let $\R_0$ be the set of representatives of equivalence
classes of $\B_0$, and define $\R_1$
analogously. Furthermore, we write $\R_{i,n}$ for the set of
$n$-vertex trees in $\R_i$. Finally, let $\Alt_n$ be the set
of alternating permutations of $\{1,2,\ldots,n\}$, beginning with a
rise. We are going to construct a bijection between
$\R_{0,2n}$ and $\Alt_{2n}$ as well as a bijection between
$\R_{1,2n+1}$ and $\Alt_{2n+1}$.

The bijection is constructed by means of induction. The empty tree
corresponds to the ``permutation'' of $0$ elements, and the bijection
between $\R_{1,1}$ and $\Alt_1$ is also trivial. Now, note that a
tree $T \in \R_0$ is characterized by the following
properties:
\begin{itemize}
\item the left branch lies in $\R_0$,
\item the right branch lies in $\R_1$.
\end{itemize}
Hence, there are two alternating permutations $\sigma_1,\sigma_2$
associated with the branches of $T$. Note that $\sigma_1$ is a
permutation of an even number of labels, whereas $\sigma_2$ is a
permutation of an odd number of labels. Now, a simple construction
yields the alternating permutation associated with $T$: reverse the labels
in $\sigma_2$, i.e. interchange the positions of the largest and smallest label, the positions of the second-largest and second-smallest label, etc. (for instance, $57692$ becomes $75629$), so that one obtains an alternating permutation $\sigma'_2$ beginning with a fall
(and ending with a rise, since the number of labels is odd) on the
same set of labels. Now append $\sigma_1$, $1$ and $\sigma'_2$ to
obtain the alternating permutation $\sigma$ associated with $T$.

Similarly, a tree $T \in \R_1$ is characterized by the fact that both
its branches belong to $\R_0$. Given the alternating permutations
$\sigma_1,\sigma_2$ corresponding to these branches, we obtain a new
alternating permutation (which we associate with $T$) by reversing the
labels of $\sigma_2$ (obtaining a permutation $\sigma'_2$) and appending $\sigma_1$, $1$ and $\sigma'_2$.

Clearly, the described construction defines a bijection, which proves
the fact that there are $E_n$ equivalence classes and thus $2^nE_n$
binary increasing trees on $2n$ vertices with a perfect matching.

\begin{figure}[htbp]
\begin{center}
\includegraphics[width=80mm]{Alter.pdf}
\end{center}
\caption{Application of the recursive procedure for binary increasing trees.}
\end{figure}

For ternary increasing trees, let $\S_0$ and $\S_1$ be the sets of representatives
for the equivalence classes of $\C_0$ and $C_1$ respectively, let
$\S_{0,n}$ and $\S_{1,n}$ be defined analogously to $\R_{0,n}$ and
$\R_{1,n}$ and denote by $\O_n$ the set of permutations of
$\{1,2,\ldots,n\}$ with the property that all cycles have odd length. We will provide a bijection between $\S_{0,2n}$ and $\O_{2n}$ and a bijection between $\S_{1,2n+1}$
and $\O_{2n+1}$ by means of a similar recursive construction as in the
case of binary increasing trees.

First, note that there is a simple bijection $\phi$ between
permutations with odd-length cycles and permutations with even-length cycles
only, as demonstrated in \cite{Cal2001} for instance. For the sake of
completeness, we state this bijection as well: given a permutation
$\sigma$ with odd-length cycles and an even number of cycles, write it
in such a way that the largest element in each cycle occurs first and these
elements are in increasing order. Then, move the last element of the
1st, 3rd, 5th, \ldots cycle to the end of the 2nd, 4th, 6th, \ldots
cycle to obtain a permutation $\sigma'$ with even-length cycles. For
instance, $(3)(512)(847)(9)$ is mapped to $(5123)(84)(97)$. It is not
difficult to see that the correspondence is bijective.

Now, we are ready to construct the bijections between $\S_{0,2n}$ and
$\O_{2n}$ and between $\S_{1,2n+1}$ and $\O_{2n+1}$. Again, the empty tree
corresponds to the ``permutation'' of $0$ elements, and the bijection
between $\S_{1,1}$ and $\O_1$ is trivial. Now, a tree $T \in \S_0$ is
characterized by the following properties:
\begin{itemize}
\item the left and middle branch lie in $\S_0$,
\item the right branch lies in $\S_1$.
\end{itemize}
Hence, there are two permutations $\sigma_1,\sigma_2$ with odd-length cycles
associated with the left and middle branches of $T$. We apply the
bijection $\phi$ to $\sigma_2$ and obtain a permutation $\sigma'_2$ with
even-length cycles. The union of the cycles of $\sigma_1$ and
$\sigma'_2$ uniquely defines a permutation of the labels of the left
and middle subtrees. We write this permutation as a list of elements
rather than in cycle notation and prepend $1$ to obtain the cycle
containing $1$ (for instance, the permutation $27834$ yields the cycle
$(127834)$). Together with the permutation associated with the right
branch, this gives us the unique permutation $\sigma$ (with odd-length
cycles only) associated with $T$.

\begin{figure}[ht]
\begin{center}
\includegraphics[width=97mm]{Odd.pdf}
\end{center}
\caption{Application of the recursive procedure for ternary increasing trees.}
\end{figure}

In a similar manner, we construct the permutation associated with a
tree $T \in \S_1$: the three branches all belong to $\S_0$, so we may
use the left and middle branch to define the cycle that contains $1$,
and the right branch to define the permutation of the remaining elements.

So finally, we have established a bijective proof of the fact that there
are $3^n(2n-1)!!^2$ ternary increasing trees on $2n$ vertices with a
perfect matching. Note also that the number of ternary increasing
trees on $n$ vertices is precisely $(2n-1)!!$. Hence, there might be a
simple bijection between equivalence classes of ternary increasing trees
on $2n$ vertices and pairs of ternary increasing trees on $n$ vertices.

\section*{Acknowledgment}

The authors would like to thank Dominique Foata for his kind support, in
particular for providing valuable references.

\def\cprime{$'$}
\begin{thebibliography}{10}

\bibitem{AwGoLuPl1989}
B.~Awerbuch, A.~Goldberg, M.~Luby, and S.~Plotkin.
\newblock Network decomposition and locality in distributed computing.
\newblock In {\em Proceedings of the 30th IEEE Symposion on Foundations of
  Computer Science}, 1989.

\bibitem{BarFou2006}
D.~Barth and H.~Fournier.
\newblock A degree bound on decomposable trees.
\newblock {\em Discrete Math.}, 306(5):469--477, 2006.

\bibitem{BerFlaSal1992}
F.~Bergeron, P.~Flajolet, and B.~Salvy.
\newblock Varieties of increasing trees.
\newblock In {\em CAAP '92 (Rennes, 1992)}, volume 581 of {\em Lecture Notes in
  Comput. Sci.}, pages 24--48. Springer, Berlin, 1992.

\bibitem{BLL1998}
F.~Bergeron, G.~Labelle, and P.~Leroux.
\newblock {\em Combinatorial species and tree-like structures}.
\newblock Cambridge University Press, 1998., Cambridge, 1998.

\bibitem{BolRio2003}
B.~Bollob{\'a}s and O.~M. Riordan.
\newblock Mathematical results on scale-free random graphs.
\newblock In {\em Handbook of graphs and networks}, pages 1--34. Wiley-VCH,
  Weinheim, 2003.

\bibitem{Cal2001}
D.~Callan.
\newblock Permutations and coin tossing sequences.
\newblock {\em Math. Mag.}, 74(1):55--57, 2001.

\bibitem{Chan2003}
D.~Chan, B.~Hughes, A.~Leong, and W.~Reed.
\newblock Stochastically evolving networks.
\newblock {\em Physical Review E}, 24(066124):24 pages, 2003.

\bibitem{FlaOd1990}
P.~Flajolet and A.~Odlyzko.
\newblock Singularity analysis of generating functions.
\newblock {\em SIAM J. Discrete Math.}, 3(2):216--240, 1990.

\bibitem{FoaSch1973}
D.~Foata and M.-P. Sch{\"u}tzenberger.
\newblock Nombres d'{E}uler et permutations alternantes.
\newblock In {\em A survey of combinatorial theory (Proc. Internat. Sympos.,
  Colorado State Univ., Fort Collins, Colo., 1971)}, pages 173--187.
  North-Holland, Amsterdam, 1973.

\bibitem{FoaStr1974}
D.~Foata and V.~Strehl.
\newblock Rearrangements of the symmetric group and enumerative properties of
  the tangent and secant numbers.
\newblock {\em Math. Z.}, 137:257--264, 1974.

\bibitem{GaBha1984}
J.~Gastwirth and P.~Bhattacharya.
\newblock Two probability models of pyramid or chain letter schemes
  demonstrating that their promotional claims are unreliable.
\newblock {\em Journal of Applied Probability}, 32:527--536, 1984.

\bibitem{GraKnuPat1994}
R.~L. Graham, D.~E. Knuth, and O.~Patashnik.
\newblock {\em Concrete mathematics}.
\newblock Addison-Wesley Publishing Company, Reading, MA, second edition, 1994.

\bibitem{KuzPakPos1994}
A.~G. Kuznetsov, I.~M. Pak, and A.~E. Postnikov.
\newblock Increasing trees and alternating permutations.
\newblock {\em Uspekhi Mat. Nauk}, 49(6(300)):79--110, 1994.

\bibitem{MeiMo1974}
A.~Meir and J.~Moon.
\newblock Cutting down recursive trees.
\newblock {\em Mathematical Biosciences}, 21:173--181, 1974.

\bibitem{Moon1987}
J.~W. Moon.
\newblock The number of trees with a {$1$}-factor.
\newblock {\em Discrete Math.}, 63(1):27--37, 1987.

\bibitem{NajHey1982}
D.~Najock and C.~Heyde.
\newblock On the number of terminal vertices in certain random trees with an
  application to stemma construction in philology.
\newblock {\em Journal of Applied Probability}, 19:675--680, 1982.

\bibitem{PanPro2007}
A.~Panholzer and H.~Prodinger.
\newblock The level of nodes in increasing trees revisited.
\newblock {\em Random Struct. Algorithms}, to appear.

\bibitem{Sim1984}
R.~Simion.
\newblock Trees with a {$1$}-factor: degree distribution.
\newblock In {\em Proceedings of the fifteenth Southeastern conference on
  combinatorics, graph theory and computing (Baton Rouge, La., 1984)},
  volume~45, pages 147--159, 1984.

\bibitem{Sim1991}
R.~Simion.
\newblock Trees with {$1$}-factors and oriented trees.
\newblock {\em Discrete Math.}, 88(1):93--104, 1991.

\bibitem{MahSmy1995}
R.~T. Smythe and H.~M. Mahmoud.
\newblock A survey of recursive trees.
\newblock {\em Teor. \u Imov\=\i r. Mat. Stat.}, (51):1--29, 1994.

\bibitem{Wag2006}
S.~Wagner.
\newblock On the number of decomposable trees.
\newblock In {\em Proceedings of the Fourth Colloquium on Mathematics and
  Computer Science (Nancy 2006)}, pages 301--308, 2006.

\end{thebibliography}


\end{document}