Séminaire Lotharingien de Combinatoire 57 (2007), Article B57a

PERFECT MATCHINGS AND k-DECOMPOSABILITY OF INCREASING TREES

Markus Kuba and Stephan Wagner

Institut für Diskrete Mathematik und Geometrie Technische Universität Wien Wiedner Hauptstr. 8-10/104, 1040 Wien, Austria

                   E-mail: Markus.Kuba@tuwien.ac.at

and

Institut für Analysis und Computational Number Theory Technische Universität Graz Steyrergasse 30, 8010 Graz, Austria

                 E-mail: wagner@finanz.math.tugraz.at

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.

1. 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

2000 Mathematics Subject Classification. Primary 05A15; Secondary 05A16 05C05 05C30. Key words and phrases. Increasing trees, decomposability of trees, perfect matchings,

permutations.

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

(in particular, permutations) — see [13] and the references therein. Bergeron, Flajolet and Salvy [3] developed a general theory for the asymptotic enumeration of increasing trees, based on the general differential equation

T′(x) = Φ(T (x)).  (1)

Here, Φ(t) is the so-called degree function associated with a family of increasing trees. Two major types of increasing trees are distinguished: plane (meaning that the subtrees stemming from a node are ordered) and non-plane increasing trees (meaning that the subtrees are not ordered). Now, the variety of (plane or non-plane) increasing trees associated with a sequence {s_{j}} of non-negative integers (with s_{0} ≠ 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

Φ(t) = ∑_{j=0}^{∞} s_{j}t^{j} and Φ(t) = ∑_{j=0}^{∞} \frac{s_{j}}{j!} t^{j}

in the plane and non-plane case respectively. Differential equation (1) 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 [8].

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, …} 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 [3, 20]).

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.

p_{i}(v) = \begin{cases}\frac{1}{i} & for recursive trees, \\ \frac{d − deg^{+}(v)}{(d − 1)i + 1} & for d-ary increasing trees, \\ \frac{deg^{+}(v) + α}{(α + 1)i − 1} & for generalized plane oriented recursive trees. \end{cases} (2)

PERFECT MATCHINGS AND k-DECOMPOSABILITY OF INCREASING TREES 3

The corresponding degree-weight generating functions are Φ(t) = (1 + t)^{d} and Φ(t) = (1 − t)^{−α} respectively (a little more generally, one can use the functions Φ(t) = s_{0} exp(c_{1}t/s_{0}), Φ(t) = s_{0}(1 + c_{2}t/s_{0})^{d} and Φ(t) = s_{0}(1 − c_{2}t/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 [17] 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 [14], to aid in the construction of the family trees of preserved copies of ancient manuscripts [16], or to model chain letter and pyramid schemes [11]. Furthermore they are used to model the stochastic growth of networks [7]. For further information on recursive trees, see also the survey paper [20] 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ási model for scale-free networks (see, for example, [5]). 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 [3]. In this paper, we are going to study k-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. [1, 2]) — for a given partition λ = {λ_{1}, …, λ_{r}} of n, a graph with n vertices is called λ-decomposable if there exists a partition {V_{1}, …, V_{r}} of the vertex set V such that |V_{i}| = λ_{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 [21]). 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 [15] and Simion [18, 19]. 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.

2. 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 Φ(t); the set of these trees is denoted by T . Furthermore, let 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) = ∑_{l≥1} A_{l}(x)y^{l} for the union ⋃_{l} 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):

\frac{∂}{∂x}B(x, y) = yΦ(A(x) + B(x, y)),  (3)

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 (Φ(t) = e^{t}).

Let us briefly sketch the derivation of (3): we think of a tree T in the class T_{l} as being decomposed into the root, followed by several subtrees T_{1}, T_{2}, … 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}, …: those T_{i} whose roots belong to the component of F that contains the root of T belong to some T_{r_{i}}, whereas the others have to belong to T . Conversely, a collection of rooted trees from T ∪ ⋃_{l} T_{l} whose roots are joined to a new common root yields a rooted tree from ⋃_{l} T_{l}. This decomposition translates directly to equation (3) in analogy to (1) — we refer to the work of Bergeron, Labelle and Leroux [4] for a detailed account on the algebraic equivalents of combinatorial relations of this kind.

