Séminaire Lotharingien de Combinatoire 53 (2005), Article B53d

INVERSION OF INTEGRAL SERIES ENUMERATING PLANAR TREES

JEAN-LOUIS LODAY

Abstract. We consider an integral series f(X, t) which depends on the choice of a set X of labelled planar rooted trees. We prove that its inverse with respect to composition is of the form f(Z, t) for another set Z of trees, deduced from X. The proof is self-contained, though inspired by the Koszul duality theory of quadratic operads. In the same vein we give a conceptual proof for the formulas giving the coefficients of the inverse with respect to composition of the generic formal power series.

1. Introduction

Let I be a finite set of indices. Let Y_{n}×I^{n} be the set of planar binary rooted trees whose n vertices are labelled by elements in the index set I. Let X be a subset of Y_{2} ×I^{2} and let Z be its complement. Define X_{n} as the subset of Y_{n} × I^{n} made of labelled trees whose local patterns are in X. In other words, a tree is in X_{n} if for every pair of adjacent vertices the subtree defined by this pair is in X. By convention X_{0} = Y_{0} × I^{0} and X_{1} = Y_{1} ×I. From the definition of X_{n} it follows immediately that X_{2} = X. The set Z determines similarly a sequence Z_{n}.

The alternating generating series of X is by definition

