Séminaire Lotharingien de Combinatoire 55 (2006), Article B55e

ON GENERATING SERIES OF COLOURED PLANAR TREES

ROLAND BACHER AND GILLES SCHAEFFER

Abstract. We generalize and reprove an identity of Parker and Loday. It states that certain pairs of generating series associated to coloured plane rooted trees are mutually reciprocal series.

1. Introduction

In [1] Carlitz, Scoville and Vaughan consider finite words over a finite alphabet A such that all pairs of consecutive letters belong to a fixed subset L ⊂ A × A. They show (Theorems 6.8 and 7.3 of [1]) that suitably defined pairs of signed generating series counting such words associated to L ⊂ A × A and to its complementary set \overline{L} = A × A \ L are inverses of each other. Their result was generalized in the first part of Parker’s thesis [5] who showed an analogous result for suitable classes of finite trees having coloured vertices. Loday in [3], motivated by questions concerning combinatorial realizations of operads, rediscovered Parker’s result and gave a new proof based on homological arguments.

This paper presents a combinatorial interpretation and a further generalization of Parker’s and Loday’s result.

A typical example of our identity can be described as follows: associate to two complex matrices

M_{1} = ( \begin{matrix}a & b \\ c & d \end{matrix} ) and M_{2} = ( \begin{matrix}α & β \\ γ & δ \end{matrix} )

formal power series G_{1}, G_{2}, Ĝ_{1}, Ĝ_{2} of the form X^{2}+… defined by the algebraic systems of equations