Note that a similar argument was used in [21] for the analysis of simply generated tree families, where one obtains a functional equation for B(x, y) instead of a differential equation.

2.1. Matchings: the case k = 2. In the special case k = 2, (3) yields the system of differential equations

\begin{aligned}A′(x) = A′_{2}(x) & = Φ′(A(x))A_{1}(x), \\ A′_{1}(x) & = Φ(A(x)). \end{aligned}  (4)

Multiplying the two equations, we obtain

A_{1}(x)A′_{1}(x) = \frac{Φ(A(x))}{Φ′(A(x))}A′(x)

and thus

\frac{1}{2}A_{1}(x)^{2} = ∫_{0}^{A(x)} \frac{Φ(t)}{Φ′(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

x = ∫_{0}^{A} \frac{du}{Φ′(u)\sqrt{2 ∫_{0}^{u} \frac{Φ(t)}{Φ′(t)} dt}}.  (5)

Of course, the integral does not necessarily exist. To be precise, it exists if and only if s_{1}, the coefficient of t in Φ(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 (Φ(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 (5), we are especially interested in those families of increasing trees which can be generated by a (natural) tree evolution process: recursive trees (Φ(t) = exp(t)), gports (Φ(t) = 1/(1 − t)^{α}, α > 0), and d-ary increasing trees (Φ(t) = (1 + t)^{d}, d > 1). We have

x = ∫_{0}^{A} \frac{1}{\sqrt{2t}}e^{−t} dt, recursive trees,
x = ∫_{0}^{A} \frac{(1 − u)^{α+1}du}{\sqrt{α}\sqrt{2u − u^{2}}}, gports,

x = ∫_{0}^{A} \frac{du}{(1 + u)^{d−1}\sqrt{d}\sqrt{2u + u^{2}}} , d-ary increasing trees.

(6)

First we turn our attention to binary and ternary increasing trees (d = 2, 3), respectively, where the corresponding integrals of (6) can be evaluated easily using the substitution v = \sqrt{u/(2 + u)}. For binary increasing trees we obtain

\frac{x}{\sqrt{2}} = arctan \sqrt{\frac{A}{2 + A}}, A(x) = sec(\sqrt{2}x) − 1,

and for ternary increasing trees

\frac{\sqrt{3}x}{2} = \frac{\sqrt{A(2 + A)}}{2(1 + A)}, A(x) = \frac{1}{\sqrt{1 − 3x^{2}}} − 1.

This proves two remarkable combinatorial formulas: the number of binary increasing trees on 2n vertices with a perfect matching is exactly 2^{n}E_{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 3, we are going to give bijective proofs of these formulas.

For gports (with α ∈ ℕ) and arbitrary d-ary increasing trees, the integrals (6) 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:

\frac{\sqrt{α}x}{2} = ∫_{0}^{√ \overline{\frac{A}{2−A}}} \frac{(1 − v^{2})^{α+1}}{(1 + v^{2})^{α+2}} dv

respectively

\frac{\sqrt{d}x}{2} = ∫_{0}^{√ \overline{\frac{A}{2+A}}} \frac{(1 − v^{2})^{d−2}}{(1 + v^{2})^{d−1}} dv.

For an arbitrary integer d > 1 we have

\begin{aligned}∫_{0}^{√ \overline{\frac{A}{2+A}}} \frac{(1 − v^{2})^{d−2}}{(1 + v^{2})^{d−1}} dv & = ∫_{0}^{√ \overline{\frac{A}{2+A}}} ∑_{l=0}^{d−2} \frac{\binom{d−2}{l}(−1)^{d−2−l}2^{l}}{(1 + v^{2})^{l+1}} dv \\ & = ∑_{l=0}^{d−2} \binom{d − 2}{l}(−1)^{d−2−l}2^{l}I_{l+1}(\sqrt{\frac{A}{2 + A}}), \end{aligned}  (7)

where I_{l}(z) := ∫_{0}^{z} 1/(1 + v^{2})^{l}dv. By partial integration, one obtains a recurrence for I_{l}(z):

2lI_{l+1}(z) = \frac{z}{(1 + z^{2})^{l}} + (2l − 1)I_{l}(z).

Together with I_{1}(z) = arctan z, iteration gives

I_{l}(z) = \frac{l\binom{2l}{l}}{4^{l}(2l − 1)} ∑_{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).

Substituting the result for I_{l}(z) into (7) leads to the following result:

∫_{0}^{√ \overline{\frac{A}{2+A}}} \frac{(1 − v^{2})^{d−2}}{(1 + v^{2})^{d−1}} dv = c_{0} arctan(\sqrt{\frac{A}{2 + A}}) + ∑_{l=1}^{d−2} \frac{c_{l}\sqrt{\frac{A}{2+A}}}{(1 + \frac{A}{2+A})^{l}} ,

where the coefficients are given by

\begin{aligned}c_{0} & = \begin{cases}0 & d odd, \\ 2^{−d+2}\binom{d−2}{d/2−1} & d even, \end{cases} \\ c_{l} & = \frac{4^{l}}{2l\binom{2l}{l}} ∑_{i=l}^{d−2}(−1)^{d−2−i}\binom{d − 2}{i}\frac{\binom{2i}{i}}{2^{i}}. \end{aligned}

As a direct consequence A is always an algebraic function if d is odd (and similarly if α is even). The formula or the coefficients c_{l} is easily obtained for l ≥ 0. For l = 0 we have to simplify the sum

c_{0} = ∑_{i=0}^{d−2}(−1)^{d−2−i}\binom{d − 2}{i}\frac{\binom{2i}{i}}{2^{i}},

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 [12], 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 [3]. As an example, let us consider the case of “festoon” trees, where the labels of a node’s children form an alternating permutation (cf. [3]; there, however, all internal vertices were supposed to have odd degree). In this case, we have Φ(t) = (1 + sin t)/ cos t = sec t + tan t. Then, equation (5) gives us

x = ∫_{0}^{A} \frac{(1 − sin u) du}{\sqrt{2 sin u}}.

It follows that the dominating singularity of A is given by

ρ = ∫_{0}^{π/2} \frac{(1 − sin u) du}{\sqrt{2 sin u}} = ∫_{0}^{1} \sqrt{\frac{1 − v}{2v(1 + v)}} dv = 1.006862.

The value of ρ can also be written in terms of elliptic integrals. Now, expanding the integral around \frac{π}{2}, we obtain

x = ρ − \frac{1}{6\sqrt{2}} (\frac{π}{2} − A(x))^{3} + O ((\frac{π}{2} − A(x))^{4})

and hence

A(x) = \frac{π}{2} − (72ρ^{2})^{1/6} · (1 − x/ρ)^{1/3} + O ((1 − x/ρ)^{2/3}) .

Application of the Flajolet–Odlyzko singularity analysis [8] yields the asymptotics of the coefficients a_{n} of A(x):

a_{n} ∼ \frac{2(72ρ^{2})^{1/6}}{−Γ(−1/3)} n^{−4/3} ρ^{−n} = (\frac{8ρ^{2}}{3} )^{1/6} · \frac{Γ(1/3)}{π} · n^{−4/3} · ρ^{−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} ∼ \sqrt{\frac{log 2}{π}} · n^{−3/2} · (log 2)^{−n}.

Hence, the proportion of trees with a perfect matching among festoon trees is asymptotically

\frac{a_{n}}{t_{n}} ∼ (\frac{8ρ^{2}}{3} )^{1/6} · \frac{Γ(1/3)}{\sqrt{π log 2}} · n^{1/6} · (\frac{log 2}{ρ})^{n} = 2.142692 · n^{1/6} · (0.688423)^{n}.

2.2. The general case for recursive trees. Generally, one obtains a system of k differential equations from (3) 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 Φ(t) = e^{t}. For these trees, we can proceed as follows. The differential equation

\frac{∂}{∂x}B(x, y) = y exp(A(x) + B(x, y))

has the explicit solution

B(x, y) = log (\frac{1}{1 − y ∫_{0}^{x} exp(A(t))dt}).

Extracting the coefficient of y^{l} leads to

A_{l}(x) = \frac{1}{l}( ∫_{0}^{x} exp(A(t))dt)^{l},

and so we arrive at the equation

A_{k}(x) = A(x) = \frac{1}{k}( ∫_{0}^{x} exp(A(t))dt)^{k}.

Further simplification and differentiation with respect to x gives

k^{\frac{1}{k} −1}A′(x)A(x)^{\frac{1}{k} −1} = exp(A(x)),

which leads to the implicit solution

x = ∫_{0}^{A}(kt)^{\frac{1}{k} −1}e^{−t} dt.  (8)

Note that A has nonzero coefficients only for those powers x^{n} for which n is a multiple of k. Following [3], we see that A(x) = B(x^{k}), where B has a dominant singularity at ρ^{k} and ρ is given by

ρ = ∫_{0}^{∞}(kt)^{\frac{1}{k} −1}e^{−t} dt = k^{\frac{1}{k} −1}Γ (\frac{1}{k}) .

Expanding around the singularity shows that A behaves like

A(x) = log \frac{1}{1 − (x/ρ)^{k}} − (1 − \frac{1}{k}) log log \frac{1}{1 − (x/ρ)^{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) ∼ \frac{1}{n} (\frac{k^{1− \frac{1}{k}}}{Γ (\frac{1}{k})})^{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 · (\frac{k^{1− \frac{1}{k}}}{Γ (\frac{1}{k})})^{kn} .

Note that k^{1−1/k}Γ(1/k)^{−1} tends to 1 as k → ∞, a behavior that was also observed in [21] — 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 (3).

3. Bijections for binary and ternary increasing trees with a perfect matching

In this section, we are going to give bijective proofs of two identities observed in Section 2.1. 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 [9, 10, 13].

First of all, we define 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 ∈ 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′ ∈ B_{0}. Similarly, if a tree T ∈ 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′ ∈ C_{0}. Figure 3 shows two examples of this procedure — the edges of the perfect matching are represented by broken lines.

Figure 1. Constructing T′ from T.

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 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, …, 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 ∈ R_{0} is characterized by the following properties:

• the left branch lies in R_{0},

• the right branch lies in R_{1}. Hence, there are two alternating permutations σ_{1}, σ_{2} associated with the branches of T. Note that σ_{1} is a permutation of an even number of labels, whereas σ_{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 σ_{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 σ′_{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 σ_{1}, 1 and σ′_{2} to obtain the alternating permutation σ associated with T.

Similarly, a tree T ∈ R_{1} is characterized by the fact that both its branches belong to R_{0}. Given the alternating permutations σ_{1}, σ_{2} corresponding to these branches, we obtain a new alternating permutation (which we associate with T) by reversing the labels of σ_{2} (obtaining a permutation σ′_{2}) and appending σ_{1}, 1 and σ′_{2}.

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

Figure 2. Application of the recursive procedure for binary increasing trees.

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, …, 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 ϕ between permutations with odd-length cycles and permutations with even-length cycles only, as demonstrated in [6] for instance. For the sake of completeness, we state this bijection as well: given a permutation σ 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, … cycle to the end of the 2nd, 4th, 6th, … cycle to obtain a permutation σ′ 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 ∈ S_{0} is characterized by the following properties:

• the left and middle branch lie in S_{0},

• the right branch lies in S_{1}.

Hence, there are two permutations σ_{1}, σ_{2} with odd-length cycles associated with the left and middle branches of T. We apply the bijection ϕ to σ_{2} and obtain a permutation σ′_{2} with even-length cycles. The union of the cycles of σ_{1} and σ′_{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 σ (with odd-length cycles only) associated with T.

Figure 3. Application of the recursive procedure for ternary increasing trees.

In a similar manner, we construct the permutation associated with a tree T ∈ 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.

Acknowledgment

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

References

[1] B. Awerbuch, A. Goldberg, M. Luby, and S. Plotkin. Network decomposition and locality in distributed computing. In Proceedings of the 30th IEEE Symposion on Foundations of Computer Science, 1989.

[2] D. Barth and H. Fournier. A degree bound on decomposable trees. Discrete Math., 306(5):469– 477, 2006.

[3] F. Bergeron, P. Flajolet, and B. Salvy. Varieties of increasing trees. In CAAP ’92 (Rennes, 1992), volume 581 of Lecture Notes in Comput. Sci., pages 24–48. Springer, Berlin, 1992.

[4] F. Bergeron, G. Labelle, and P. Leroux. Combinatorial species and tree-like structures. Cambridge University Press, 1998., Cambridge, 1998.

[5] B. Bollobás and O. M. Riordan. Mathematical results on scale-free random graphs. In Handbook of graphs and networks, pages 1–34. Wiley-VCH, Weinheim, 2003.

[6] D. Callan. Permutations and coin tossing sequences. Math. Mag., 74(1):55–57, 2001.

[7] D. Chan, B. Hughes, A. Leong, and W. Reed. Stochastically evolving networks. Physical Review E, 24(066124):24 pages, 2003.

[8] P. Flajolet and A. Odlyzko. Singularity analysis of generating functions. SIAM J. Discrete Math., 3(2):216–240, 1990.

[9] D. Foata and M.-P. Schützenberger. Nombres d’Euler et permutations alternantes. In A survey of combinatorial theory (Proc. Internat. Sympos., Colorado State Univ., Fort Collins, Colo., 1971), pages 173–187. North-Holland, Amsterdam, 1973.

[10] D. Foata and V. Strehl. Rearrangements of the symmetric group and enumerative properties of the tangent and secant numbers. Math. Z., 137:257–264, 1974.

[11] J. Gastwirth and P. Bhattacharya. Two probability models of pyramid or chain letter schemes demonstrating that their promotional claims are unreliable. Journal of Applied Probability, 32:527–536, 1984.

[12] R. L. Graham, D. E. Knuth, and O. Patashnik. Concrete mathematics. Addison-Wesley Publishing Company, Reading, MA, second edition, 1994.

[13] A. G. Kuznetsov, I. M. Pak, and A. E. Postnikov. Increasing trees and alternating permutations. Uspekhi Mat. Nauk, 49(6(300)):79–110, 1994.

[14] A. Meir and J. Moon. Cutting down recursive trees. Mathematical Biosciences, 21:173–181, 1974.

[15] J. W. Moon. The number of trees with a 1-factor. Discrete Math., 63(1):27–37, 1987.

[16] D. Najock and C. Heyde. On the number of terminal vertices in certain random trees with an application to stemma construction in philology. Journal of Applied Probability, 19:675–680, 1982.

[17] A. Panholzer and H. Prodinger. The level of nodes in increasing trees revisited. Random Struct. Algorithms, to appear.

[18] R. Simion. Trees with a 1-factor: degree distribution. In Proceedings of the fifteenth Southeastern conference on combinatorics, graph theory and computing (Baton Rouge, La., 1984), volume 45, pages 147–159, 1984.

[19] R. Simion. Trees with 1-factors and oriented trees. Discrete Math., 88(1):93–104, 1991.

[20] R. T. Smythe and H. M. Mahmoud. A survey of recursive trees. Teor. Ĭmovīr. Mat. Stat., (51):1– 29, 1994.

[21] S. Wagner. On the number of decomposable trees. In Proceedings of the Fourth Colloquium on Mathematics and Computer Science (Nancy 2006), pages 301–308, 2006.