Séminaire Lotharingien de Combinatoire 63 (2010), Article B63h

THE PRODUCT OF TREES IN THE LODAY–RONCO ALGEBRA THROUGH CATALAN ALTERNATIVE TABLEAUX

J.-C. AVAL, X. VIENNOT

Abstract. The aim of this note is to show how the introduction of certain tableaux, called Catalan alternative tableaux, provides a very simple and elegant description of the product in the Hopf algebra of binary trees defined by Loday and Ronco. Moreover, we use this description to introduce a new associative product on the space of binary trees.

1. Introduction

J.-L. Loday and M. Ronco defined in [5] an interesting Hopf algebra structure on the linear span of rooted planar binary trees. This algebra is defined as a sub-algebra of the Malvenuto–Reutenauer Hopf algebra of permutations. Let S_{n} be the symmetric group and k be a ground field. We denote by k[S_{n}] the group algebra. C. Malvenuto and C. Reutenauer construct in [6] a Hopf algebra structure on

k[S_{∞}] = ⨁_{n≥0} k[S_{n}].

It is worth to recall here that the Malvenuto–Reutenauer algebra contains the sum of Solomon descent algebras Sol_{∞} = ⨁_{n≥0} Sol_{n}, with Sol_{n} of dimension 2^{n−1}.

In [5], Loday and Ronco define a sub-Hopf algebra of k[S_{∞}]:

k[Y_{∞}] = ⨁_{n≥0} k[Y_{n}],

where Y_{n} is the set of planar binary trees with n internal vertices.

The aim of this work is to present a very simple presentation for the product of two trees in k[Y_{∞}] through the use of Catalan alternative tableaux. These objects were introduced by X. Viennot [12] as a special case of alternative tableaux, which are in bijection with permutation tableaux. Permutation tableaux were introduced by E. Steingrímsson and L. Williams [9], as a subclass of Γ -diagram defined by A. Postnikov [8]. This notion was used by S. Corteel and L. Williams [2, 3] in the study of the physical model named PASEP (partially asymmetric exclusion process), see for example the seminal paper by B. Derrida et al. [4]. These tableaux are also related to the study of total positivity for Grassmannian [13]. Both permutation and alternative tableaux are in bijection with permutations, see for example P. Nadeau’s article [7]. The advantage of alternative tableaux is that they possess symmetry between rows and columns.

This research has been supported by the ANR (project MARS/06-BLAN-0193).

This new interpretation of the Loday–Ronco product motivates the introduction of a new associative product, that we call the # product, on the space of binary trees. This new product is studied in [1] by F. Chapoton.

The present article is organized as follows: in Section 2 we recall the definition of the Loday–Ronco algebra, then, in Section 3, we introduce the Catalan alternative tableaux and prove that they are in bijection with binary trees; we state and prove the main result of this work in Section 4, and we introduce the new # product in Section 5.

2. The Loday–Ronco Hopf algebra

We recall the definition of the Loday–Ronco product of binary trees. Since this product is inherited from the Malvenuto–Reutenauer product of permutations, we shall first recall the definition of the product in k[S_{∞}], denoted by ∗. We refer to [6] for more details and only recall briefly the definition.

Let u = u_{1} u_{2} …, u_{k} be a k-tuple of distinct integers. We define the standardization of u — and denote it by Std(u) — as the unique permutation σ ∈ S_{k} that preserves the relative order of the u_{i}’s, i.e.,

σ_{i} < σ_{j} if and only if u_{i} < u_{j}.

For example, Std(3275) = 2143. Conversely, for σ ∈ S_{k} a permutation and A = {a_{1}, a_{2}, …, a_{k}} a set of k (distinct) integers, we define σ_{|A} to be the k-tuple with distinct entries in A such that Std(σ_{|A}) = σ. With this notation we may define the product ∗ in k[S_{∞}] as follows. Let σ ∈ S_{k} and τ ∈ S_{l}. We set