\{ \begin{matrix}G_{1} & = & (X + aG_{1} + bG_{2})(X + αG_{1} + βG_{2}) \\ G_{2} & = & (X + cG_{1} + dG_{2})(X + γG_{1} + δG_{2}) \end{matrix}

and

\{ \begin{matrix}Ĝ_{1} & = & (X + (1 + a)Ĝ_{1} + (1 + b)Ĝ_{2})(X + (1 + α)Ĝ_{1} + (1 + β)Ĝ_{2}) \\ Ĝ_{2} & = & (X + (1 + c)Ĝ_{1} + (1 + d)Ĝ_{2})(X + (1 + γ)Ĝ_{1} + (1 + δ)Ĝ_{2}) \end{matrix} .

Our main result states then that the formal power series φ = X −G_{1} −G_{2} and ψ = X + Ĝ_{1} + Ĝ_{2} satisfy the identity φ ∘ ψ = X. They define thus reciprocal branches of holomorphic algebraic functions in a neighbourhood of the origin.

2000 Mathematics Subject Classification. 05A15, 05A19, 05C05.

Key words and phrases. Generating function, inversion of power series, planar tree.

A tedious proof of this result can be given by computing a minimal polynomial P (φ, X) = ∑_{i,j} p_{i,j}φ^{i}X^{j} = 0 for φ and by checking that we have P (X, ψ) = ∑_{i,j} p_{i,j}X^{i}ψ^{j} = 0. Since this identity is algebraic, the field of complex numbers can be replaced by an arbitrary commutative ring. Our proof is instead based on a simple combinatorial argument showing that the series G = G_{1} + G_{2} and Ĝ = Ĝ_{1} + Ĝ_{2} satisfy the relation Ĝ = G ∘ (X + Ĝ).

The sequel of this paper is organized as follows: the next section states the main result in purely algebraic terms over a not necessarily commutative ring. Parker’s and Loday’s result is the special case of weight-matrices with coefficients in {0, −1} and of colours having a common degree k (corresponding to k−regular trees). Parker’s thesis contains also a generalization to colours of different degrees (corresponding to trees which are no longer necessarily regular). Our main result removes the restriction on the coefficients. It is also more elementary (at least in a commutative setting) since the statement avoids combinatorial descriptions (although they are crucial to our proof).

It follows from our formulation that all involved generating functions are algebraic in a commutative setting and over a finite alphabet. Section 3 fixes notations concerning trees and proves the main result. The proof avoids homological arguments and is thus more elementary than the proof of [3]. Section 4 contains a combinatorial proof of a related identity. As an application of our main result (Corollary 2.4), we describe formulas for the reversion (or inversion under composition) of formal power series in Section 5. Section 6 describes briefly a further generalization involving several variables associated to trees having vertices of different types. Section 7 contains the computations for example (i) of [3], using notations close to the notations of [3]. We display the defining polynomial of the relevant (algebraic) generating function and discuss briefly its asymptotics.

2. Main result

In the sequel, 𝕂 denotes a fixed, not necessarily commutative ring. All variables, formal power series, etc., are also non-commutative. This condition can be weakened, especially over a commutative ring 𝕂 where one can also work in a totally commutative setting.

Consider a (not necessarily finite) set A, called the alphabet, together with a degree function d : A ⟶ ℕ. We denote by Y_{A} a set of (non-commutative) variables indexed by elements α ∈ A and by X a supplementary (non-commu-tative) variable. We denote by 𝕂[[X, Y_{A}]] the obvious ring of non-commutative formal power series. An element of 𝕂[[X, Y_{A}]] is a (generally infinite) sum of monomials of the form

r_{1}Z_{1}r_{2}Z_{2} ⋯ r_{l}Z_{l}r_{l+1}

with r_{i} ∈ 𝕂 and Z_{i} ∈ Y_{A} ∪ {X}.

Consider also a sequence

w(1), w(2), ⋯ ⊂ 𝕂^{A×A}

of weight-matrices with coefficients w(k)_{α,β} ∈ 𝕂 indexed by (α, β) ∈ A × A. These data define recursively a set {G_{α}}_{α∈A} ⊂ 𝕂[[X, Y_{A}]] of formal power series indexed by A such that

G_{α} = Y_{α}(X + ∑_{β∈A} w(1)_{α,β}G_{β})(X + ∑_{β∈A} w(2)_{α,β}G_{β}) ⋯

⋯ (X + ∑_{β∈A} w(d(α))_{α,β}G_{β})

for all α ∈ A.

Remark 2.1. A coefficient w(k)_{α,β} with k > d(α) of the k-th weight-matrix w(k) is never used and can thus be left unspecified.

Remark 2.2. The formal power series G_{α} are well-defined: if d(α) = 0 we get G_{α} = Y_{α} and there is nothing to do. For d(α) > 0, we consider all variables X, Y_{A} graded of degree 1. The series G_{α} can now be computed by “bootstrapping”: set G_{α}^{1} = Y_{α} as an approximation which is correct up to degree 1. An approximation {G_{α}^{k}}_{α∈A} correct up to degree k for all α ∈ A produces now an approximation

G_{α}^{k+1} = Y_{α}(X + ∑_{β∈A} w(1)_{α,β}G_{β}^{k}) ⋯ (X + ∑_{β∈A} w(d(α))_{α,β}G_{β}^{k})

which is exact at least up to degree k + 1.

Similarly, we consider also the set {Ĝ_{α}}_{α∈A} ⊂ 𝕂[[X, Y_{A}]] of formal power series defined by

\begin{aligned}Ĝ_{α} & = & Y_{α}(X + ∑_{β∈A}(1 + w(1)_{α,β})Ĝ_{β})(X + ∑_{β∈A}(1 + w(2)_{α,β})Ĝ_{β}) ⋯ \\ & & ⋯ (X + ∑_{β∈A}(1 + w(d(α))_{α,β})Ĝ_{β}) . \end{aligned}

Setting G = ∑_{α∈A} G_{α} and Ĝ = ∑_{α∈A} Ĝ_{α}, our main result is as follows.

Theorem 2.3. We have

Ĝ = G ∘_{X} (X + Ĝ)

where ∘_{X} indicates composition of formal power series with respect to X (every occurrence of X in G is replaced by the formal power series X + Ĝ).

Corollary 2.4. We have

(X − G) ∘_{X} (X + Ĝ) = X .

Proof. Rewrite the identity of Theorem 2.3 as Ĝ − G ∘_{X} (X + Ĝ) + X = X in order to get

Ĝ − G ∘_{X} (X + Ĝ) + X = (X + Ĝ) − G ∘_{X} (X + Ĝ) = (X − G) ∘_{X} (X + Ĝ) .

□ Remark 2.5. (i) Theorem 2.3 and Corollary 2.4 continue to hold for commutative variables Y_{A}. However, the variable X cannot commute with non-central elements of 𝕂.

(ii) All specializations (say to elements of 𝕂) of variables Y_{α} with α ∈ A of degree d(α) ≥ 2 are possible in a setting of formal power series. Specializations of Y_{α} for α of degree d(α) = 0 or 1 lead easily to difficulties and convergence problems.

(iii) The main result of [1] corresponds to d^{−1}(1) = A. In this case, Corollary 2.4 boils down to a simple product in 𝕂 since X − G and X + Ĝ are of the form cX, \frac{1}{c}X with c ∈ 𝕂[[Y_{A}]] invertible.

(iv) A straightforward generalization involving variables X_{VT} associated to vertex-types will be presented in Section 6.

Remark 2.6. One can also consider the following slightly more general version: let (λ_{α})_{α∈A} be an additional vector associating a weight λ_{α} ∈ 𝕂 to each colour α ∈ A. Theorem 2.3 and Corollary 2.4 (which correspond to the case λ_{α} = 1 for all α ∈ A) remain valid with G = ∑_{α∈A} λ_{α}G_{α} and Ĝ = ∑_{α∈A} λ_{α}Ĝ_{α}. The case where there exists a vector (μ_{α})_{α∈A} such that μ_{α}λ_{α} = 1 for all α ∈ A can be reduced to the case treated in this paper by considering variables Ỹ_{α} = λ_{α}Y_{α} and weight-matrices with coefficients w̃(k)_{α,β} = w(k)_{α,β}μ_{β}.

Remark 2.7. Loday and Parker use slightly different notations. Loday’s result in the case where all elements of A have degree 2 corresponds to Y_{α} = −1 for all α ∈ A, t = −X with

g_{α} = −G_{α} = (−t + ∑_{β∈A} L_{α,β}g_{β}) (−t + ∑_{β∈A} R_{α,β}g_{β})

where the matrices L = −w(1), R = −w(2) are in {0, 1}^{♯(A)×♯(A)}. By Corollary 2.4, the reciprocal series of −t + ∑_{α∈A} g_{α} is then given by −(X + Ĝ) = −X + ∑_{α∈A} ĝ_{α} where

ĝ_{α} = −Ĝ_{α} = (X − ∑_{β∈A}(1 − L_{α,β})ĝ_{α}) (X − ∑_{β∈A}(1 − R_{α,β})ĝ_{α})

= (−X + ∑_{β∈A}(1 − L_{α,β})ĝ_{α}) (−X + ∑_{β∈A}(1 − R_{α,β})ĝ_{α}) .

3. Trees

A rooted tree T is either given by the empty set {} representing the trivial rooted tree reduced to its root or is recursively defined by a non-empty set

T = {T_{s}}_{s∈S}

where T_{s} are rooted trees attached to the sons (also called children or direct descendants) S of the root vertex. Such a tree T can be identified with a directed graph Γ(T) having a distinguished vertex r, called the root, by joining the root vertex r to its sons using a directed edge originating in r and terminating at the root r_{s} of the rooted graph Γ(T_{s}) issued from its son indexed by s ∈ S. In the sequel, we often identify a vertex v of T (or, more precisely, of Γ(T)) with the tree T_{v} rooted in v which consists of v and all its descendants. A rooted tree T is finite if Γ(T) is a finite graph and locally finite if every vertex has only a finite number of sons.

A plane rooted tree is recursively defined by a finite or (enumerably) infinite sequence

T = (T_{1}, T_{2}, …)

of plane rooted trees T_{1}, T_{2}, . . .. A plane rooted tree is thus a rooted tree such that every vertex has a finite or enumerable number of completely ordered sons. The empty sequence () represents the trivial plane rooted tree.

In the sequel, a tree denotes always a finite plane rooted tree.

3.1. Coloured trees. Consider an alphabet A together with a degree function d : A ⟶ ℕ inducing a partition

A = ⋃_{k=0}^{∞} A_{k}

defined by A_{k} = d^{−1}(k).

An A-coloured tree or coloured tree is either given by the empty sequence () or is recursively defined as (α; T_{1}, …, T_{d(α)}) where α ∈ A of degree d(α) is the colour of the root r and where the coloured trees T_{1}, …, T_{d(α)} are attached to the d(α) sons of r. We call the coloured tree () represented by the empty sequence trivial. A coloured tree (α) reduced to a root with a colour α ∈ A_{0} of degree 0 is not considered as trivial. Every leaf (vertex without sons) of a rooted tree is thus either trivial (the subtree issued from the leaf is the trivial tree reduced to its uncoloured root) or coloured by an element in d^{−1}(0) ⊂ A of degree 0. A leaf coloured by α ∈ A_{0} = d^{−1}(0) ⊂ A is an ordinary leaf.

Figure 1. A coloured tree

Figure 1 shows the coloured tree

(R; (Q; (), (P; (q))), (P; (R; (), (r), (p))), ())

having three trivial leaves and three ordinary leaves (coloured p, q and r). It has colours in A = {p, q, r, P, Q, R} of degree d(p) = d(q) = d(r) = 0, d(P) = 1, d(Q) = 2, d(R) = 3.

Let w(1), w(2), ⋯ ∈ 𝕂^{A×A} be a sequence of weight-matrices as in Section 2. The energy e(T) ∈ 𝕂[X, Y_{A}] of a coloured tree T is the monomial defined by e(T) = X if T is trivial and is recursively by

e(T) = Y_{α}e_{1,α}(T_{1})e_{2,α}(T_{2}) ⋯ e_{d(α),α}(T_{d(α)})

for a non-trivial tree T = (α; T_{1}, …, T_{d(α)}), where e_{k,α}(T_{k}) = e(T_{k}) = X if T_{k} is trivial and where e_{k,α} = w(k)_{α,β_{k}}e(T_{k}) if the tree T_{k} = (β_{k}; T_{k,1}, …, T_{k,d(β_{k})}) (attached to the k-th son of the root in T) is non-trivial and has root colour β_{k}. Remark 3.1. (i) Coefficients w(k)_{α,β} with k > d(α) are never used (cf. Remark 2.1).

(ii) Coloured trees as appearing in this paper do in general not correspond to graph-theoretic colourings of the underlying trees: adjacent vertices of a coloured tree can share a common colour. This can of course be avoided: weight-matrices such that w(k)_{α,α} = 0 for all k ∈ ℕ and for all α ∈ A give the energy 0 to all trees with improper colourings in a graph-theoretic sense.

The energy e(T) of the coloured tree T represented in Figure 1 is given by

Y_{R} w(1)_{R,Q}Y_{Q}Xw(2)_{Q,P} Y_{P} w(1)_{P,q}Y_{q} w(2)_{R,P} Y_{P} w(1)_{P,R}Y_{R}Xw(2)_{R,r}Y_{r}w(3)_{R,p}Y_{p} X .

The generating function (or partition function) G_{CT} for the set CT of coloured trees is now defined as

G_{CT} = ∑_{T ∈CT} e(T) ∈ 𝕂[[X, Y_{A}]] .

Denoting by

CT_{α} = {(α; T_{1}, …, T_{d(α)})|T_{1}, …, T_{d(α)} ∈ CT } ⊂ CT

the subset of all non-trivial coloured trees with root colour α, we introduce also restricted generating functions

G_{α} = ∑_{T ∈CT_{α}} e(T) .

The partition

CT = {()} ⋃_{α∈A} CT_{α}

shows the identity

G_{CT} = X + ∑_{α∈A} G_{α} .

Proposition 3.2. We have

G_{α} = Y_{α}(X + ∑_{β∈A} w(1)_{α,β}G_{β})(X + ∑_{β∈A} w(2)_{α,β}G_{β}) ⋯

⋯ (X + ∑_{β∈A} w(d(α))_{α,β}G_{β}) .

Proof. The proof is by induction on the total degree of the variables Y_{A}. The formula yields the correct value G_{α} = Y_{α} for α ∈ A of degree d(α) = 0. We suppose thus Proposition 3.2 correct up to degree n in Y_{A}.

The contribution e(T) to G_{α} of a coloured tree (α; T_{1}, …, T_{d(α)}) ∈ CT_{α} containing n + 1 coloured vertices factorizes uniquely as

e(α; T_{1}, …, T_{d(α)}) = Y_{α}ẽ_{1} ⋯ ẽ_{d(α)}

where the contribution ẽ_{k}, associated to the k-th son T_{k} of the root, is given by X if T_{k} = () is trivial and by w(k)_{α,β_{k}}e(T_{k}) if T_{k} = (β_{k}; T_{k,1}, …, T_{k,d(β_{k})}) ∈ CT_{β_{k}} is non-trivial with root colour β_{k}. The total degree of the product ẽ_{1} ⋯ ẽ_{d(α)} in Y_{A} is exactly n and each such product of total degree n in Y_{A} consisting of d(α) monomials with the k-th factor in X + ∑_{β∈A} w(k)_{α,β}G_{β} corresponds bijectively to a unique tree in CT_{α} and contributes a monomial of degree n + 1 in Y_{A} to G_{α}. This proves the result. □

3.2. Composed coloured trees and proofs. A composed coloured tree is a pair (T, M) where T is a coloured tree, and M ⊂ E a subset of marked edges containing all edges with endpoint a trivial leaf of T. The set CCT of composed coloured trees contains the trivial tree () = ((), ∅). Every other element (T, M) ∈ CCT can be written uniquely as (A; B_{1}, …, B_{a}) where A ∈ CT is a non-trivial coloured tree having a trivial leaves and where B_{1}, …, B_{a} are (perhaps trivial) composed coloured trees with the root of B_{k} glued to the k-th trivial leaf of A. The set M of marked edges is the union of all marked edges in B_{1}, …, B_{a}, together with all a edges of A ending at a trivial leaf of A.

Figure 2. A composed coloured tree

Figure 2 shows the composed coloured tree with colours {p, q, r, P, Q, R} and 6 marked edges represented by dotted segments which is recursively encoded by

((R; (Q; (), (P; ())), (), ()); (), (q), ((P; ()); ((R; (), (r), (p)); ())), ()) .

We define the energy e(T) of a composed coloured tree by e(T) = X if T is trivial and recursively by

e(A; B_{1}, …, B_{a}) = e(A) ∘_{X} (e(B_{1}), …, e(B_{a}))

otherwise, where the composition ∘_{X} with respect to X indicates that the k-th occurrence of X in the monomial e(A) (encoding the energy of the ordinary, non-composed coloured tree A) has to be replaced by the energy e(B_{k}) of the composed coloured tree B_{k} attached to the k-th trivial leaf of A.

The energy e(T) of the composed coloured tree T represented in Figure 2 is given by

Y_{R} w(1)_{R,Q}Y_{Q}Xw(2)_{Q,P} Y_{P} Y_{q} Y_{P} Y_{R}Xw(2)_{R,r}Y_{r}w(3)_{R,p}Y_{p} X

and can also be obtained by removing all factors corresponding to marked edges from the energy of the associated non-composed coloured tree depicted in Figure 1.

Denoting by Ĝ_{α} = ∑_{T ∈CCT_{α}} e(T) the partition function associated to the set CCT_{α} of all composed coloured trees with a root of colour α, we have the following result involving the partition function

Ĝ_{CCT} = X + ∑_{α∈A} Ĝ_{α} = ∑_{T ∈CCT} e(T)

of the set CCT containing all composed coloured trees.

Proposition 3.3. We have

Ĝ_{α} = G_{α} ∘_{X} Ĝ_{CCT}

where the composition ∘_{X} indicates that every occurrence of X in G_{α} has to be replaced by the generating series Ĝ_{CCT} associated to all composed coloured trees.

Proof. This reflects simply the recursive definition of the energy of a non-trivial composed coloured tree T = (A; B_{1}, …, B_{a}) ∈ CCT_{α} with root colour α. □

The following result, analogous to Proposition 3.2, characterizes the formal power series Ĝ_{α} = ∑_{T ∈CCT_{α}} e(T) recursively.

Proposition 3.4. We have

Ĝ_{α} = Y_{α} (Ĝ_{CCT} + ∑_{β∈A} w(1)_{α,β}Ĝ_{β}) ⋯ (Ĝ_{CCT} + ∑_{β∈A} w(d(α))_{α,β}Ĝ_{β})

where Ĝ_{CCT} = X + ∑_{α∈A} Ĝ_{α}.

Proof. The energy e(T) of a composed coloured tree (T, M) with

T = (α; T_{1}, …, T_{d(α)}) ∈ CT_{α}

a coloured tree and M a suitable subset of marked edges in T, is recursively given by

Y_{α}w̃(1)_{α,β_{1}}e(T_{1}, M_{1}) ⋯ w̃(d(α))_{α,β_{d(α)}}e(T_{d(α)}, M_{d(α)})

where w̃(k)_{α,β_{k}} = 1 if the edge relating the root of T to its k-th son is marked (and β_{k} may be undefined in this case) and where w̃(k)_{α,β_{k}} = w(k)_{α,β_{k}} otherwise with β_{k} denoting the colour of the k-th son of the root. In the marked case, e(T_{k}, M_{k}) can be an arbitrary monomial of Ĝ_{CCT}. In the case of an ordinary edge ending at a son of colour β_{k}, the energy e(T_{k}, M_{k}) can be an arbitrary monomial of Ĝ_{β_{k}}. Summing over all possibilities, we get

Ĝ_{α} = Y_{α}E_{1} …, E_{d(α)}

where E_{k} = Ĝ_{CCT} + ∑_{β∈A} w(k)_{α,β}Ĝ_{β}. □

Proof of Theorem 2.3. Proposition 3.2 shows that the formal power series G_{α} appearing in Theorem 2.3 coincide with the generating series ∑_{T ∈CT_{α}} e(T) (denoted by the same letter G_{α}) associated to CT_{α}.

The identity Ĝ_{CCT} = X+∑_{α∈A} Ĝ_{α} and Proposition 3.4 show that the formal power series Ĝ_{α} involved in Theorem 2.3 coincide with the generating series ∑_{T ∈CCT_{α}} e(T) associated to CCT_{α}.

Summing the equality of Proposition 3.3 over α ∈ A ends the proof. □

4. A combinatorial proof of G_{α} = Ĝ_{α} ∘_{X} (X − ∑_{β∈A} G_{β})

The equality Ĝ_{α} = G_{α} ∘_{X} (X + ∑_{β∈A} Ĝ_{β}) of Proposition 3.3 has a “dual” formulation as follows.

Proposition 4.1. We have

G_{α} = Ĝ_{α} ∘_{X} (X − ∑_{β∈A} G_{β}) .

This section is devoted to a direct combinatorial proof of this proposition. Summing the identity of Proposition 4.1 over α ∈ A yields

G = Ĝ ∘_{X} (X − G)

which is the “dual” statement of Theorem 2.3. This identity is of course equivalent to Theorem 2.3 or to Corollary 2.4.

Proof of Proposition 4.1. Let M be the set of marked edges of a non-trivial composed coloured tree (T, M). A marked edge is trivial if it contains a trivial (uncoloured) leaf. We denote by M^{t} ⊂ M the set of all trivial edges and by M^{o} = M \ M^{t} the complementary set of ordinary marked edges in M. The skeleton SK(T, M) of a non-trivial composed coloured tree (T, M) is the plane rooted tree with uncoloured vertices obtained by forgetting all colours and contracting all unmarked edges and all trivial marked edges in (T, M). Edges of SK(T, M) are thus in bijection with ordinary marked edges of (T, M) and vertices of SK(T, M) correspond to (non-composed) coloured trees involved in the recursive definition of (T, M) = (A; B_{1}, …, B_{d(α)}). The (non-composed) coloured tree A corresponds thus to the root r̃ of the skeleton SK(T, M). Sons of r̃ correspond to the ordinary coloured trees involved in the subset {B_{i_{1}}, …, B_{i_{k}}} ⊂ {B_{1}, …, B_{d(α)}} of all composed coloured trees in {B_{1}, …, B_{d(α)}} which are non-trivial, etc.

Figure 3. A skeleton of a composed coloured tree

Figure 3 depicts the skeleton of the composed coloured tree represented in Figure 2. Its four vertices (labelled 1, …, 4 for the convenience of the reader) correspond to the following four coloured trees:

(R; (Q; (), (P; ())), (), ()) for the root vertex 1
(q)  for vertex 2
(P; ())  for vertex 3
(R; (), (r), (p))  for vertex 4

An edge E of the skeleton SK(T, M) is trivial if E contains a leaf. We denote by T ESK(T, M) the set of all trivial edges in the skeleton SK(T, M) of a non-trivial composed coloured tree (T, M). A signed composed coloured tree is a non-trivial composed coloured tree (T, M) together with a sign-function s : T ESK(T, M) ⟶ {±1}. The set T ESK of trivial edges in the skeleton depicted in Figure 3 for example consists of the two edges {1, 2} and {3, 4}.

We define the energy of a signed composed coloured tree (T, M, s) as

e(T, M, s) = e(T, M) ∏_{E∈T ESK(T,M)} s(E)

with e(T, M) denoting the energy of the composed coloured tree (T, M) obtained by forgetting the sign-function s. The definition of e(T, M, s) implies that the 2^{♯(T ESK(T,M))} energies (corresponding to all possibilities for the sign function s) coming from a fixed composed coloured tree (T, M) cancel pairwise out and sum thus up to 0 if ♯(T ESK(T, M)) > 0. If ♯(T ESK(T, M)) = 0, the underlying composed coloured tree is of the form (T, M) = (A; (), (), …, ()) and corresponds to a non-composed coloured tree since all its marked edges are trivial. There is thus only one possibility for the sign function (defined on the empty set) giving rise to a signed energy corresponding to the energy e(A) of the coloured tree A. Denoting by SCCT_{α} the set of all signed composed coloured trees with root colour α we have thus

∑_{(T,M,s)∈SCCT_{α}} e(T, M, s) = ∑_{T ∈CT_{α}} e(T) = G_{α} .

On the other hand, the definition of the energy e(T, M, s) of a signed composed coloured tree shows easily that we have

∑_{(T,M,s)∈SCCT_{α}} e(T, M, s) = Ĝ_{α} ∘_{X} (X − ∑_{β∈A} G_{β}) .

This completes the proof of Proposition 4.1. □

5. Inversion of power series

We work in this section over a commutative ring 𝕂 and set Y_{α} = 1 for all α ∈ A.

For a natural integer l ≥ 1, we consider the alphabet

A = {1, …, l} × {2, 3, 4, … } ⊂ ℕ^{2}

with degree function d(i, j) = j ≥ 2 and weight-matrices w(k) having coefficients

w(k)_{(i,j),(i′,j′)} = \begin{cases}α(k)_{j} & if i = i′, \\ 0 & otherwise, \end{cases}

where α(k)_{j} ∈ 𝕂 are arbitrary. This choice of weight-matrices leads to restricted partition functions G_{(i,j)}(X) and Ĝ_{(i,j)}(X) which are independent of i. Thus the formal power series G_{∗}(X) = ∑_{j=2}^{∞} G_{(i,j)}(X) and Ĝ_{∗}(X) = ∑_{j=2}^{∞} Ĝ_{(i,j)}(X) are well-defined and given by the equations

\begin{matrix}G_{∗}(X) = ∑_{j=2}^{∞} ∏_{k=1}^{j} (X + α(k)_{j}G_{∗}(X)) , \\ Ĝ_{∗}(X) = ∑_{j=2}^{∞} ∏_{k=1}^{j} (X + (l + α(k)_{j})Ĝ_{∗}(X)) . \end{matrix}

Corollary 2.4 shows that we have formally

(X − lG_{∗}(X)) ∘ (X + lĜ(X)) = (X + lĜ(X)) ∘ (X − lG_{∗}(X)) = X .

Comparing coefficients of X^{k} yields algebraic identities and the above identity holds thus for all l ∈ 𝕂. This gives recipes (other than the celebrated Lagrange inversion formula) for computing the reciprocal or reverse series of power series having the form X +lX^{2} +… with l ≠ 0. For an arbitrary formal power series y(x) = αx + βx^{2} + … (with α ∈ 𝕂 invertible), one can use a homographic transformation and set

Y (x) = y (\frac{α}{β + lα^{2}} \frac{x}{x + \frac{α^{2}}{β+lα^{2}}} ) = x − lx^{2} + …

for l ≠ 0 such that β + lα^{2} ≠ 0. The reciprocal formal power series (or compositional inverse) ŷ of y is then given by

ŷ = \frac{α}{β + lα^{2}} \frac{Ŷ}{Ŷ + \frac{α^{2}}{β+lα^{2}}}

where Ŷ is the reciprocal formal power series of Y = x − lx^{2} + . . ..

Remark 5.1. The method outlined above is especially interesting for reversing formal power series of the form X − lG(X) with G(X) ∈ X^{2}𝕂[[X]] a formal power series having a double root at the origin and l a parameter.

Remark 5.2. One could of course also work with slightly more general weightmatrices defined by

w(k)_{(i,j),(i′,j′)} = \begin{cases}α(k)_{j} & if i = i′, \\ β(k)_{j} & otherwise, \end{cases}

where α(k)_{j}, β(k)_{j} ∈ 𝕂. The restricted partition functions G_{(i,j)}(X) and Ĝ_{(i,j)}(X) are again independent of i and the associated formal power series G_{∗}(X) = ∑_{j=2}^{∞} G_{(i,j)}(X) and Ĝ_{∗}(X) = ∑_{j=2}^{∞} Ĝ_{(i,j)}(X) are defined by

\begin{matrix}G_{∗}(X) = ∑_{j=2}^{∞} ∏_{k=1}^{j} (X + (α(k)_{j} + (l − 1)β(k)_{j})G_{∗}(X)) , \\ Ĝ_{∗}(X) = ∑_{j=2}^{∞} ∏_{k=1}^{j} (X + (l + α(k)_{j} + (l − 1)β(k)_{j})Ĝ_{∗}(X)) . \end{matrix}

The evaluations α̃(k)_{j} = α(k)_{j} + (l − 1)β(k)_{j} transform these equations into the former equations.

5.1. A few examples. Setting α(k)_{j} = 1 for all j ≥ 2 and for all k, 1 ≤ k ≤ j, we get the equation

G_{∗} = \frac{(X + G_{∗})^{2}}{1 − (X + G_{∗})}

with solution

G_{∗} = \frac{1 − 3x − \sqrt{1 − 6x + x^{2}}}{4} = x^{2} + 3x^{3} + 11x^{4} + 45x^{5} + 197x^{6} + ….

The formal power series Y = X − lG_{∗} satisfies thus the algebraic equation P (X, Y) = 0 where

P (X, Y) = (X − Y)(l − (1 + l)X + Y) − ((1 + l)X − Y)^{2} .

Similarly, Ŷ = X +lĜ_{∗} (where Ĝ_{∗} = \frac{(X+(1+l)Ĝ_{∗})^{2}}{1−(X+(1+l)Ĝ_{∗})}) satisfies P (Ŷ , X) = 0. The specialization l = −1 leads to

Y = \frac{1 + X − \sqrt{1 − 6X + X^{2}}}{4} = X + X^{2} + 3X^{3} + 11X^{4} + …

(cf. Sequence A1003 in [2]) and

Ŷ = X − \frac{X^{2}}{1 − X} = X − X^{2} − X^{3} − X^{4} − …

The choice α(k)_{j} = 1 if k = 1 and α(k)_{j} = 0 otherwise leads to G_{∗} = \frac{X^{2}}{1−2X} with Y = X − lG_{∗} = X \frac{1−(l+2)X}{1−2X} root of (X − Y)(1 − X) − ((l + 1)X − Y)X. The specialization l = −1 yields Y = X +X^{2} +2X^{3} +4X^{4} +8X^{5} +16X^{6} +… with reciprocal series

Ŷ = \frac{1 + 2X − \sqrt{1 + 4X^{2}}}{2} = X − X^{2} + X^{4} − 2X^{6} + 5X^{8} − 14X^{10} + 42X^{12} − …

closely related to Catalan numbers (cf. A108 in [2]).

Similarly, α(k)_{j} = 1 for k ≤ 2 and 0 otherwise leads to

\begin{aligned}G_{∗} & = & \frac{(X + G_{∗})^{2}}{1 − X} = \frac{1 − 3X − \sqrt{1 − 6X + 5X}}{2} \\ & = & X^{2} + 3X^{3} + 10X^{4} + 36X^{5} + 137X^{6} + 543X^{7} + … \end{aligned}

(cf. A2212 of [2]) with Y = X − lG_{∗} root of

l(1 − X)(X − Y) − ((l + 1)X − Y)^{2} .

More generally, considering a periodic sequence α(1)_{j}, j = 2, 3, … and setting either α(k)_{j} = 0 for k > 2 or α(k)_{j} = α(1)_{j} yields a formal power series G_{∗} which is algebraic.

6. A generalization involving different vertex-types

Consider a set VT of vertex-types and an alphabet A (with a degree function d : A ⟶ ℕ as in Section 2) together with an application vt : A ⟶ VT associating to each element of A its vertex-type.

A coloured tree with vertex-types in VT is a coloured tree T together with an application t : T L(T) ⟶ VT from the set T L(T) of its trivial leaves into VT . We can thus associate a vertex-type τ(v) ∈ VT to every vertex v of such a tree: if v is a trivial leaf, we set τ(v) = t(v). If v is an ordinary leaf of colour α ∈ A, we set τ(v) = vt(α). For the sake of simplicity, we will henceforth identify the functions t, vt and τ with τ. (This identification is slightly abusive: the three functions are defined on different sets.)

We denote by X_{VT} a set of variables indexed by VT and define the energy e(T) of a coloured tree T with vertex-types in VT as X_{τ(r)} if T is a trivial tree reduced to its root r (which is a trivial leaf) of vertex-type τ(r) and as the usual, recursively defined, product otherwise.

Figure 4. A coloured tree with vertex types

The energy of the tree represented in Figure 4 (with vertex types {1, 2}) for example is given by

Y_{A}w(1)_{A,B}Y_{B}X_{2}w(3)_{A,D}Y_{D}X_{1}w(2)_{D,C}Y_{C} .

Composed coloured trees with vertex types are defined in the obvious way. Their energy is again the energy of the associated ordinary coloured tree, after removing the contribution of all marked edges.

We denote by CT_{τ} the set of all non-trivial coloured trees with a root r of vertex-type τ = τ(r) (and having thus its colour in the subset vt^{−1}(τ) ⊂ A).

The set CCT_{τ} is defined analogously. Its elements are all non-trivial composed coloured trees with root type τ and root colour in vt^{−1}(τ) ⊂ A.

Defining G_{τ} = ∑_{T ∈CT_{τ}} e(T) and Ĝ_{τ} = ∑_{T ∈CCT_{τ}} e(T) we have the following result which is analogous to Theorem 2.3.

Theorem 6.1. We have

Ĝ_{τ} = G_{τ} ∘_{X_{VT}} (X_{σ} + Ĝ_{σ})_{σ∈VT}

where ∘_{X_{VT}} indicates that each occurrence of X_{σ} (with σ ∈ VT ) in G_{τ} has to be replaced by the formal power series X_{σ} + Ĝ_{σ}.

It follows easily that the systems of formal power series

(X_{τ} − G_{τ})_{τ∈VT} and (X_{τ} + Ĝ_{τ})_{τ∈VT}

are reciprocal under composition with respect to the variables X_{VT}.

Denoting by G_{α} the generating function of all non-trivial rooted trees with vertex-type in VT and a root of colour α ∈ A and setting X = ∑_{τ∈VT} X_{τ} Proposition 3.2 is valid.

Similarly, Proposition 3.4 holds for the similarly defined power series Ĝ_{α} involving composed coloured trees after setting Ĝ_{CCT} = ∑_{τ∈VT} X_{τ} +∑_{α∈A} Ĝ_{α}.

7. Loday’s example (i)

This section contains a partial analysis of example (i) in [3] and was the starting point of this paper. The framework is somewhat simpler than in the previous sections: we work over the commutative ground field ℂ of complex numbers. We consider the alphabet

A = {∘, N, NW , W, SW , S, SE, E, NE}

of nine elements suggesting the graphical notation of [3]. All elements of A are of degree 2 (and we are thus working with 2-regular trees). We set X = −t, Y_{α} = −1, ∀α ∈ A in order to stick to [3], cf. Remark 2.7. We consider weight-matrices w(1), w(2) with coefficients w(k)_{α,β} = −M_{k}(α, β), k = 1, 2 where M_{1}, M_{2} are the two 9 × 9 matrices

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 0 & 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \end{matrix} ) , ( \begin{matrix}0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \end{matrix} )

Setting g_{α} = −G_{α}, Proposition 3.2 corresponds to the equations

g_{∘} = (−t + g_{∘})(−t + g_{N} + g_{NW} + g_{W})
g_{N} = (−t + g_{∘} + g_{N} + g_{NW})(−t + g_{W})
g_{NW} = (−t + g_{∘} + g_{N} + g_{NW} + g_{W})(−t)
g_{W} = (−t + g_{∘} + g_{NW} + g_{W})(−t + g_{N})
g_{SW} = (−t + g_{∘} + g_{N} + g_{NW} + g_{W} + g_{SW})(−t + g_{S})
g_{S} = (−t + g_{∘} + g_{N})(−t + g_{NW} + g_{W} + g_{SW} + g_{S})
g_{SE} = (−t + g_{∘} + g_{N} + g_{NW} + g_{W} + g_{S})
(−t + g_{SW} + g_{SE} + g_{E} + g_{NE})
g_{E} = (−t + g_{∘} + g_{N} + g_{W})(−t + g_{NW} + g_{E} + g_{NE})
g_{NE} = (−t + g_{∘} + g_{N} + g_{NW} + g_{W})(−t + g_{E} + g_{NE}) .

One sees easily that we have

g_{o} = g_{N} = g_{W} .

Eliminating g_{N}, g_{W} we get the simpler equations:

\begin{aligned}g_{∘} & = & (−t + g_{∘})(−t + 2g_{∘} + g_{NW}) \\ g_{NW} & = & (−t + 3g_{∘} + g_{NW})(−t) \\ g_{SW} & = & (−t + 3g_{∘} + g_{NW} + g_{SW})(−t + g_{S}) \\ g_{S} & = & (−t + 2g_{∘})(−t + g_{∘} + g_{NW} + g_{S} + g_{SW}) \\ g_{E} & = & (−t + 3g_{∘})(−t + g_{NW} + g_{E} + g_{NE}) \\ g_{NE} & = & (−t + 3g_{∘} + g_{NW})(−t + g_{E} + g_{NE}) \\ g_{SE} & = & (−t + 3g_{∘} + g_{NW} + g_{S})(−t + g_{SW} + g_{SE} + g_{E} + g_{NE}) \end{aligned}

where functions above a horizontal line are independent of functions below the line.

Computations (done with Maple) using Gröbner bases show that

y = −t + g_{∘} + g_{N} + g_{NW} + g_{W} + g_{SW} + g_{S} + g_{SE} + g_{E} + g_{NE}

(corresponding to the power series X − G = X − ∑_{α∈A} G_{α} of Corollary 2.4) satisfies the algebraic equation P (y(t), t) = 0 where

P (y, t) = c_{0} + c_{1} y + c_{2} y^{2} + c_{3} y^{3} + c_{4} y^{4}

with

c_{0} = t (288 t^{31} − 1008 t^{30} − 17696 t^{29} + 35124 t^{28} + 513042 t^{27}

−352654 t^{26} − 8834409 t^{25} − 2315100 t^{24} + 94293622 t^{23} +92841847 t^{22} − 608228325 t^{21} − 1031578684 t^{20} +2072381165 t^{19} + 5859780674 t^{18} − 1127775119 t^{17} −16287829166 t^{16} − 15833938922 t^{15} + 9251292427 t^{14} +38652814035 t^{13} + 44572754075 t^{12} + 10866248029 t^{11} −40129564125 t^{10} − 59007425756 t^{9} − 36829453004 t^{8} −10216139916 t^{7} − 63849664 t^{6} + 693364800 t^{5} + 187804368 t^{4} +24111840 t^{3} + 1694752 t^{2} + 63488 t + 1024)

c_{1} = −768 t^{31} + 1488 t^{30} + 44636 t^{29} − 49538 t^{28} − 1198111 t^{27}

+359773 t^{26} + 19127286 t^{25} + 7602856 t^{24} − 192894854 t^{23} −193322898 t^{22} + 1208988418 t^{21} + 1968967542 t^{20} −4212884427 t^{19} − 10893520130 t^{18} + 4099837581 t^{17} +31343794098 t^{16} + 22508418249 t^{15} − 27437733598 t^{14} −67449042813 t^{13} − 62529644946 t^{12} − 3629552721 t^{11} +84243589625 t^{10} + 130637976096 t^{9} + 104165077688 t^{8} +50704667612 t^{7} + 15902199040 t^{6} + 3290858704 t^{5} +451630576 t^{4} + 40498432 t^{3} + 2274080 t^{2} + 72704 t + 1024

c_{2} = t (680 t^{29} − 932 t^{28} − 39270 t^{27} + 33926 t^{26} + 1020385 t^{25}

−335552 t^{24} − 15580483 t^{23} − 2999586 t^{22} + 151572589 t^{21} +104425399 t^{20} − 945694543 t^{19} − 1131146667 t^{18} +3558106593 t^{17} + 6544185368 t^{16} − 6226627151 t^{15} −20759382401 t^{14} − 4197042728 t^{13} + 29133893401 t^{12} +33005986439 t^{11} + 5921959164 t^{10} − 22398414511 t^{9} −37477032816 t^{8} − 35648192872 t^{7} − 21631096056 t^{6} −8298733544 t^{5} − 1992896768 t^{4} − 295849440 t^{3} −26179392 t^{2} − 1255424 t − 24832)

c_{3} = −t^{2} (t − 2) (t + 1) (2 t^{4} + 6 t^{3} − 11 t^{2} − 30 t − 4)

(124 t^{21} − 398 t^{20} − 5146 t^{19} + 14694 t^{18} + 92616 t^{17} − 213234 t^{16} −966327 t^{15} + 1518831 t^{14} + 6391763 t^{13} − 5003278 t^{12} −26227554 t^{11} + 1248286 t^{10} + 58532080 t^{9} + 36103178 t^{8} −41699603 t^{7} − 64544195 t^{6} − 41818519 t^{5} − 21472740 t^{4} −8578026 t^{3} − 1961960 t^{2} − 218928 t − 9296)

and

c_{4} = (t^{2} − 2 t − 2)(t^{2} − 2 t − 7)(t − 2)^{2}(t + 1)^{2}

(2 t^{4} + 6 t^{3} − 11 t^{2} − 30 t − 4)^{2}t^{5} (8 t^{7} − 10 t^{6} − 171 t^{5} + 209 t^{4} + 948 t^{3} − 721 t^{2} − 1892 t − 249).

The first coefficients of the series y(t) are − t + 9 t^{2} − 49 t^{3} + 284 t^{4} − 1735 t^{5} + 10955 t^{6} − 70695 t^{7} + 463087 t^{8}

− 3066450 t^{9} + 20471641 t^{10} − 137540539 t^{11} + 928791019 t^{12} ∓ … The reciprocal function

ŷ = −t + 9t^{2} − 113t^{3} + 1724t^{4} − 29309t^{5} + 532896t^{6} − …

satisfies the polynomial equation P (t, ŷ) = 0 with P (y, t) = c_{0} + c_{1}y + c_{2}y^{2} + c_{3}y^{3} + c_{4}y^{4} as above. Corollary 2.4 shows that ŷ is also defined by

ŷ = −t + ĝ_{∘} + ĝ_{N} + ĝ_{NW} + ĝ_{W} + ĝ_{SW} + ĝ_{S} + ĝ_{SE} + ĝ_{E} + ĝ_{NE} where ĝ_{∘}, ĝ_{N}, ĝ_{NW} , ĝ_{W} , ĝ_{SW} , ĝ_{S}, ĝ_{SE}, ĝ_{E}, ĝ_{NE} satisfy the “complementary” equations

ĝ_{∘} = (−t + ĝ_{N} + ĝ_{NW} + ĝ_{W} + ĝ_{SW} + ĝ_{S} + ĝ_{SE} + ĝ_{E} + ĝ_{NE})
(−t + ĝ_{∘} + ĝ_{SW} + ĝ_{S} + ĝ_{SE} + ĝ_{E} + ĝ_{NE})
ĝ_{N} = (−t + ĝ_{W} + ĝ_{SW} + ĝ_{S} + ĝ_{SE} + ĝ_{E} + ĝ_{NE})
(−t + ĝ_{∘} + ĝ_{N} + ĝ_{NW} + +ĝ_{SW} + ĝ_{S} + ĝ_{SE} + ĝ_{E} + ĝ_{NE})
ĝ_{NW} = (−t + ĝ_{SW} + ĝ_{S} + ĝ_{SE} + ĝ_{E} + ĝ_{NE})
(−t + ĝ_{∘} + ĝ_{N} + ĝ_{NW} + ĝ_{W} + ĝ_{SW} + ĝ_{S} + ĝ_{SE} + ĝ_{E} + ĝ_{NE})
ĝ_{W} = (−t + ĝ_{N} + ĝ_{SW} + ĝ_{S} + ĝ_{SE} + ĝ_{E} + ĝ_{NE})
(−t + ĝ_{∘} + ĝ_{NW} + ĝ_{W} + ĝ_{SW} + ĝ_{S} + ĝ_{SE} + ĝ_{E} + ĝ_{NE})
ĝ_{SW} = (−t + ĝ_{S} + ĝ_{SE} + ĝ_{E} + ĝ_{NE})
(−t + ĝ_{∘} + ĝ_{N} + ĝ_{NW} + ĝ_{W} + ĝ_{SW} + ĝ_{SE} + ĝ_{E} + ĝ_{NE})
ĝ_{S} = (−t + ĝ_{NW} + ĝ_{W} + ĝ_{SW} + ĝ_{S} + ĝ_{SE} + ĝ_{E} + ĝ_{NE})
(−t + ĝ_{∘} + ĝ_{N} + ĝ_{SE} + ĝ_{E} + ĝ_{NE})
ĝ_{SE} = (−t + ĝ_{SW} + ĝ_{SE} + ĝ_{E} + ĝ_{NE})
(−t + ĝ_{∘} + ĝ_{N} + ĝ_{NW} + ĝ_{W} + ĝ_{S})
ĝ_{E} = (−t + ĝ_{NW} + ĝ_{SW} + ĝ_{S} + ĝ_{SE} + ĝ_{E} + ĝ_{NE})
(−t + ĝ_{∘} + ĝ_{N} + ĝ_{W} + ĝ_{SW} + ĝ_{S} + ĝ_{SE})
ĝ_{NE} = (−t + ĝ_{SW} + ĝ_{S} + ĝ_{SE} + ĝ_{E} + ĝ_{NE})
(−t + ĝ_{∘} + ĝ_{N} + ĝ_{NW} + ĝ_{W} + ĝ_{SW} + ĝ_{S} + ĝ_{SE})

Remark 7.1. For computations of huge terms in the series expansion of an algebraic function, one can use the following well-known trick: any algebraic function y(t) = ∑ a_{n}t^{n} of degree d satisfies a linear differential equation

∑_{k=0}^{d} q_{k}(t)y^{(k)}(t) = 0

with polynomial coefficients q_{0}, …, q_{t} ∈ ℂ[t]. This allows a recursive computations of a_{n} with time and memory requirements linear in n. In our case, we get

q_{0}(t)y + q_{1}(t)y′ + q_{2}(t)y′′ + q_{3}(t)y^{(3)} + q_{4}(t)y^{(4)} = 0

where q_{0}, …, q_{4} ∈ ℤ[t] are polynomials of degrees respectively 150, 151, 155, 156 and 157.

7.1. Asymptotics. The asymptotic growth rate of the coefficients of y(t) is governed by the distance of the origin to the first ramification point of the corresponding sheet, see [4]. Ramifications are above the roots of the discriminant D(t) of P (y, t) with respect to y. This discriminant is given by

D(t) = r_{1}^{2} r_{2} r_{3}^{2} r_{4}^{2} r_{∞}

where

r_{1} = t^{4} − 4 t^{3} + 6 t^{2} + 8 t + 1
r_{2} = t^{13} − 3 t^{12} − 16 t^{11} + 100 t^{10} − 86 t^{9} − 222 t^{8} + 312 t^{7} − 544 t^{6}
+4845 t^{5} + 10665 t^{4} + 9536 t^{3} + 4084 t^{2} + 528 t + 16
r_{3} = 20 t^{16} + 50 t^{15} − 849 t^{14} − 937 t^{13} + 11563 t^{12} + 7833 t^{11}
−64177 t^{10} − 58882 t^{9} + 141152 t^{8} + 259280 t^{7} + 82253 t^{6}
−366913 t^{5} − 698955 t^{4} − 468324 t^{3} − 122700 t^{2} − 13720 t − 552
r_{4} = 5760 t^{53} + 8864 t^{52} − 425056 t^{51} + ⋯ − 7200309248 t − 76152832

(r_{4} is not involved in coarse asymptotics of y(t)). The roots of the polynomial

r_{∞} = t^{6} (t − 2)^{2} (t + 1)^{3} (2 t^{4} + 6 t^{3} − 11 t^{2} − 30 t − 4)^{2}

are critical points for the critical value ∞.

Since the coefficients of y(t) have alternating signs, the “smallest” singularity of y(t) is on the negative real halfline. The following table resumes the relevant data for its computation. More precisely, the algebraic function defined by P has a ramification of order 3 with y = ∞ above t = 0. The remaining sheet is unramified above t = 0 and defines the generating function y(t) under consideration.

The table contains the following informations: the first column shows the argument t considered in the corresponding row. The second column indicates the factor of the discriminant D(t) if t is a root of D(t). The remaining column displays information about the inverse images of t defined by the algebraic equation of y(t).

We have

t_{0} = 0  r_{∞} y_{1} = y_{2} = y_{3} = ∞, y_{4} = 0
t_{0} > t > t_{1}  y_{1} < y_{2} < y_{3} < 0 < y_{4}
t_{1} ∼ −0.04355 r_{2} y_{1} ∼ −2922 < y_{2} = y_{3} ∼ −1.083 < 0 < y_{4} ∼ 0.066
t_{1} > t > t_{2}  y_{1} < 0 < y_{4}, y_{2} = \overline{y_{3}} ∈ ℂ \ ℝ
t_{2} ∼ −0.1118 r_{3} y_{1} ∼ −82.3 < y_{2} = y_{3} ∼ 0.2194 < y_{4} ∼ 0.4499
t_{2} > t > t_{3}  y_{1} < 0 < y_{4}, y_{2} = \overline{y_{3}} ∈ ℂ \ ℝ
t_{3} ∼ −0.14047  0 < y_{4} ∼ 4.113, y_{1} = ∞, y_{2} = \overline{y_{3}} ∼ −2.98 ± 8.481i
t_{3} > t > t_{4}  0 < y_{4} < y_{1}, y_{2} = \overline{y_{3}} ∈ ℂ \ ℝ
t_{4} ∼ −0.14118 r_{∞} 0 < y_{4} ∼ 8.692 < y_{1} ∼ 28.07, y_{2} = y_{3} = ∞
t_{4} > t > t_{5}  0 < y_{4} < y_{1}, y_{2} = \overline{y_{3}} ∈ ℂ \ ℝ
t_{5} ∼ −0.14127 r_{2} 0 < y_{4} = y_{1} ∼ 14.89, y_{2} = \overline{y_{3}} ∼ 23.95 ± 59.72i

The convergence radius of the series for y(t) is of course given by |t_{5}| = −t_{5} and the asymptotic growth of the coefficients of y(t) is roughly exponential with argument

1/t_{5} ∼ −7.07857458512410303820641252737538586816317182 .

A slightly more precise asymptotic behaviour of the coefficients of y(t) can be computed as follows:

At the root

ρ = t_{5} ∼ −.14127137998962933757540882196178714222253950575630 of r_{2}, the ramified sheet corresponds to the double root

y_{ρ} ∼ 14.88738808602894055277970788094544394

of P (y, ρ) ∈ ℂ[y]. (Caution: when computing y_{ρ} as a root of P (y, ρ) one loses roughly half the digits since an error of order ϵ on ρ induces an error of order \sqrt{ϵ} on the corresponding two roots approximating the double root y_{ρ} of P (y, ρ). A better strategy is of course to compute y_{ρ} as a (simple) root of the derivative \frac{d}{dy}P (y, ρ) of P (y, ρ)).

In a small open neighbourhood of ρ we get now a Puiseux series expansion

y(t) = h(t) + g(t)\sqrt{ρ − t}

with h(t), g(t) holomorphic. Since the discriminant D(t) contains no other roots of absolute value |ρ|, the asymptotics of the generating function y(t) are roughly given by

γ_{ρ}\sqrt{ρ}\sqrt{1 − t/ρ}
= γ_{ρ}\sqrt{ρ} ∑_{n=0}^{∞} \binom{1/2}{n} (\frac{−t}{ρ})^{n}
= γ_{ρ}\sqrt{ρ} (1 − ∑_{n=1}^{∞} \frac{1}{2} \frac{1/2·3/2···(n−3/2)}{n!} (\frac{t}{ρ})^{n})
= γ_{ρ}\sqrt{ρ} (1 − ∑_{n=1}^{∞} \frac{1·3···(2n−3)}{2^{n} n!} (\frac{t}{ρ})^{n})
= γ_{ρ}\sqrt{ρ} (1 − \frac{1}{2} ∑_{n=1}^{∞} \frac{(2n−2)!}{4^{n−1} n! (n−1)! ρ^{n}} t^{n})

where γ(ρ) = g(ρ). Since

\frac{(2n − 2)!}{n! (n − 1)!} ∼ \frac{1}{n} \frac{\sqrt{4π(n − 1)} 4^{n−1} (n − 1)^{2n−2} e^{−2n+2}}{2π (n − 1) (n − 1)^{2(n−1)} e^{−2(n−1)}} ∼ \frac{4^{n−1}}{\sqrt{π} n^{3/2}}

we get the asymptotics

a_{n} ∼ \frac{γ_{ρ}}{2 \sqrt{π} n^{3/2} ρ^{n−1/2}} .

The constant γ_{ρ} can be computed by remarking that

0 = P (h(t) + \sqrt{ρ − t} g(t), t)
= P (y_{ρ} + γ_{ρ}\sqrt{ρ − t} + O((ρ − t)), t)
= \frac{∂^{2}P}{∂y^{2}} |_{(y_{ρ},ρ)} \frac{γ_{ρ}^{2} (ρ−t)}{2} + \frac{∂P}{∂t} |_{(y_{ρ},ρ)}(t − ρ) + O((ρ − t)^{3/2}))

