Simplicial Properties of the Set of Planar Binary Trees.
Planar binary trees appear as the the main ingredient of a new homology theory related to dialgebras, cf.(J.-L. Loday, i>C.R. Acad. Sci. Paris 321 (1995), 141146.) Here I investigate the simplicial properties of the set of these trees, which are independent of the dialgebra context though they are reflected in the dialgebra homology.The set of planar binary trees is endowed with a natural (almost) simplicial structure which gives rise to a chain complex. The main new idea consists in decomposing the set of trees into classes, by exploiting the orientation of their leaves. (This trick has subsequently found an application in quantum electrodynamics, c.f. (C. Brouder, On the Trees of Quantum Fields, Eur. Phys. J. C12, 535549 (2000).) This decomposition yields a chain bicomplex whose total chain complex is that of binary trees. The main theorem of the paper concerns a further decomposition of this bicomplex. Each vertical complex is the direct sum of subcomplexes which are in bijection with the planar binary trees. This decomposition is used in the computation of dialgebra homology as a derived functor, cf. (A. Frabetti, Dialgebra (co) Homology with Coefficients, Springer L.N.M., to appear).
Introduction
The planar binary trees have been widely studied for their combinatorial properties, which relate
them to permutations, partition of closed strings and other finite sets. In fact, the cardinality
of the set Y n of planar binary trees with leaves and one root is the Catalan number
n!(n+1)! , which is well known to have many combinatorial interpretations [G].
In 1994, in the paper [L] written by J.-L. Loday, these trees appear as the main ingredient in
the homology of a new kind of algebras, called dialgebras , equipped with two binary associative
operations. Instead of the single copy
A\Omega n , which forms the module of Hochschild n-chains of
an associative algebra A, Loday finds out that the module of n-chains of a dialgebra D contains
c n copies of
D\Omega n . The crucial observation is that labelling each copy of
D\Omega n by an n-tree leads
to a very natural and simple definition of the face maps: the i-th face of an n-tree is obtained
by deleting its i-th leaf. Hence the set of rooted planar binary trees acquires an important
role in the simplicial context of dialgebra homology. The study of this homology leads to the
investigation of the simplicial structure of the set of trees, which is completely independent of
the dialgebra context and constitutes the content of this paper.
The set of trees can be equipped with degeneracy operators s j which satisfy all the simplicial
relations except that s i s . For such a set, which is called almost-simplicial , some of the
properties of simplicial sets still hold, for instance the Eilenberg-Zilber Theorem, c.f. [I].
Our main idea consists in decomposing the set of trees into classes, by exploiting the orientation
of their leaves. This trick is purely combinatorial (set-theoretical), and it is explained in
section 1. In section 2 we show that this decomposition is compatible with the almost-simplicial
strucure and yields a chain bicomplex whose total chain complex is that of binary trees. Conse-
quently, in the application, we obtain a canonical spectral sequence converging to the dialgebra
homology.
Our main theorem concerns a further decomposition of this bicomplex. We show that each
vertical complex is in fact the direct sum of subcomplexes, that we call towers . It turns out that
these towers are in bijection with the planar binary trees. The vertical complex in degree p is
the some of the towers indexed by the planar binary trees of order p. Again, this decomposition
is purely combinatorial. An illustrative picture of the situation is placed at the beginning of
section 3, where we define the vertical towers, by means of a new kind of degeneracy operators,
and prove the decomposition theorem (3.11).
The main application of this decomposition is the interpretation of dialgebra homology as a
Tor functor given in [F2].
1 Classes of planar binary trees
In this section we introduce some classes of planar binary trees and compute their cardinality.
1.1 - Planar binary trees. By a planar binary tree we mean an open planar graph with 3-fold
internal vertices. Among the external vertices we fix a preferred one and call it root . Usually
we draw the root at the bottom of the tree. The remaining external vertices, called leaves , are
drawn at the top of the tree:
leaves
root
For any natural number n, let Y n be the set of planar binary trees with
we label as 0; 1; :::; n from left to right. Given a tree y with leaves, we call order of y
the natural number jyj := n. Notice that the order of a tree is the number of internal vertices.
Therefore, for we consider the unique tree with one leaf, the root and no internal vertices.
Here is a picture of the sets Y n for 3:
The cardinality of the set Y n is given by the Catalan number (see [K], [A], [B] and [G])
Hence the sets Y 0 , Y 1 , Y 2 , . have cardinality 1, 1, 2, 5, 14, 42, 132 and so on.
In the sequel we abbreviate "planar binary tree" into "tree".
1.2 - Classes of trees. For any couple of natural numbers p; q, let Y p;q be the set of (p+q+1)-
trees with p leaves oriented like n (excluded the 0-th leaf), and q leaves oriented like = (excluded
the last one). The class of an n-tree is specified by the component Y p;q ae Y n , with
to which the tree belongs. For example:
For any p; q - 0, the set Y p;0 (resp. Y 0;q ) contains only one tree (resp. ), called comb.
The sets Y p;q are obviously disjoint, for different couples (p; q), and their disjoint union covers
the set Y p+q+1 . Hence we have
G
p+q+1=n
For example, Notice that the number of
classes in the set Y n is precisely ng.
1.3 - Proposition. Let c p;q be the cardinality of the set Y p;q . Then
p! q!
c p;q02q

Figure

1: The cardinality of the classes of rooted planar binary trees.
Lemma. The cardinality c p;q of the set Y p;q is c
finally, for any p; q - 1, it satisfies the relation
Proof. When there exists only one (0; 0)-tree, namely . Thus c 0;0 = 1. Similarly,
there exists only one (p; 0)-tree, namely the comb tree . The same for
When q)-tree y can have one of the following three shapes:
Thus, for any p; q - 1, c p;q is the sum of the cardinality of these three disjoint sets. 2
Proof of (1.3). We have to count the number c p;q of (p; q)-trees, for Consider the values
c p;q as coefficients of Taylor's expansion of a function of two variables x and y, around the point
(0; 0), and put
It is straightforward to show that the relations of lemma (1.4) lead us to the quadratic equation
in the indeterminate f(x; y). The solution of this equation
is the function f(x;
. By direct computations, choosing
the sign "\Gamma" before the root, we obtain the values
In fact
where g n;0 (x; y) is a polynomial with g n;0 (0;
2 is such
that \Delta(0;
@y m . Therefore the function f(x; y) has itself Taylor's
expansion
@ n+m f(0;
and the coefficients c p;q satisfy
@ n+m f(0;
Again by direct computation we obtain
@ n+m f(x; y)
where g n;m (0; Hence we get the final formula
@x p+1 @y q+1
Remark. The Catalan number c n can be given in terms of binomial coefficients, c n =n+1
. Hence the discrete convolution formula for binomial coefficients, namely
!/
evaluated at exactly the identity
!/
p! q!
Simplicial structure on the set of binary trees
In this section we recall the existence of an almost-simplicial structure on the family of planar
binary trees which was previously introduced in [L] and [F1], and show that it gives rise to an
acyclic complex.
The faces and degeneracies are compatible with the decomposition of the set Y n into the
classes Y p;q . As a result, there exists a chain bicomplex whose total chain complex is that of
planar binary trees. An important application, given in [F2], concerns the dialgebra homology
defined in [L]: the bicomplex of trees induces a non trivial spectral sequence converging to the
dialgebra homology.
Faces and degeneracies
2.1 - Pseudo and almost-simplicial sets. We recall that a pre-simplicial set E is a collection
of sets E n , one for each n - 0, equipped with face maps d
satisfying the relations
(d) d i d
Given a field k, we consider the k-linear span k[E n ] of the elements of the set E n . The faces give
rise to the boundary operator
Therefore any pre-simplicial set fE n ; d i g always gives rise to a chain complex (k[E   ]; d).
We also recall that a simplicial set is equipped with degeneracy maps
any the relations
By definition, a pseudo-simplicial set is a family of sets endowed with faces and degeneracies
satisfying relations (d) and (ds) but not necessarily relations (s) (see [T-V] and [I]).
We call almost-simplicial a pseudo-simplicial set whose degeneracies satisfy relations
except for which means that s i s in general (but not necessarily)
all simplicial or almost-simplicial sets are pseudo-simplicial,
fsimplicial setsg ae falmost-simplicial setsg ae fpseudo-simplicial setsg ae fpre-simplicial setsg:
Let us consider now the set of binary trees described in section 1. Trees can be obtained one
from another by repeating two basic operations: deleting and adding leaves. The operation of
deleting leaves allows us to define face maps Y n \Gamma! Y n\Gamma1 and thus to consider the associated
chain complex k[Y   ] for any given field k. The operation of adding leaves allows us to define
degeneracy maps Y n \Gamma! Y n+1 .
2.2 - Face maps on trees. For any n - 0, and any th face the map
which associates to an n-tree y the (n \Gamma 1)-tree d i (y) obtained by deleting the i th leaf from y.
For example:
2.3 - Lemma. The face maps d i satisfy the above relations (d). Hence, given a field k, the
sequence
is a chain complex, with boundary operator
Proof. In fact, since the leaf number j of the tree y is the leaf number of the tree d i (y), the
maps d i d j and d j \Gamma1 d i produce the same modification: they delete the leaves number i and j. 2
2.4 - Degeneracies on trees. For any n - 0, and any th degeneracy the
which bifurcates the j th leaf of an n-tree, i.e. which replaces the j th leaf by the branch . For
example:
2.5 - Lemma. The degeneracy maps satisfy the above relations (ds). They also satisfy (s) for
hence the module of binary trees fk[Y n ]; d is almost-simplicial.
Proof. (ds) The operations d i s j on a tree y first adds a leaf replacing the leaf number j by the
branch , and then deletes the leaf number i. So, when i ! j, it is clear that we obtain the
same tree if we first delete the i th leaf and then bifurcate the original j th leaf, which is now
labeled by j \Gamma 1.
1, the operator d i evidently brings the tree s j (y) (with branch labeled by
back to the original tree.
Finally, when i 1, we can invert the operations after having observed that the leaf number
i of the tree s j (y) is the leaf number in the tree y.
The operation s i s j on a tree y first bifurcates the leaf number j and then bifurcates
the leaf number i. So it is clear that if i ! j the same tree can be obtained performing the
two bifurcations in incerted order, observing that the j th leaf of y is the leaf number
(Notice that for replace the i th leaf with the branch , while the
operator produces the branch , hence they do not coincide.) 2
2.6 - Theorem. For any field k, the chain complex of binary trees is acyclic, that is
ae k; for
Proof. It is straightforward to check that the map
is an extra-degeneracy (i.e.
satisfies relations (s)) for the almost-simplicial set of binary trees. It follows that dh
hence the induced map h : k[Y n] \Gamma! k[Y n\Gamma1 ] is a homotopy between the maps id and 0. 2
Bicomplex of trees
The orientation of the leaves of an n-tree, given by the numbers p and q of n- and =-leaves,
permits us to define a double complex of binary trees, by considering maps which do not change
one of the two numbers p, q.
However, in general, a map defined on a set of trees can not be specified to preserve globally
one orientation, since it usually changes both values p and q acting on different trees. This
happens, in particular, to the face d when restricted to
each component Y p;q ae Y n , it takes value in one of the two components Y p\Gamma1;q , Y p;q\Gamma1 of Y
depending on the tree y of Y p;q . Consider, for example, the face d 0 restricted to the component
takes value in Y 0;1 on , and in Y 1;0
on and .
Y 1;0
Y 0;1
This motivates the following definition.
2.7 - Oriented maps. be a linear map, and consider its restriction to
each component Y p;q ae Y n . We call oriented maps of f the following
defined as
ae f(y); if f(y) 2 k[Y p\Gamma(n\Gammam);q ],
0; otherwise,
vertical defined as
ae f(y); if f(y) 2 k[Y p;q\Gamma(n\Gammam) ],
0; otherwise.
In particular, we can consider the oriented maps defined by the faces d i and the degeneracies s j .
2.8 - Bicomplex of trees. For any natural numbers p; q, take k[Y p;q ] as the module of (p; q)-
chains, and define horizontal and vertical boundary operators d
respectively as
d h :=
i and d v :=
2.9 - Lemma. The oriented boundaries defined above satisfy d h d
are chain complexes for any p; q - 0.
Proof. It suffices to show that the oriented faces d h
i and d v
still satisfy the simplicial relations
(d) of (2.1). Let us show, for instance, that d v
i for any i ! j. It suffices to prove that
is a vertical map (i.e. d i only if d j \Gamma1 d i is vertical. A face d i
deletes a =-leaf if the i th -leaf itself is oriented like =, i.e. , or if it is a n-leaf such that
. Then
it is easy to see that both d i d j and d j \Gamma1 d i delete two =-leaves only on the four combinations of
these two possibilities for the leaves i and j. 2
2.10 - Remark. By assumption, in a pre-simplicial module the faces are all non-zero maps.
Therefore, even if the horizontal (resp. vertical) faces satisfy relations (d), the horizontal families
vertical families k[Y p;  ]) are not considered to be pre-simplicial modules.
2.11 - Proposition. The triple (k[Y  ;  ]; d v ; d h ) forms a chain bicomplex, whose total complex
is the shifted complex of binary trees (k[Y  +1 ]; d).
\Gamma\Psi
oe
oe
oe
oe
oe
oe
oe
oe
oe

Figure

2: Bicomplex of rooted planar binary trees.
Proof. On any tree y, the map d i acts either as d h
(because d v
or as d v
(when
an obvious identity d
Consequently,
the boundary operator is the sum . Then we have
From (2.9) it follows that d h d v This show at
the same time that (k[Y  ;  ]; d h ; d v ) is a bicomplex, and that k[Y  +1
2.12 - Remark. The bicomplex of trees gives rise to a spectral sequence
which is zero everywhere, since the complex of trees is acyclic and the E 1 -plane, in a similar way,
can be shown to be zero. However the peculiar structure of trees becomes interesting when k[Y n ]
appear as tensor components of some chains module, as for the chain complex of dialgebras (see
[L], [F1] and [F2]). In this case, the bicomplex of trees permits us to find a spectral sequence
which converges to the homology of the given complex.
3 Decomposition of the bicomplex of trees into towers
In this section we show a technical result which helps drastically in the computation of dialgebra
homology as a derived functor (see [F2]). The main theorem says that any vertical complex
is a direct sum of subcomplexes whose homology can be computed for some dialgebras.
At the same time, being related to intrinsical properties of the trees, this result clarifies the
simplicial structure of the bicomplex. Each subcomplex, called vertical tower and denoted by
is constructed on a single tree, provided that it has all zero vertical faces and called base
tree, by applying all possible vertical increasing maps of degree 1, i.e. by adding =-leaves in all
possible distinct ways. It turns out, due to the particular shape of planar binary trees, that
such towers are all disjoint one from each other and that they cover the whole bicomplex. This
structure yields a decomposition of the bicomplex of trees which has many regularities:
ffl The base trees arising in the vertical chain complex k[Y p;  ], for fixed p - 0, are in bijection
with p-trees (see lemma (3.10)), i.e. they are counted exactly by c
ffl The vertical tower T   (y), associated to a p-tree y, is a multi-complex with dimension
proposition (3.12)).
ffl The vertical tower T   (y), associated to a p-tree y, is a subcomplex of k[Y shifted by
the number of =-leaves of y (excluded its last leaf). This means that if y belongs to the
class Y p 0 ;q 0 of Y p , then Tm (y) ae k[Y p;q 0 +m ] for any m - 0 (see again lemma (3.10)). A
geometrical meaning of the number q 0 is given in the appendix.
We draw in fig. 3 a summarizing picture of the vertical towers at small dimension. The
details of the definitions and proofs are given in the remaining part of this section.
-base tree
r
r
r
r
r
r
r
r
r
r
r
r

Figure

3: Decomposition of the bicomplex of trees into vertical towers.
New kind of degeneracies: grafting operators.
In order to construct a vertical complex on a given tree, we need to introduce a second kind of
increasing maps Y n \Gamma! Y n+1 , besides the usual degeneracies s j .
The operation of adding a leaf to a tree consists, more precisely, in grafting a new leaf into a
given edge of the tree. The degeneracy operators defined in (2.4), in fact, graft a new leaf into
the edge which starts from any existing leaf. Thus, to define the remaining increasing operators,
we need a rule to label the internal edges of a tree.
3.1 - Labels of internal vertices and internal edges. Any binary tree with
and one root has precisely n internal vertices. Let us choose the following rule to label them.
An internal vertex is labeled by i if it closes a descending path which starts between the leaves
number
An internal edge of the tree is the branch delimited by two adjacent vertices, included the
root. We label by i the edge whose 'upper' extreme is a vertex labeled by i. (If we extend this
rule to the external edges, each leaf is labelled as the edge which starts from it.) For instance:
@
@
@
@
@ @
r
r
r
and
@
@
@
@
@ @
@
@
\Gamma24
Labels of internal vertices. Labels of internal edges.
In conclusion, any n-tree has n+1 external edges (the leaves), labeled from 0 to n, and n internal
edges (included the one which ends with the root), labeled from 1 to n.
3.2 - Grafting operators. For any n - 0, and for any th left and right
grafting operator the maps
which graft a new leaf into the i th internal edge of a tree, respectively from the left and from
the right. For example
l
Notice that the operation of grafting a new leaf into an external edge produces the same
result whether it is performed from the left or from the right: it consists in bifurcating the leaf.
Thus, as we said, the grafting operators on external edges coincide with the degeneracies.
We wish to determine whether increasing maps are horizontal or vertical. We show in the
next lemma that the orientation of grafting operators does not depend on the index i nor on
the tree on which the map is acting. Instead, the orientation of the degeneracy s i changes with
the index depending on the particular tree on which it is acting.
3.3 - Lemma. Let p; q be natural numbers, and
1. The left grafters l i are horizontal maps, i.e. l
Similarly, the right grafters r i are vertical maps, i.e. r
2. For any (p; q)-tree y, and for any index i 2 f0; :::; ng, the degeneracy s i is horizontal on
y, i.e. s v
only if the i th leaf of y is oriented like =. Similarly, s i is vertical on y,
i.e. s h
only if the i th leaf of y is oriented like n.
Proof. 1. Any left grafter l i acts by adding a n-leaf, which will be labeled, in the (n
by an integer j 2 f0; ng. The terminal vertex of the new leaf will be consequently labeled
1. Similarly, any left grafter r i acts by adding a =-leaf, which will be labeled, in the
1)-tree, by an integer j 2 f1; 2; 1g. The terminal vertex of the new leaf will be
consequently labeled by j.
2. The map s i acts on the leaf as
, thus s i adds a n-leaf (it is horizontal). Similarly, s i
acts on the leaf as
, thus s i adds a =-leaf (it is vertical). 2
Since we wish to deal with vertical complexes k[Y p;  ], throughout the remaining part of this
section we fix a p - 0, and observe (p; q)-trees for different values of q - 0.
The next lemma says weather an increasing map is distinct from any other or produces the
same tree as some other map.
3.4 - Labels of oriented leaves. Let y be a (p; q)-tree, and 1. We define a map
by assigning to the integer i the label of the i th n-leaf
of y, counting leaves from left to right and excluding the 0 th leaf.
Any n-leaf (except the first one) is grafted into a =-leaf (included the last one). Thus there
is a map b y : f1; :::; pg \Gamma! f1; :::; ng, b y
i , which assigns to the integer i the label of the
=-leaf into which the i th n-leaf is grafted, i.e.
a b
Call A(y) := fa y
ng the image of a. Since the p n-leaves of y are distinct by
assumption, the map a y is a bijection between the set f1; :::; pg and the set A(y). Thus we can
also define a ng by b(a y
. Call B(y) := fb y
ng the
image of b.
Some properties of the maps a and b are given in section A.
y be a (p; q)-tree, and
1. The degeneracy maps are all distinct from each other, i.e. for any
then s i (y) 6= s j (y). (In particular this holds for any index in the set A(y).)
2. Any right grafting map into an internal edge labeled as a =-leaf produces the same tree as
some degeneracy map or a right grafting map into an edge labeled as a n-leaf. In other words, for
any index i 2 f1; :::; ng n A(y), there exists an a 2 A(y) such that r i
3. All right grafting maps into internal edges labeled as a n-leaf are distinct from each other
and from any degeneracy map. That is, for any a 2 A(y), r a (y) 6= s a 0
(y) and r a (y) 6= r a 0
(y) for
any a 0 6= a 2 A(y).
Thus, for any (p; q)-tree y, there are precisely vertical non-zero degeneracies
acting on y, namely s
distinct vertical grafting maps, namely r a 1
Proof. The assertion 1. is obvious.
2. Suppose that an internal edge is labeled as a =-leaf, by i. Then there are two possible
shapes of the branch around the i th leaf:
In the first case, we have there is no a 0 between a and b,
we have r b Otherwise, if there are a 0 ; a 00 ; ::: 2 A(y) such that a ! a
we have r b
(y).
In the second case, we have i 2 f1; :::; ng n [A(y) [ B(y)], and the i th -leaf is grafted into
a n-leaf labeled, say, by a, so a there are no a 0 between a and i, we have
Otherwise, if there are a 0 ; a 00 ; ::: 2 A(y) such that a ! a
(y).
3. The position of an internal edge which is labeled as n-leaf is very peculiar. Suppose that
it is labeled by a. Then there must be an index a 0 ! a such that the internal edge a starts at
the intersection between the n-leaf a 0 and the =-leaf b(a). Thus there are only two possible
shapes of the branch around the a th leaf, and r a acts as follows:
a' a b=b'
a 7! r a
a' a b b'
and for
a' a b b'
a 7! r a
a' a b b'
It is then clear that r a (y) can never be obtained by bifurcating a leaf: the branch
a b
obstructs
it. So r a (y) 6= s a 00 (y) for any a 00 6= a.
Now consider the right grafter into another n-leaf. Again the internal edge is placed in a
peculiar position, such as the one labeled by a. Let us consider the 8 mutual positions of two
internal edges labeled by a and a 0 . Suppose a
a' a b=b'
a'
a
a' a b=b'
a'
a
a' a b b'
a'
a
a' a b b'
a'
a
a' b' a b
a' a
a' b' a b
a'
a
a' b' a b
a' a
a' b' a b
a' a
One can check that on these 8 trees we always have r a 6= r a 0 , so finally r a is always different
from r a 0
. 2
Since any map r i coincide with some degeneracy, for ng n A(y), we give the
commutation relations between r a and the faces d i only for a 2 A(y).
Lemma. The right grafting operators satisfy the relations
r
r a d i ; for a - i - b(a),
r a d
(r) r a r a 0
r a 0 +1 r a ; for a ! a 0 and b ! b 0 ,
r a 0 r a ; for a ! a 0 and b - b 0 ,
(Notice that the last relation involves an edge labeled as a =-leaf.)
Proof. (dr) For any a 2 A(y), the operator r a can act on the two basic trees (1) and (2) of
lemma (3.5). Relations (dr) can be checked on (1) with the help of the following observations.
a, the leaf number a of (1) is labeled by a \Gamma 1 in d i (1), hence also the internal edge
labeled by a in (1) becomes a \Gamma 1 in d i (1).
ffl If a - i - b, the edge labeled by a in (1) remains labeled by a in d i (1).
1, the face d b+1 deletes precisely the leaf which has just been added by r a .
1, the edge labeled by a in (1) remains labeled by a in d i (1), but the leaf number
deleted in r a (1) by the face d i was labeled by
The same observations hold for the tree (2).
Check directly on the 8 trees (ij) and [ij], for of lemma (3.5). 2
Decomposition of the vertical complexes into towers.
towers. Let y be a (p; q)-tree. We call vertical tower over y the family T   [y],
For example, the tree
Thus
ae
oe
and so on. To simplify the notation, we use the same symbol Tm [y] to denote the subset of trees
and the k-module spanned by these trees. In general, a vertical tower is not a vertical complex.
Lemma. For any (p; q)-tree y, the vertical tower T   [y] is closed for the vertical faces d v
if and only if d v
Proof. (i) Assume that d v
1. We show that if y 0 belongs to Tm [y]
such that d v
the tree d v
belongs to Tm\Gamma1 [y]. We proceed by induction on m.
ffl First assume that y by definition of vertical tower we know that y
or there exists an index i 2 f1; :::; pg such that y 0 is equal either to s a i (y) or to r a i (y). Now
consider a 2g such that d v
s a i d v
for a i possibly equal also to 0, or
k r a i
r a i
r a i d v
r a i d v
In conclusion we have that d v
ffl Assume now that for any tree y 00 2 Tm\Gamma1 [y], we have d v
We show that the same holds for any tree y
In fact y 0 must be equal either to s 0 (-y), s a i
(-y) or to r a i
(-y), for an index i 2 f1; :::; pg, with
Thus, in the first case (for a i also equal to 0)
k s a i
s a i d v
belongs to Tm\Gamma1 [y], because for inductive hypothesis d v
and in the second case
k r a i
r a i
r a i d v
belongs to Tm\Gamma1 [y] for the same reason.
(ii) Assume now that there exists an index k 2 f0; :::; p+q+1g such that d v
We show that the tower over y is not closed for the vertical faces. In fact:
0 (y) is a tree
in Y p;q which is different from y, i.e. it does not belong to T 0 [y].
a i
a i +1 (y) is a
tree in Y p;q different from y.
ffl If a
k (y) is a
tree in Y p;q different from y. 2
Base trees. For any p - 0, we call (p;  )-base tree any (p; q)-tree y such that d v
for all By (3.8), the vertical tower constructed on a base tree is a vertical complex.
3.10 - Lemma-Notation. There is a bijective correspondence between the set Y p and the
set of (p;  )-base trees. Therefore we denote by T   (y) the tower T   [~y] on the (p;  )-base tree ~y
corresponding to the p-tree y. Moreover, the number of =-leaves of a p-tree y is equal to the
number of =-leaves of its associated base tree ~y.
Proof. Let
G
be the map which sends a tree y into the tree '(y) obtained by bifurcating all the =-leaves. The
map ' is clearly injective, let us show that it is well defined.
ffl If y is a p-tree, then the tree '(y) has exactely p leaves oriented like n. In fact, suppose
that the p-tree y lies in the component Y r;s of Y p , i.e. y has r internal n-leaves and s internal
=-leaves, with r p. Then the tree '(y) has the original r n-leaves, and the new s
n-leaves appearing after the bifurcation of the s =-leaves.
ffl If y is a p-tree, then the tree '(y) can have at most =-leaves. In fact, the
=-leaves of '(y) are exactely the s original =-leaves of the p-tree y belonging to the component
Y r;s , and clearly Hence '(y) belongs to the union
F
ffl Let us show that if '(y) belongs to the set Y p;s , then d v
If the index i labels a =-leaf of '(y), it comes by construction from a bifurcated =-leaf of y, thus
produces a tree with the same number of =-leaves, and a n-leaf less. When the index i labels
a n-leaf of '(y), the face d i clearly deletes a n-leaf unless the th leaf is a = leaf which is
grafted into the i th leaf, and this is impossible in the tree '(y), because by construction any
=-leaf is preceded by a n-leaf which is grafted into the =-leaf, and not the opposite.
Finally, to prove that the map ' is a bijection, we show that the surjective map
G
Y p;q \Gamma! Y p
which deletes all the =-leaves, included the last one, is inverse to ' when restricted to the subset
of trees with d v
1. The composition / ffi ' is clearly the identity
map on Y p . On the other side, let y be a (p; q)-tree, for some q - 0. By construction, the tree
'/(y) is obtained by deleting all the =-leaves from y, and then replacing all the new =-leaves
with bifurcations. Thus y and '/(y) can only differ for some =-leaf, say labeled by k, such
that the leaf labeled by k \Gamma 1 is not a n-leaf grafting into it. Any such leaf produces a vertical
non-zero face d v
k . Since the domain of / is restricted to the trees with only zero vertical faces,
the trees y and '/(y) must coincide. 2
3.11 - Theorem. For any p - 0, the vertical complex (k[Y p;  ]; d v ) is the direct sum of towers,
shifted by the number q y of =-leaves of y.
Proof. By construction, the sum of the towers T   (y) is direct. We show that it covers the
whole vertical complex k[Y p;  ], i.e. that for any y 2 Y p;q , there exists a tree y
such that
be its (p;  )-base tree. Then
y differs from ~
y 0 for some =-leaves which are not labelled by any b i , with In fact,
by definition, any tree in degree m is obtained by adding a =-leaf to a tree in degree
means of the maps s a or r a . Thus y belongs to Tm [ ~
. 2
3.12 - Proposition. The tower T   (y), associated to a p-tree y, is the total complex of a multi
complex with dimension 1. Hence the number of its direct summands, at any degree
- 0, is given by the binomial coefficient
Proof. Apply definition (3.7) and remark, after (3.6) and (3.5), that 2p + 1 is precisely the
number of distinct maps which can act on a tree with p n-leaves by adding a =-leaf. 2
Drawings of vertical towers.
3.13 - Vertical tower for The vertical complex k[Y 0;  ] coincides with the tower T   ( )
with base , and it is pre-simplicial since all the faces are non-zero (fig. 4).

Figure

4: Vertical tower T   ( ) with base .
3.14 - Vertical tower for 1. The vertical complex k[Y coincide with the tower T   ( )
with base . This complex is the total of a multi-complex with dimension (fig. 5).
6 I
\Phi-
III
\Gammad 3

Figure

5: Vertical tower T   ( ) with base .
3.15 - Vertical towers for 2. The set Y 2 contains two trees, and , associated
respectively to the base trees and . Hence k[Y 2;  the two
towers are multi-complexes with dimension (fig. 6 and fig. 7).
3. The set Y 3 contains five trees, , , , and ,
which correspond, respectively, to the five following base trees:
Hence k[Y 3;  ] is the direct sum of five vertical towers, based on these five trees, which are
multi-complexes with dimension 7.
In a similar way one can proceed for p ? 3. Each vertical complex k[Y is the direct sum of
vertical towers (where c p is the number of p-trees), and each vertical tower is a multi-complex
with dimension
Qk
I
6 II
III
@
@
@
@
@
@
@
@
@
@
@
@ @R
IV
\Gamma\Psi
@
@
@
@
@
@
@
@
@
@
@
@
@
@

Figure

Vertical tower T   ( ) with base .
Qk
I
6 II
III
@
@
@
@
@
@
@
@
@
@
@
@ @R
IV
\Gamma\Psi
@
@
@
@
@
@
@
@
@
@
@
@
@
@
\Gammad 3
\Gammad 5

Figure

7: Vertical tower T   ( ) with base .
A

Appendix

. An invariant of the towers
In this appendix we show that the classes of trees are in bijection with certain classes of set
maps. From this construction it is then clear that the number of =-leaves of a tree y characterizes
the shape of all trees belonging to the vertical tower T   (y) associated to y.
A.1 - Proposition. For any p; q - 0, there is a bijective correspondence between (p; q)-trees
and pairs of set maps satisfying the following
conditions:
1. if i !j then a(i)!a(j), hence the map a is monotone strictly increasing;
2. a(i)!b(i) for any i, in particular the maps a and b have disjoint image;
3. if i !j and a(j)!b(i), then b(i)-b(j) (equivalently, if i !j and b(i)!b(j) then b(i)!a(j)).
Proof. (i) Let us show that for any (p; q)-tree y, the set maps ng defined
in (3.4), with which label the oriented leaves of y, satisfy conditions 1, 2, 3. The
first two conditions are evident: 1 means that the p n-leaves are distinct, and 2 means that any
n-leaf is distinct from the =-leaf into which is grafted. Condition 3 is due to the facts that any
n-leaf cannot coincide with any =-leaf, so b i 6= a j , and that for the relation
would correspond to the following impossible picture:
a b
a b
ng be two maps satisfying conditions 1, 2,
1. Then we can construct a tree y with the following algorithm.
label them from 0 to p 1. Draw an edge n from the 0-th
leaf, an edge = from the last leaf and the root.
ffl From any leaf labelled by a(i), draw an edge n and graft it into an edge = drawn from the
leaf labelled by b(i). Extend all the edges untill they reach an edge of opposite orientation.
ffl From any remaining leaf, draw an =-edge, and reach an n-edge.
None of these operations has any freedom of choice, so the tree thus obtained is uniquely deter-
mined, and it is clearly described by the given maps a; b. 2
Here is an example of the algorithm above. Let 2. Choose two
maps according to conditions 1, 2, 3 of (A.1), for instance,
5:
Now follow the three steps in the drawing.
A.2 - Blocks. The map b is not necessarily monotone. However we can say that it is "block"
monotone, since it satisfies
4. For any triple of indices k such that b(i) ! b(j), it is impossible that b(k) - b(i).
This condition says that whenever the map b satisfies the inequality sign
"!" separates two blocks in the image of b, given, respectively, by indices preceding and following
the inequality sign. This follows easily from the above conditions 1, 2, 3. By 3, the inequality
implies that b(i) ! a(j). Condition 2 says that a(k) ! b(k). Thus, combining the two
inequalities and the thesis, we obtain which is impossible because, by
Remark that the number of blocks of the (p; q)-tree associated to the maps a and b can vary
between 1 and p, for p ? 0, and is assumed to be 1 for
A.3 - Proposition. All the trees belonging to a vertical tower T   (y) have the same number
blocks, where q y is the number of =-leaves of the tree y.
Hence the number q y has a geometrical meaning which is invariant in the vertical tower T   (y)
constructed over y, being related to the number of blocks of leaves of any tree in the tower.
Proof. If a p-tree y has q y -leaves, by (3.10) we know that its associated oriented tree ~y is a
)-tree. The tower T   (y) is based on this tree, a nd by construction the tree ~y is the one
with minimal number of =-leaves in the tower. Grafting new =-leaves into any n-leaf does not
affect the ordering of the indices b i , and hence of the number of blocks. Thus we only need to
show that ~y itself has qy
Denote by b y the number of blocks of the (p; q y )-tree ~y. By definition (A.2), the number of
cases the total number of cases between the p indices b i is
y is the number of cases (i that ~y is the tree with
less =-leaves in the tower). This means that y is the number of coinciding =-leaves among
possible ones. Therefore the total number of distinct =-leaves of ~y (included the last one) is



--R

Some remarks and results on Catalan numbers
Historical note on a recurrent combinatorial problem
Dialgebra homology of associative algebras

Research bibliography of two special number sequences

Homoopyy of pseudosimplicial groups
The art of computer programming I.

"Category theory, homology theory and applications"
--TR
Concrete mathematics: a foundation for computer science
The art of computer programming, volume 1 (3rd ed.)
almost-simplicial sets;planar binary trees