σ ∗ τ = ∑_{A⊔B={1,2,...,k+l}} σ_{|A} . τ_{|B},

where ⊔ denotes the disjoint union, and . stands for concatenation.

For example,

12 ∗ 213 = 12 435 + 13 425 + 14 325 + 15 324 + 23 415 + 24 315+ 25 314 + 34 215 + 35 214 + 45 213.

Remark 1. The product ∗ that we consider is sometimes known as the product in the dual Malvenuto–Reutenauer algebra. But it is the one used in [5] to define the Loday–Ronco algebra, that we shall now describe.

Let Y_{n} denote the set of binary trees with n internal vertices. We recall that the cardinality of Y_{n} is given by the n-th Catalan number C_{n} = \frac{1}{n+1} \binom{2n}{n}.

Let Ỹ_{n} denote the set of increasing binary trees, i.e., of binary trees such that each internal vertex has a distinct label in {1, 2, …, n}, and such that the labels increase along the tree.

It is well known that increasing binary trees are in bijection with permutations: to obtain the permutation from the tree, you just have to read the labels from left to right.

Below is an example of a plane binary tree with 8 internal vertices, with an increasing binary tree with the same underlying tree, and with the corresponding permutation σ ∈ S_{n}.

We denote by Ψ : S_{n} → Y_{n} the composition of the bijection S_{n} ≃ Ỹ_{n} with the projection Ỹ_{n} → Y_{n} which consists in forgetting the labels. The induced linear map Ψ : k[S_{n}] → k[Y_{n}] has a linear dual Ψ^{∗} : k[Y_{n}] → k[S_{n}] obtained by identifying each basis with its own dual. For example,

Ψ^{∗}( ) = 3412 + 2413 + 2314.

We also define for any tree T the set

Z_{T} = {σ ∈ S_{n} / Ψ(σ) = T },

so that Ψ^{∗}(T) = ∑_{σ∈Z_{T}} σ.

The inclusion map Ψ^{∗} gives rise to a graded linear map Ψ^{∗} : k[Y_{∞}] → k[S_{∞}]. The main result in the construction of the Loday–Ronco algebra may now be stated as follows (see [5, Theorem 3.1]).

Theorem 2. The image of the inclusion map Ψ^{∗} : k[Y_{∞}] → k[S_{∞}] is a sub-Hopf algebra of k[S_{∞}]. So, k[Y_{∞}] inherits the structure of a Hopf algebra.

3. Trees and Catalan alternative tableaux

We now present the Catalan alternative tableaux. Let us denote by ℕ the set of nonnegative integers. A Catalan alternative tableau in given by:

• a path in ℕ×ℕ from {0}×ℕ to ℕ×{0} made of (1, 0) and (0, −1) steps. The length of the path is called the size of the tableau, and the cells below the path are simply called the cells of the tableau. The path defining the tableau is also called the shape of the tableau.

• a set of blue and red dots in the cells of the tableau such that:

(1) there is no dot below a red dot;

(2) there is no dot on the left of a blue dot;

(3) any cell of the tableau is either below a red dot, or on the left of a blue

dot.

Let us give an example of a Catalan alternative tableau of size 23. Note that red and blue dots appear respectively as light grey and dark grey dots on black and white printers.

It is possible to directly check that Catalan alternative tableaux are enumerated by Catalan numbers (whence their name), but we shall use the following proposition, more adapted to our context.

Proposition 1. The Catalan alternative tableaux of size n − 1 are in bijection with binary trees with n internal nodes.

Proof. We refer to [10] (Algorithm 2.2) for a formal proof and give here only the idea of the construction. In fact, in that paper, the algorithm was given in term of “Catalan permutation tableaux,” the subclass of permutation tableaux corresponding to Catalan alternative tableaux, and discussed in [9].

We start with a Catalan alternative tableau of size n − 1 and rotate it:

The thick line represents the tree under construction. Recursively, for any “Up-Down” pattern

in the thick line, we apply the operation of a shift, where two cases are to be distinguished:

• if the corresponding corner in the tableau is blue:

and we erase the row of the corner in the tableau;

• if the corresponding corner in the tableau is red:

and we erase the column of the corner in the tableau.

For our example, we obtain:

It is not difficult to verify that this construction is a bijection. □

For a permutation σ ∈ S_{n}, its Up-Down sequence (cf. [11]) is the vector Q(σ) = (q_{1}, …, q_{n−1}) ∈ {−1, +1}^{n−1} such that

q_{i} = +1 if and only if σ_{i+1} > σ_{i}.

It is clear that for any tree T, all the σ in Z_{T} have the same Up-Down sequence, which we may call the Up-Down sequence of T, also called canopy of the binary tree T in [11].

Now we may view the shape of a Catalan alternative tableau of size n − 1 as a vector in {−1, +1}^{n−1} (horizontal steps correspond to “−1” entries and vertical steps to +1 entries).

We have the following property.

Proposition 2. The shape of the tableau associated to a tree T through the bijection described in Proposition 1 is the Up-Down sequence of T, as well as the common Up-Down sequence of any permutation σ in Z_{T}.

Now the algorithm described above may be extended to labelled trees: we may put n labels along the shape of a Catalan alternative tableau of size n − 1:

If we keep the labels of the nodes when we apply the algorithm to get a tree from the tableau, we obtain a labelled tree

In the previous example, we may say that the tableau was labelled with the permutation 792531648. As a consequence of the bijection, we get the following property.

Proposition 3. Let σ be a permutation of size n. We may label a tableau C with σ, then apply the bijective algorithm. The labelled tree that we obtain is increasing if and only if:

• the shape of C is the Up-Down sequence of σ;

• the position of the red and blue dots in C is the only one which gives the binary tree Ψ(σ).

4. The product of trees through Catalan alternative tableaux

Now we come to the main result of this work.

Theorem 3. Let T_{1} and T_{2} be two binary trees. Their product in the Loday–Ronco algebra

T_{1} ∗ T_{2} = ∑ T

is given by taking the sum over the trees T associated to Catalan alternative tableaux in the union

where C_{1} and C_{2} are the Catalan alternative tableaux associated respectively to T_{1} and T_{2}, and the question marks ? represent any (valid) placement of (red and blue) dots in the rectangles.

Proof. By definition of Ψ^{∗}, we have

(1)  Ψ^{∗}(T_{1} ∗ T_{2}) = Ψ^{∗}(T_{1}) ∗ Ψ^{∗}(T_{2}) = ∑_{σ_{1}∈Z_{T_{1}}} σ_{1} ∗ ∑_{σ_{2}∈Z_{T_{2}}} σ_{2} = ∑_{σ∈S} σ.

Let σ be an element of S. By definition of the product ∗ in the Malvenuto– Reutenauer algebra, σ is of the form σ = τ_{1}.τ_{2} (concatenation), with the letters appearing in τ_{1} and τ_{2} forming a partition of {1, …, n}, and

(2)  Ψ(τ_{1}) = T_{1} and Ψ(τ_{2}) = T_{2}.

Thus if Ψ(σ) = T, the Up-Down sequence of T, Q(T), is either Q(T_{1}) Up Q(T_{2}) or Q(T_{1}) Down Q(T_{2}). Hence the form of the Catalan alternative tableau C associated to T is one of the two given in Theorem 3. We label the shape of C with the entries of σ. The red and blue dots in C have to be placed in a position such that, by applying the bijective algorithm, we obtain an increasing binary tree. But if we apply the algorithm to the part of C that carries the entries of τ_{1} (respectively τ_{2}), Propositions 1 and 3 imply that the (red and blue) dots of C in the corresponding subparts of C have to be placed in the same configuration than in C_{1} (respectively C_{2}). This implies that C has the required form.