f(X, t) := ∑_{n≥0}(−1)^{n+1}(#X_{n})t^{n+1} = −t + (#I)t^{2} − (#X)t^{3} + · · · .

Theorem. If Z is the complement of X, i.e., X ⊔ Z = Y_{2} × I^{2}, then the generating series of X and Z are inverse to each other with respect to composition:

f(X, f(Z, t)) = t.

For some choices of I and X the integer sequence (#X_{n})_{n≥0} appear in the data base “On-line Encyclopedia of Integer sequences!” [Sl], but for some others they do not.

Date: November 24, 2005.

Key words and phrases. Integer sequence, generating series, planar tree, excluded pattern, operad, Koszul duality.

Here is an application of this theorem. Given an integer sequence \underline{a} = (a_{0}, …, a_{n}, …), it is often interesting to know a combinatorial interpretation of these numbers, that is, to know a family X_{n} of combinatorial objects such that a_{n} = #X_{n}. The theorem provides a solution for some integer sequences as follows. Suppose that the inverse with respect to composition of the alternating series of \underline{a} gives an integer sequence \underline{b} which can be interpreted combinatorially by labelled trees. Then the integer sequence \underline{a} admits also such an interpretation, see 2.3.

Our proof of the theorem consists in constructing a chain complex whose Poincaré series is exactly f(X, f(Z, t)). Then we prove that this chain complex is acyclic (i.e., the homology groups are 0 except H_{1} which is of dimension 1) by reducing it to the sum of subcomplexes which turn out to be augmented chain complexes of standard simplices. Hence the Poincaré series is t.

Our proof is self-contained but the idea of considering this particular chain complex is inspired by the theory of quadratic operads. Indeed the choice of X determines a certain type of algebras, i.e., a certain quadratic operad, and the choice of Z gives the “dual operad” in the Koszul duality sense cf. [G-K]. Then the chain complex is the Koszul complex attached to this dual pair of operads. So our main theorem gives a large family of Koszul operads.

We give all the details for the case of binary trees, but this method can be generalized to planar trees. We outline the case of k-ary trees. A surprising consequence is the following property of the Catalan numbers c_{n}. The series h(t) = ∑_{n≥0}(−1)^{n+1}c_{n}t^{3n+1} is its own inverse with respect to composition: h(h(t)) = t.

The formula for the inverse of the generic formal power series is wellknown. The coefficients which show up are the numbers of the planar trees of a given type. In the last section we give a conceptual proof of this formula by using Koszul duality of an elementary operad.

After the release of the first version of this paper, I was informed by Prof. I. Gessel that his student S.F. Parker obtained the same result by combinatorial methods in her thesis (unpublished). A far reaching generalization of our result has been obtained subsequently by R. Bacher in [B] using a different technique.

2. Labelled trees

2.1. Planar binary rooted trees. Denote by Y_{n} the set of planar binary rooted trees of degree n, that is, with n vertices (with valency 2 + 1):

Y_{0} = { | } , Y_{1} = { [figure] } , Y_{2} = {L := [figure] , R := [figure] }

Y_{3} = { [figure] , [figure] , [figure] , [figure] , [figure] }

Observe that the end of the leaves and of the root are not considered as vertices. This notion of vertex is sometimes referred to as “internal vertex” in the literature.

The number of elements in Y_{n} is the so-called Catalan number c_{n} = \frac{(2n)!}{n!(n+1)!}, cf. 2.3 (b). Let I be a finite set of indices. By definition a labelled tree is a planar binary rooted tree such that each vertex is labelled by an element of I. These elements need not be distinct. Therefore the set of labelled trees of degree n is in bijection with Y_{n}×I^{n}.

An element of Y_{2} × I^{2} is either of the form (L; i_{1}, i_{2}) or of the form (R; i_{1}, i_{2}):

[figure: i_{1}; i_{2}; i_{2}; i_{1}; .]

Let X be a subset of Y_{2} × I^{2} and let Z be its complement. We define a subset X_{n} of Y_{n} × I^{n} as follows. A pair of adjacent vertices in the labelled tree y determines a subtree of degree 2, called a local pattern. The labelled tree y is in X_{n} if and only if all its local patterns belong to X. In other words we exclude all the trees which have a local pattern which belongs to Z. It is clear that X_{2} = X. By convention we define X_{0} = Y_{0} × I^{0} and X_{1} = Y_{1} × I.

The alternating generating series of X is determined by the integer sequence (#X_{n})_{n≥0} as follows:

f(X, t) := ∑_{n≥0}(−1)^{n+1}(#X_{n})t^{n+1} = −t + (#I)t^{2} − (#X)t^{3} + ….

If, instead of X, we start with Z, then we get another family Z_{n}. For n = 2, Z_{2} is the complement of X_{2}, but this property does not hold for higher n’s.

2.2. Theorem. If Z is the complement of X, i.e., X ⊔ Z = Y_{2} × I^{2}, then the generating series of X and Z are inverse to each other with respect to composition:

f(X, f(Z, t)) = t.

The proof is given in the next section.

2.3. Examples. We list a few interesting examples of integer sequences and their dual which appear in the study of quadratic operads (cf. [L3]). The notation is as follows: the sequence (a_{0}, ⋯, a_{n}, ⋯) is such that a_{n} = #X_{n} and f(t) = ∑_{n≥0}(−1)^{n+1}a_{n}t^{n+1}. The dual sequence is (b_{0}, ⋯, b_{n}, ⋯) where b_{n} = #Z_{n} and g(t) = ∑_{n≥0}(−1)^{n+1}b_{n}t^{n+1}.

Observe that a_{0} = 1, a_{1} = #I, a_{2} = #X and 0 ≤ a_{2} ≤ 2(a_{1})^{2}. In the following examples we can write g(t) as a rational function, hence we get a combinatorial interpretation of the integer sequence \underline{a} whose alternating series f(t) is determined by the functional equation g(f(t)) = t.

(a) (1, 1, 1, …, 1, …) versus itself.

• I = {1}, X = {L} and Z = {R}.

• f(t) = g(t) = \frac{−t}{1+t}.

(b) (1, 1, 2, 5, 14, 42, 132, ⋯, c_{n} = \frac{(2n)!}{(n+1)!n!}, …) versus (1, 1, 0, …, 0, …).

• I = {1}, Z = ∅, X = Y_{2}.

• g(t) = −t + t^{2}.

• We get the well known functional equation for the generating series of the Catalan numbers c(t) := ∑_{n≥0} c_{n}t^{n},

tc(t)^{2} − c(t) + 1 = 0.

(c) (1, 2, 6, 22, 90, ⋯, 2C_{n}, …) versus (1, 2, 2, …, 2, …).

• C_{n} is the super Catalan number (also called Schröder number), that is, the number of planar trees with n + 1 leaves.

• I = {1, 2}, Z = {(L; 1, 1), (R; 2, 2)} and X has 6 elements.

• It is immediate to see that Z_{n} has only two elements: the left comb indexed by 1’s and the right comb indexed by 2’s. Therefore g(t) = \frac{−t+t^{2}}{1+t}. On the other hand, one can show that, for n ≥ 2, there is a bijection between the elements of X_{n} and two copies of the set of planar trees with n+1 leaves (see [L-R2] for a variant of this result). The theorem gives the well known functional equation for the generating series of the super Catalan numbers C(t) := ∑_{n≥0} C_{n}t^{n},

tC(t)^{2} + (1 − t)C(t) − 1 = 0.

(d) (1, 2, 6, 21, 80, …) versus (1, 2, 2, 1, 0, …, 0, …).

• I = {1, 2}, Z = {(L; 2, 1), (R; 1, 2)} and X has 6 elements.

• It is immediate to see that Z_{3} has only one element and that Z_{n} is empty for n ≥ 4. Hence g(t) = −t + 2t^{2} − 2t^{3} + t^{4}.

• This example and the previous one show that the integer sequence determined by X does not depend only on the number of elements of I and X.

(e) (1, 2, 7, 31, 154, …) versus (1, 2, 1, 1, …, 1, …).

• Let I = {1, 2}, Z = {(L; 1, 1)} and X has 7 elements.

• It is immediate to see that for n ≥ 2, Z_{n} has only one element: the left comb indexed by 1’s. Hence g(t) = \frac{−t+t^{2}+t^{3}}{1+t}.

(f) (1, 3, 17, 121, 965, ⋯) versus (1, 3, 1, 1, …, 1, …), and (1, k, 2k^{2} − 1, 5 3^{k} − 5k + 1 ⋯,?, ⋯) versus (1, k, 1, 1, …, 1, …).

• I = {1, ⋯, k}, Z = {(L; 1, 1)} and X has 2k^{2} − 1 elements.

• It is immediate to see that, for n ≥ 2, Z_{n} has only one element. Hence g(t) = \frac{−t+(k−1)(1+t)t^{2}}{1+t}.

(g) (1, 3, 14, 80, 510, ⋯) versus (1, 3, 4, 5, …, n + 2, …).

• I={1, 2, 3}, Z = {(L; 1, 1), (L; 2, 1), (R; 2, 2), (R; 3, 3)}, X has 14 elements.

• One checks that Z_{n} is made of (n + 1) + 1 elements. Hence g(t) = \frac{t(−1+t+t^{2})}{(1+t)^{2}}.

(h) (1, 4, 23, 156, 1162, ⋯) versus (1, 4, 9, 16, …, (n + 1)^{2}, …).

• I={↖, ↗, ↘, ↙}, in the following we write Rij in place of (R; i, j):

Z = \{ \begin{matrix}R ↖↖ & R ↗↖ & L ↗↗ \\ R ↙↖ & R ↘↖ & L ↘↗ \\ R ↙↙ & L ↘↙ & L ↘↘ \end{matrix} \}

• We have shown in [A-L, Proposition 4.4] that Z_{n} = (n + 1)^{2}, hence g(t) = \frac{t(−1+t)}{(1+t)^{3}}.

• The first sequence has been given a different combinatorial interpretation in terms of connected non-crossing configurations in [F-N].

(i) (1, 9, 113, ⋯) versus (1, 9, 49, …,).

• I is a set of 9 indices denoted \begin{matrix}↖ & ↑ & ↗ \\ ← & ∘ & → \\ ↙ & ↓ & ↘ \end{matrix} and Z is made of the

following 49 elements (indexed by the cells of Δ^{2} × Δ^{2}):

\begin{matrix}R ↖↖ & R ↗↖ & L ↗↗ & R ↗↑ & R ↖↑ & R ↑↖ & R ↑↑ \\ R ↙↖ & R ↘↖ & L ↘↗ & R ↘↑ & R ↙↑ & L ↓↖ & R ↓↑ \\ R ↙↙ & L ↘↙ & L ↘↘ & R ↘↓ & L ↙↓ & L ↓↙ & L ↓↓ \\ R ↙← & R ↘← & L ↘→ & R ↘ ∘ & R ↙ ∘ & L ↓← & R ↓ ∘ \\ R ↖← & R ↗← & L ↗→ & R ↗ ∘ & R ↖ ∘ & L ↑← & R ↑ ∘ \\ R ←↖ & L →↖ & L →↗ & R →↑ & L ←↑ & L∘ ↖ & L∘ ↑ \\ R ←← & R →← & L →→ & R → ∘ & R ← ∘ & L∘ ← & R ∘ ∘ \end{matrix}

• Unfortunately we do not know how to compute the number of elements in Z_{n}. This example is strongly related to dendriform trialgebras [L-R1] and motivated by the ennea-algebras [Le].

Added after the release of the first version: a thorough study of this example has been performed in [B].

3. Koszul complex and the Theorem

Only elementary homological algebra methods are used in the proof. The reader may find them in standard textbooks on homological algebra such as, for instance, [Bbki].

3.1. Koszul complex. Given a planar binary rooted tree y ∈ Y_{n}, one numbers the leaves from left to right by 0, …, n. Accordingly, one numbers the vertices by 1, …, n, the ith vertex being in between the leaves i − 1 and i. So a decoration is a map ϵ from {1, …, n} to I. A vertex of y is said to be a cup if it is directly connected to two leaves (no intermediate node). In the following example z has a cup at vertex 1 and vertex 3:

[figure]

The grafting of two treees y and y′ is the new tree y ∨ y′ obtained from y and y′ by joining the roots to a new vertex and adding a new root.

For instance, the above tree is the grafting [figure] ∨ [figure] .

We define a chain complex K_{∗} = (K_{n}, d)_{n>0} over the field 𝕂 as follows. The space of (n + 1)-chains is

K_{n+1} := ⨁ 𝕂[Z_{n} × X_{i_{0}} × ⋯ × X_{i_{n}}]

where the sum is over all (n + 1)-tuples (i_{0}, ⋯, i_{n}), where i_{j} ≥ 0. The boundary map d : K_{n+1} → K_{n} is of the form d = ∑_{i=1}^{n}(−1)^{i}d_{i}, where d_{i} sends a basis vector to a basis vector or 0 according to the following rule.

Let z ∈ Z_{n} and x_{j} ∈ X_{i_{j}}. If the ith vertex of z is not a cup, then d_{i}(z; x_{0}, …, x_{n}) := 0. If the ith vertex of z is a cup, then

d_{i}(z; x_{0}, …, x_{n}) := (d_{i}(z); x_{0}, …, x_{i−1} ∨_{ϵ(i)} x_{i}, …, x_{n})

where d_{i}(z) is the labelled tree obtained from z by deleting the ith node (replace it by a leaf), and where ∨_{ϵ(i)} means the grafting with ϵ(i) as the decoration of the new node. If it happens that the labelled tree x_{i−1} ∨_{ϵ(i)} x_{i} contains a pattern in Z, then we put d_{i}(z; x_{0}, …, x_{n}) := 0.

3.2. Lemma. d^{2} = 0.

Proof. Let ω = (z; x_{0}, …, x_{n}). It is sufficient to prove that d_{i}d_{j} = d_{j−1}d_{i} for i < j (presimplicial relation). If i < j − 1, then the actions of d_{i} and d_{j} on ω are sufficiently far apart so that they commute (the indexing j − 1 comes from the renumbering). In the case j = i + 1 we will prove that d_{i}d_{i+1}(ω) = 0 = d_{i}d_{i}(ω). We are, locally in z, in one of the following two situations:

[figure: ϵ(i + 1); ϵ(i); ϵ(i); ϵ(i + 1)]

In the first situation d_{i}d_{i}(ω) = 0 because the ith vertex is not a cup. If i + 1 is not a cup, then d_{i}d_{i+1}(ω) = 0 because d_{i+1}(ω) = 0. If i + 1 is a cup, then d_{i}d_{i+1}(ω) = 0 because one of the entries of d_{i}d_{i+1}(ω) is a ∨_{ϵ(i)} (b ∨_{ϵ(i+1)} c) which has a local pattern in Z and so is 0 in X_{l}.

The proof is similar in the second situation. □

The chain complex K_{∗} is called the Koszul complex of X (see Section 4 for an explanation of this terminology).

3.3. Extremal elements. By definition a basis vector ω = (z; x_{0}, …, x_{n}) of K_{n} is an extremal element if there does not exist a basis vector ω′ such that d_{i}(ω′) = ω for some i.

3.4. Proposition. For each extremal element ω with k cups, the basis vectors d_{i_{1}} ⋯ d_{i_{r}}ω span a subcomplex K_{ω} of K which is isomorphic to the augmented chain complex of the standard simplex Δ^{k−1}.

Proof. Let ω = (z; x_{0}, …, x_{n}) be an extremal element. The graded subvector space of K_{∗} spanned by the elements d_{i_{1}} ⋯ d_{i_{r}}ω is stable by d and so forms a subcomplex.

Let us now prove the isomorphism. We claim that d_{i_{1}} ⋯ d_{i_{r}}ω is non-zero if and only if the indices i_{j} are such that the vertices i_{j} are cups. Indeed the “only if” case is immediate. In the other direction: if d_{i_{1}} ⋯ d_{i_{r}}ω ≠ 0, then this would say that there is an l, such that the vertex l is a cup and d_{l}(ω) = (d_{l}(z); …, (a ∨_{u} b) ∨_{v} c, …) with (R; u, v) in Z, or d_{l}(ω) = (d_{l}(z); …, a ∨_{u} (b ∨_{v} c, …) with (L; u, v) in Z. So we could construct ω̂ = (ẑ; …, a, b, c, …) so that d_{l}(ω̂) = ω, and ω would not be extremal.

We construct a bijection between the cells of Δ^{k−1} and the set of nonzero vectors {d_{i_{1}} ⋯ d_{i_{r}}ω} by sending the jth vertex (number j − 1) of Δ^{k−1} to d_{i_{1}} … d̂_{i_{j}} … d_{i_{k}}ω where i_{j} is the jth cup of x. It is immediate to verify that the boundary map in the chain complex of the standard simplex corresponds to the boundary map d by this bijection. Observe that, under this bijection, the big cell of the simplex is mapped to ω and the generator of the augmentation space is mapped to d_{i_{1}} … d_{i_{k}}ω. □

3.5. Proposition. The chain complex K_{∗} is isomorphic to ⨁_{ω} K_{ω} where the sum is taken over all the extremal elements ω.

Proof. Let us show that any basis vector belongs to K_{ω} for some extremal element ω. If ω is extremal, then the Proposition holds. If not, then there exists an element ω_{1} such that d_{i}(ω_{1}) = ω for some i, and so on. The process stops after a finite number of steps because (z; |, …, |) is extremal.

Now it is sufficient to prove that, if a basis vector belongs to K_{ω} and to K_{ω′}, then ω = ω′.

Let ω = (z; x_{0}, …, x_{n}) and ω′ = (z′; x′_{0}, …, x′_{n}). If d_{i}(ω) = d_{j}(ω′) ≠ 0, then i is a cup of z, j is a cup of z′ and d_{i}(z) = d_{j}(z′). If i < j, then there exists ω̄ such that d_{j}(ω̄) = ω, d_{i}(ω̄) = ω′, and therefore ω is not extremal. So we have i = j.

If d_{i}(ω) = d_{i}(ω′) ≠ 0, then it is of the form (z̄; …, a ∨_{ϵ(i)} b, …). But the element (z; …, a, b, …), where z is the labelled tree obtained from z̄ by replacing the ith leaf by a cup and putting ϵ(i) as a decoration, is the only element such that d_{i}(ω) = (z̄; …, a ∨_{ϵ(i)} b, …). Hence ω = ω′.

So we have proved that any basis vector belongs to one and only one subcomplex of the form K_{ω}. □

3.6. Remark. In order to visualize these two proofs it is helpful to think of the element ω = (z; x_{0}, …, x_{n}) as a single graph (with a “horizon”) obtained by gluing the x_{j}’s to the leaves of z. The horizon indicates where to cut to get the x_{j}’s back. The operator d_{j}, where j is the number of a cup, consists in lowering the horizon under the relevant node.

Example with n = 3 and two cups in z:

[figure: x_{i}; horizon; z]

3.7. Corollary. For any choice of X the Koszul complex K_{∗} is acyclic.

Proof. By Propositions 3.5 and 3.4 the homology of the Koszul complex is trivial since the standard simplex is contractible. There is only one exception in dimension 1 since the subcomplex corresponding to the extremal element ω = (|; |) is 𝕂 in dimension 1. So we have H_{n}(K_{∗}) = 0 for n > 1 and H_{1}(K_{∗}) = 𝕂. □

3.8. Proposition. The Poincaré series of the Koszul complex K_{∗} is equal to f(Z, f(X, t)).

Proof. Let us call w = n + i_{0} + ⋯ + i_{n} the weight of an element ω ∈ Z_{n} × X_{i_{0}} × ⋯ × X_{i_{n}}. From the definition of d_{i}(ω) we see that the weight of d_{i}(ω) is also w. Therefore the Koszul complex is the direct sum of subcomplexes K_{∗}^{(w)} made of all the elements of weight w. For a fixed weight w the complex K_{∗}^{(w)} is finite, beginning with 𝕂[Z_{w} × (X_{0})^{w+1}], ending with 𝕂[Z_{0} × X_{w}]. More generally one has K_{n}^{(w)} = ⨁ 𝕂[Z_{n} ×X_{i_{0}} ×⋯×X_{i_{n}}] where the sum is over all the (n+1)- tuples (i_{0}, …, i_{n}) such that n + i_{0} + ⋯ + i_{n} = w.

Let a_{n} := #X_{n} and b_{n} := #Z_{n} so that f(X, t) = ∑_{n≥1}(−1)^{n+1}a_{n}t^{n+1} and f(Z, t) = ∑_{n≥1}(−1)^{n+1}b_{n}t^{n+1}. From the explicit description of K_{n}^{(w)} we check that the Euler-Poincaré characteristic of K_{∗}^{(w)} is precisely the coefficient of (−1)^{w}t^{w+1} in the expansion of

∑_{n≥1}(−1)^{n+1}b_{n}( ∑_{m≥1}(−1)^{m+1}a_{m}t^{m+1})^{n} .

Therefore the Poincaré series ∑_{w≥0}(−1)^{w}χ(K_{∗}^{(w)})t^{w+1} is equal to f(Z, f(X, t)). □

3.9. End of the proof of Theorem 2.2. By Proposition 3.8 it suffices to show that the Poincaré series of K_{∗} is t. The Poincaré series of a complex is the same as the Poincaré series of its homology. Since the homology of K_{∗} is 0, except in weight 0 where it is 𝕂 by Corollary 3.7, the Poincaré series is t. □

4. Operadic interpretation.

4.1. Algebraic operad. The free associative algebra over the vector space V is the tensor algebra T (V) equipped with the concatenation product. If V is generated by the elements x_{1}, …, x_{k}, then T (V) is nothing but the algebra of noncommutative polynomials over the x_{i}’s. Let us consider T as a functor T : Vect → Vect. The inclusion V → T (V) is given by a transformation of functors ι : Id → T and the classical composition of polynomials gives a transformation of functors γ : T ∘ T → T. Observe that the triple (T, γ, ι) is a monoid in the category of endofunctors of Vect.

By definition an algebraic operad is a monoid (P, γ, ι) where P is an endofunctor of Vect, and γ : P∘P → P, ι : Id → P are transformations of functors. Any algebraic operad P defines a notion of algebra as follows. A P-algebra is a vector space A equipped with a map γ_{A} : P(A) → A compatible with γ and ι. For instance, P(V) is a P-algebra. It has the property of being free over V.

In this paper we consider only operads of the form

P(V) := ⨁_{n} P_{n} ⊗ V^{⊗n}.

They are called regular operads. For instance, in the associative example described above we have As_{n} = 𝕂. For more details on operads and on the Koszul duality theory for operads the reader can consult [G-K], [L1], [F].

4.2. Algebraic operads based on labelled trees. Let I be a finite set of indices, X be a subset of Y_{2} × I^{2} and Z its complement. Over the field 𝕂 we define a type of algebras, denoted P, as follows. There is one binary operation ∘_{i} for any i ∈ I and the relations are

(x ∘_{i} y) ∘_{j} z = 0 if (L; i, j) ∈ Z and x ∘_{i} (y ∘_{j} z) = 0 if (R; i, j) ∈ Z.

It is immediate to check that the free algebra of type P on one generator admits X_{n−1} as a basis of the homogeneous part of degree n, n ≥ 1. The generator is the unique element of X_{0}, that is, | . So the operad P determined by this type of algebras is a regular operad such that P_{n} = 𝕂[X_{n−1}].

Reversing the roles of X and Z, that is, taking the elements of X as relations, gives rise to a new regular operad Q such that Q_{n} = 𝕂[Z_{n−1}].

4.3. Lemma. The Koszul dual operad of P is Q, that is, P^{!} = Q.

INVERSION OF INTEGRAL SERIES ENUMERATING PLANAR TREES 11

Proof. Recall from [G-K], (see [L1] or [L2] for a short survey and [F] for details) that the dual operad P^{!} of the regular operad P is constructed as follows. The generating operations are the same. The space of relations is made of the elements ∑ α_{ij}(x ∘_{i} y) ∘_{j} z + ∑ β_{ij}x ∘_{i} (y ∘_{j} z) (for some scalars α_{ij} and β_{ij}) which are orthogonal to the relations of P for the inner product ⟨−, −⟩ defined on the linear generators by

⟨(x ∘_{i} y) ∘_{j} z , (x ∘_{i} y) ∘_{j} z⟩ = 1, (1) ⟨x ∘_{i} (y ∘_{j} z) , x ∘_{i} (y ∘_{j} z)⟩ = −1 (2)

(3) ⟨−, −⟩ = 0 otherwise.

One immediately checks that the vector space generated by X is orthogonal to the vector space generated by Z, and therefore the Koszul dual of P is Q. □

4.4. Theorem. The operads P and Q are Koszul operads.

Proof. The Koszul duality of P is equivalent to the acyclicity of the Koszul complex of P, which is (P^{!∗}(P(V)), δ). Since P is regular, it is sufficient to check the acyclicity for V = 𝕂. Since P^{!} = Q the chains of the Koszul complex of P are the same as the chains of the Koszul complex of X constructed in the first section. A careful checking of the construction of δ shows that δ = d.

So we can apply Corollary 3.7 and the proof is completed. □

4.5. Poincaré series. The Poincaré series of a binary regular operad P is defined as

f^{P}(t) := ∑_{n≥1}(−1)^{n} dim P_{n} t^{n} .

Hence, for the operad P defined by X, one has f^{P}(t) = f(X, t) and the functional equation of Theorem 2.2 is the functional equation

f^{P^{!}}(f^{P}(t)) = t

proved in [G-K] for Koszul binary quadratic operads. A similar formula holds for any Koszul quadratic operad (not necessarily binary), cf. [F], [V2].

In this paper we exploit only the Poincaré series property of Koszul operads. There are many other applications like constructing homotopy algebras (cf. [G-K]) and computing the homology of the associated partition complex (cf. [V3]).

5. Generalization

There is no reason to restrict oneself to binary trees, that is, to binary operads. One can start with planar rooted trees. In this framework we choose a set of indices for each integer k ≥ 2. The functional equation is now in two variables because any operation determines two integers: the number of variables on which it acts and the number of generating operations used to form it (in the binary case the number of variables is equal to the number of generating operations plus one). See [V3, Section 9] for the operadic interpretation. In this section we give some examples of a particular case: the vertices of the trees have valency k + 1 ≥ 2 + 1 for a fixed integer k.

5.1. k-ary planar trees. Let Y_{n}^{(k)} be the set of planar rooted trees with n nodes, each vertex being of valency k + 1. The number of leaves of such a tree is (k − 1)n + 1. The case k = 2 is the one treated in the first part. Let I be a set of indices and let Y_{n}^{(k)}×I^{n} be the set of labelled trees. Choose a subset X of Y_{2}^{(k)} × I^{2} and let Z be its complement. As before we define X_{n} ⊂ Y_{n}^{(k)} × I^{n} to be the subset made of labelled trees whose local patterns belong to X.

In order to state the Theorem we need to introduce the following series. Let \underline{a} = (a_{0}, …, a_{n}, …) be a sequence of numbers (we will always have a_{0} = 1). Define the (lacunary) series f^{(k)} and g^{(k)} as follows:

f^{(k)}(\underline{a}, t) := ∑_{n≥0}(−1)^{n+1}a_{n}t^{(k−1)n+1} = −t + a_{1}t^{k} − a_{2}t^{2k−1} + ⋯

g^{(k)}(\underline{a}, t) := − ∑_{n≥0}(−1)^{(k+1)n}a_{n}t^{(k−1)n+1} = −t+(−1)^{k}a_{1}t^{k}−a_{2}t^{2k−1}+⋯

Observe that when k is even f^{(k)} = g^{(k)} and when k is odd all the signs in g^{(k)} are − . When k = 2, one has f^{(2)} = g^{(2)} = f as defined in Section 2. The series f^{(k)}(X, t) and g^{(k)}(X, t) are obtained by taking a_{n} = #X_{n}.

5.2. Theorem. Let X be a subset of Y_{2}^{(k)} × I^{2} and let Z be its complement, i.e., X ⊔ Z = Y_{2}^{(k)} × I^{2}. Then the following functional equation holds:

g^{(k)}(Z, f^{(k)}(X, t)) = t.

The proof is along the same lines as the proof of Theorem 2.2 and we leave it to the diligent reader to work it out.

There is an operadic interpretation of this result, which involves the notion of k-ary algebras. The relevant generalization of Koszul duality theory for quadratic algebras (not just binary) can be found in [F].

It would be interesting to study the analogous question with operads replaced by props as in [V1], [V2].

5.3. Examples. The integer sequences involved in this case are of the form

(1, \underbrace{0, …, 0}_{k−2}, a_{1}, \underbrace{0, …, 0}_{k−2}, a_{2}, \underbrace{0, …, 0}_{k−2}, a_{3}, 0, …,)

with a_{1} = #I, a_{2} = #X, so 0 ≤ a_{2} ≤ k(a_{1})^{2}. We denote such a lacunary sequence by (1; a_{1}; a_{2}; ⋯; a_{n}; ⋯)_{k} .

(a) (1; 1; k; \frac{k(3k−1)}{2}; \frac{k(8k^{2}−6k+1)}{3}; ⋯)_{k} versus (1; 1; 0; ⋯; 0; ⋯)_{k} . Let c_{n}^{(k)} be the number of k-ary trees with n nodes. Taking I = {1},

X = Y_{2}^{(k)} and Z = ∅ we get g^{(k)}(∅, t) = −t+(−1)^{k}t^{k} and f^{(k)}(Y_{2}^{(k)}, t) = ∑_{n≥0}(−1)^{n+1}c_{n}^{(k)}t^{(k−1)n+1}. So this last series, denote it y, satisfies the functional equation −y + (−1)^{k}y^{k} = t.

(b) (1; 1; 2; 5; ⋯; c_{n}; ⋯)_{3} versus (1; 1; 1; ⋯; 1; ⋯)_{3} .

Take I = 1, X has two elements and Z has one element. The set X_{n} has c_{n+1} elements and Z_{n} has one element. This case is related to the notion of totally associative ternary algebras and partially associative ternary algebras studied in [Gn].

(c) (1; 1; 2; 5; ⋯; c_{n}; ⋯)_{4} versus itself.

Let k = 4, I = {1}. The set X is made of two elements of Y_{2}^{(4)} and Z is made of the other two. It is clear that the sets X_{n} and Z_{n} are in bijection with the planar binary trees of degree n. As a consequence of Theorem 5.2 the series h(t) = ∑_{n≥0}(−1)^{n+1}c_{n}t^{3n+1} satisfies

h(h(t)) = t.

Of course this result can also be proved by direct computation from the expression c(t) := ∑_{n≥0} c_{n}t^{n} = \frac{1−\sqrt{1−4t}}{2t}.

6. Inversion of the generic formal power series

Let f(t) = t + a_{1}t^{2} + ⋯ + a_{n}t^{n+1} + ⋯ be the generic formal power series and let g(t) = t+b_{1}t^{2}+⋯+b_{n}t^{n+1}+⋯ be its inverse with respect to composition. The coefficient b_{n} is a polynomial in the coefficients a_{1}, …, a_{n}. Explicitly we get

\begin{aligned}b_{1} & = & −a_{1}, \\ b_{2} & = & 2a_{1}^{2} − a_{2}, \\ b_{3} & = & −5a_{1}^{3} + 5a_{1}a_{2} − a_{3}, \\ b_{4} & = & 14a_{1}^{4} − 21a_{1}^{2}a_{2} + 6a_{1}a_{3} + 3a_{2}^{2} − a_{4}, \end{aligned}

and more generally

b_{n} = ∑_{i_{1}+2i_{2}+···+ni_{n}}(−1)^{i_{1}+i_{2}+···+i_{n}}c_{i_{1}···i_{n}}a_{1}^{i_{1}}a_{2}^{i_{2}} … a_{n}^{i_{n}} ,

where the coefficient c_{i_{1}···i_{n}} is the number of planar rooted trees having i_{k} vertices with valency (k + 1) + 1 (cf. [St]). Observe that it is also the number of cells of the (n − 1)-dimensional associahedron K^{n−1} of the form (K^{0})^{i_{1}} × ⋯ × (K^{n−1})^{i_{n}}.

This result can be proved purely combinatorially, however it has a simple proof in the spirit of this paper, i.e., via Koszul operads. It gives a conceptual explanation for the appearance of the numbers of planar rooted trees of a certain form.

First, we oberve that it is sufficient to prove this result when the coefficients a_{n} are integers, since we know a priori that b_{n} is a polynomial in the a_{i}’s. Second, consider the algebras defined by a_{n} (n+1)-ary operations (with no symmetry) and with relations: any nontrivial composite is 0. It is clear that the (regular) operad P associated to these algebras is such that P_{n} = a_{n}𝕂 since there are no operations but the generating ones. Since the operad P is nilpotent by construction, its dual P^{!} is the free operad over the same generators. Therefore a linear generator of P_{n}^{!} is determined by a planar rooted tree whose vertices are labelled by the generators of the P_{k}’s :

[figure: μ_{1}; μ_{3}; μ_{2}]

where μ_{1} ∈ P_{2}, μ_{2} ∈ P_{4}, μ_{3} ∈ P_{3}.

It follows from this description that

dim P_{n}^{!} = ∑_{i_{1}+2i_{2}+···+ni_{n}} c_{i_{1}···i_{n}}a_{1}^{i_{1}} … a_{n}^{i_{n}} .

Since the operad P^{!} is quadratic and free, it is a Koszul operad, that is, the Koszul complex is acyclic (cf. Fresse [F]). Computing the Euler-Poincaré characteristic of this complex gives a formula entertwining the generating series of P and of P^{!}. For a general Koszul quadratic operad this has been unraveled explicitly by B. Vallette in [V2, Section 9]. In the particular case at hand it takes precisely the form g(f(t)) = t.

Special thanks to Mamuka Jibladze for discussions on the topic of this section.

References

[A-L] M. Aguiar and J.-L. Loday, Quadri-algebras, J. Pure Appl. Alg. 191 (2004),

no. 3, 205–221.

[B] R. Bacher, On generating series of complementary planar trees, Séminaire Lotharingien Combin. 53, to appear; arXiv:math.CO/0409050.

[Bbki] N. Bourbaki, Éléments de mathématique. Algèbre. Chapitre 10. Algèbre homologique. Masson, Paris, 1980. vii+216 pp.

[F-N] P. Flajolet, M. Noy, Analytic combinatorics of non-crossing configurations,

Discrete Math. 204 (1999), no. 1-3, 203–229.

[F] B. Fresse, Koszul duality of operads and homology of partition posets, Homotopy theory: relations with algebraic geometry, group cohomology, and algebraic K-theory, 115–215, Contemp. Math., 346, Amer. Math. Soc., Providence, RI, 2004.

[G-K] V. Ginzburg, M.M. Kapranov, Koszul duality for operads, Duke Math. J. 76

(1995), 203-272.

[Gn] A.V. Gnedbaye, Opérades des algèbres (k + 1)-aires. Operads: Proceedings of Renaissance Conferences (Hartford, CT/Luminy, 1995), 83–113, Contemp. Math., 202, Amer. Math. Soc., Providence, RI, 1997.

[Le] Ph. Leroux, Ennea-algebras, J. Algebra 281 (2004), no. 1, 287–302.

[L1] J.-L. Loday, La renaissance des opérades, Séminaire Bourbaki, Vol. 1994/95. Astérisque No. 237 (1996), Exp. No. 792, 3, 47–74.

[L2] J.-L. Loday, Dialgebras, in: “Dialgebras and related operads”, Springer Lect. Notes in Math. 1763, (2001), 7–66.

[L3] J.-L. Loday, Scindement d’associativité et algèbres de Hopf, Proceedings of the Conference in honor of Jean Leray, Nantes 2002, Séminaire et Congrès (SMF) 9 (2004), 155–172.

[L-R1] J.-L. Loday, M. Ronco, Trialgebras and families of polytopes, Homotopy theory: relations with algebraic geometry, group cohomology, and algebraic K-theory, 369–398, Contemp. Math., 346, Amer. Math. Soc., Providence, RI, 2004.

[L-R2] J.-L. Loday, M. Ronco, On the structure of cofree Hopf algebras, J. reine

angew. Math. (2005), to appear.

[Sl] N.J.A. Sloane, An online version of the encyclopedia of integer sequences,

http://akpublic.att.com/∼njas/sequances/ol.thm

[St] R.P. Stanley, Enumerative combinatorics. Vol. 1. Cambridge Studies in Advanced Mathematics, 49. Cambridge University Press, Cambridge, 1997.

[V1] B. Vallette, Koszul duality for PROPs, C.R.Acad.Sci Paris 338 (2004), 909– 914.

[V2] B. Vallette, A Koszul duality for props, to appear in Trans. Amer. Math. Soc.

[V3] B. Vallette, Homology of generalized partition posets, to appear in J. Pure Appl. Alg.

Institut de Recherche Mathématique Avancée, CNRS et Université Louis Pasteur, 7 rue R. Descartes, 67084 Strasbourg Cedex, France

E-mail address: loday@math.u-strasbg.fr
URL: www-irma.u-strasbg.fr/∼loday/