yielding

γ_{ρ}\sqrt{ρ} = \sqrt{2ρ \frac{\frac{∂P}{∂t} |_{(y_{ρ},ρ)}}{\frac{∂^{2}P}{∂y^{2}} |_{(y_{ρ},ρ)}}} ∼ 337.171657540870 .

We have thus asymptotically

a_{n} ∼ 95.11436852604511894068836 ρ^{−n} n^{−3/2}

with ρ ∼ −.1412713799896293375754088219617871422225395057563006418, (cf. Formula 10.64 in [4]).

References

[1] L. Carlitz, R. Scoville, T. Vaughan, Enumeration of pairs of sequences by rises, falls and levels, Manuscripta Math. 19 (1976), 211–243.

[2] N.J.A. Sloane, Encyclopedia of Integer sequences,

   http://www.research.att.com/~njas/sequences/index.html.

[3] J.L. Loday, Inversion of integral series enumerating planar trees, Séminaire Lotharingien Combin. 53 (2005), Article B53d, 16 pp.

[4] A.M. Odlyzko, Asymptotic Enumeration Methods, in Handbook of Combinatorics, vol. 2, R.L. Graham, M. Grötschel, L. Lovász, eds., Elsevier (1995), 1063–1229.

[5] S.F. Parker, The Combinatorics of Functional Composition and Inversion, Ph.D. thesis, Brandeis (1993).

Institut Fourier, Laboratoire de Mathématiques, UMR 5582 (UJF-CNRS), BP 74, 38402 St. Martin d’Hères Cedex (France).

e-mail: Roland.Bacher@ujf-grenoble.fr

Laboratoire d’informatique de l’École Polytéchnique, UMR 7161 (X-CNRS), École Polytéchnique, 91128 Palaiseau Cedex (France).

e-mail: Gilles.Schaeffer@lix.polytechnique.fr