Conversely, let T be a tableau of the form described in Theorem 3, and σ ∈ Z_{T}. By cutting σ in two parts u_{1} and u_{2} of lengths the sizes of C_{1} and C_{2}, we may write: σ = u_{1}.u_{2} with Std(u_{1}) = τ_{1} and Std(u_{2}) = τ_{2}.

It is again a simple application of Propositions 1 and 3 that we have: Ψ(τ_{1}) = T_{1} and Ψ(τ_{2}) = T_{2}, which was to be proved to complete the proof of Theorem 3. □

5. The # product of binary trees

In view of Theorem 3, it seems natural to introduce a new product on k[Y_{∞}] as follows.

Definition 4. We define the # product of two binary trees T_{1} and T_{2}, associated respectively to Catalan alternative tableaux C_{1} and C_{2}, by

T_{1} # T_{2} = ∑ T,

where the sum is taken over the trees T associated to Catalan alternative tableaux in the set:

Here, the question mark ? represents any (valid) placement of (red and blue) dots in the corresponding rectangle.

It is clear that this defines an associative product on k[Y_{∞}]. It is worth to note that for T_{1} ∈ Y_{k} and T_{2} ∈ Y_{l} the product T_{1} # T_{2} is in Y_{k+l−1}. (In this case the number of internal edges is preserved.)

We give below an example of this product, which should be checked by the reader.

#  =  +  +

Acknowledgement. The authors sincerely thank F. Chapoton for fruitful discussions.

References

[1] F. Chapoton, Some dendriform functors, preprint; arχiv:0909.2751.

[2] S. Corteel, L. Williams, Tableaux combinatorics for the asymmetric exclusion process, Adv. in Appl. Math. 39 (2007), 293–310.

[3] S. Corteel, L. Williams, Tableaux combinatorics for the asymmetric exclusion process and Askey–Wilson polynomials, preprint; arχiv:0910.1858.

[4] B. Derrida, M. Evans, V. Hakim, V. Pasquier, Exact solution of a 1D asymmetric exclusion model using a matrix formulation, J. Phys. A: Math. Gen. 26 (1993), 1493–1517.

[5] J.-L. Loday, M. Ronco, Hopf algebra of the planar binary trees, Adv. in Math. 139 (1998), 293–309.

[6] C. Malvenuto, C. Reutenauer, Duality between quasi-symmetric functions and the Solomon descent algebra, J. Algebra 177 No. 3 (1995), 967–982.

[7] P. Nadeau, The structure of alternative tableaux, preprint; arχiv:0908.4050.

[8] A. Postnikov, Total positivity, Grassmannians, and networks, preprint;

arχiv:math/0609764.

[9] E. Steingrímsson, L. Williams, Permutation tableaux and permutation patterns, J. of Combin. Theory Ser. A 114 (2) (2007), 211–234.

[10] X. Viennot, Catalan tableaux and the asymmetric exclusion process, Proceedings of FPSAC’07, Tianjin, China; arχiv:0905.3081.

[11] X. Viennot, Up-down sequences of permutations, paths and canopy of binary trees, invited talk at the Lascouxfest, 52th SLC, Ottrott, March 2004.

[12] X. Viennot, Alternative tableaux, permutations and partially asymmetric exclusion process, , Isaac Newton institute, April 2007, video and slides from a talk at the workshop ”Statistical-Mechanics and Quantum-Field Theory Methods in Combinatorial Enumeration”,

http://www.newton.ac.uk/webseminars/pg+ws/2008/csm/csmw04/0423/viennot/

[13] L. Williams, Enumeration of totally positive Grassmann cells, Adv. in Math. 190 (2005), 319–342.

(Jean-Christophe Aval) LaBRI, Université Bordeaux 1, 351 cours de la Libération, 33405 Talence cedex, FRANCE

E-mail address: aval@labri.fr

URL: http://www.labri.fr/perso/aval

(Xavier Viennot) LaBRI, Université Bordeaux 1, 351 cours de la Libération, 33405 Talence cedex, FRANCE

E-mail address: viennot@labri.fr
URL: http://www.labri.fr/perso/viennot