Printer Friendly

On symmetric structures of order two.

Let ([[omega].sub.n])0<n be the sequence known as Integer Sequence A047749 In this paper, we show that the integer [[omega].sub.n] enumerates various kinds of symmetric structures of order two. We first consider ternary trees having a reflexive symmetry and we relate all symmetric combinatorial objects by means of bijection. We then generalize the symmetric structures and correspondences to an infinite family of symmetric objects.

Keywords: symmetry of order two, bijections, symmetric ternary trees, symmetric combinatorial structures

1 Introduction

Let N = {0, 1, 2, 3, ...} be the set of nonnegative integers and [N.sup.*] = N\{0}. We denote [W.sub.n] the set of sequences of integers (called words) of length n [member of] [N.sup.*] such that for each w = [w.sub.1][w.sub.2]w.sub.3] ... [w.sub.n] [member of] [W.sub.n], we have

1. [w.sub.1] = 1;

2. [w.sub.i] > 0, for all i = 1, 2, 3, ..., n;

3. [w.sub.i] - [w.sub.i-1] [member of] {1, -1, -3, -5, ...}, for all i = 2, 3, ..., n.

For instance, we have [W.sub.4] = {1234, 1232, 1212}. The sequence [{[W.sub.n]}.sub.n[member of]N] has been enumerated in many ways in [10]. The cardinality of the set [W.sub.n], for n [greater than or equal to] 1, denoted [omega.sub.n], is given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

The first few values of [omega.sub.n] for n = 1, 2, ..., 10 are 1, 1, 2, 3, 7, 12, 30, 55, 143, 273. Note that the sequence [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is indexed in the On-line Encyclopedia of Integer Sequences [32] as sequence number A047749. This formula can be established by Lagrange inversion using generating series, by induction or by a bijective proof using lattice paths; see [10]. We present here a slightly modified proof.

Bijection 1 (([10]) From words to lattice paths.)

Let us consider a word w = [w.sub.1][w.sub.2] ... [w.sub.n] of the set [W.sub.n], where [w.sub.j] is a positive integer for 1 [greater than or equal to] j [greater than or equal to] n. We map the words of [W.sub.n] to lattice paths composed of n + [n/2] steps where the steps are u = (1, 1) and d(1,-2), using the following process:

1. to the integer i there corresponds a step u = (1, 1) at level i - 1;

2. to obtain a lattice path, connect all the steps u together with steps d = (1,-2);

3. add enough steps d at the end of the path to reach the level 0 or 1 depending on the parity of n.

By construction, such lattice paths never pass below the x-axis and end at height 0 or 1 depending on the parity of n. Using the Cycle lemma (see [9]), we can show that these paths are enumerated by the integer [omega.sub.n] defined by relation (1).

For instance, the three words of the set [W.sub.4] = {1212, 1234, 1232} are mapped to the set

{uuduud, uuuudd, uuudud}

corresponding to the lattice paths of Figure 1.

[FIGURE 1 OMITTED]

When the integer n is even, [omega.sub.n] is a generalized Catalan number of order three. Indeed, we can define the generalized Catalan number of order k, k [less than or equal to] 2, denoted [c.sub.k.sub.n], by the following relation

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

When k becomes 2, we recover the well-known Catalan numbers. Moreover, for different values of the integer k, the sequence {c.sup.k.sub.n}n[member of]N is indexed in the On-line Encyclopedia of Integer Sequences [32]. For example, for k = 2, 3 and 4, these are sequences A000108, A001764 and A002293, respectively. Generalized Catalan number appear in Section four of this paper as a generalization of the integers [omega.sub.n].

The number [omega.sub.n] defined by formula (1) enumerates many other combinatorial structures. Surprisingly, these structures all possess a symmetry of order two which can be a reflexive symmetry, an invariance under orientation reversing,.... More precisely, these structures are left fixed under the action of an involution. These objects are various: trees (ternary, even, non-crossing), 2-trees (solid, quadrangular), cacti, dissections and diagonally convex directed polyominoes. Our goal is to link bijectively all these combinatorial symmetric structures thus showing they are counted by [omega.sub.n]. To achieve this goal, we first give in the following section a correspondence between words belonging to [omega.sub.n] and symmetric ternary trees of n vertices. We consider ternary trees as our central structures. Thus, in Section three, we propose bijections between symmetric ternary trees and different symmetric objects. Finally, in Sections four and five, we generalize the results of the three previous sections considering symmetric k-ary trees, where k is any odd integer greater than three.

2 Symmetric ternary trees

In this section, we give a bijection between symmetric ternary trees and words of the sets [omega.sub.n], n [member of] [N.sup.*]. First of all, we recall the definition of (complete) ternary trees and clarify the notion of symmetry.

A ternary tree is a tree-like structure that is rooted and in which each vertex has at most three children and each child of a vertex is designated as its left or middle or right child. A complete ternary tree is a ternary tree where every vertex has either 0 or 3 children. Notice that by removing all the leaves of a complete tree or adding to each vertex (node or leaf) of a ternary tree 0 or 1 or 2 or 3 leaves so that the outdegree be 3, we obtain a bijection between ternary trees with n edges and complete ternary trees with n + 1 nodes. See Figure 2 (a) for an example of a ternary tree having 7 vertices; see also Figure 3 (a) and (b) for a ternary tree and its corresponding complete ternary tree We say that a ternary tree is symmetric if it has a reflexive symmetry about the axis passing through the chain of middle children of the root. See Figure 2 (b) for a symmetric ternary tree with 13 vertices. It is clear that the above bijection preserves symmetry.

[FIGURE 2 OMITTED]

It is easy to compute the number of symmetric ternary trees using functional equations and Lagrange inversion and to see that this number is [omega.sub.n] defined by (1). As symmetric ternary trees are our central structures, from which correspond many other symmetric objects, we have to link them to the word sets [{[W.sub.n]}.sub.n[member of]N]*. For this purpose, we provide the following bijection.

Bijection 2 (From symmetric ternary trees to words.)

Let [T.sub.n] be the set of symmetric ternary trees over n vertices. The bijection is illustrated by Figure 3. Let t [member of] [T.sub.n] be a symmetric ternary tree. Complete it first, that is, add enough leaves at t such that each vertex has outdegree three or zero. Split the symmetric complete tree along the chain of middle children of the root (called main middle chain), keeping the right part and draw the resulting tree in such a way that the main middle chain is horizontal; see Figure 3 (c). We obtain a linear order of ternary trees, possibly reduced to a single leaf, ordered along the main middle chain begining with the root of t. We then encode this linear order by a word on an alphabet of two letters, namely f standing for a node and, x for a leaf; see Figure 3 (c). Notice that we do not care about the vertices belonging to the middle chain, just forgetting them, as well as the ending leaf of the middle chain. Next, form a word by reading each letter encountered during a depth-first search process (not keeping the letter associated to a previously visited vertex) for each tree in the linear order. The words are then concatenated according to the linear order; see Figure 3 (d). We obtain a word containing n occurences of the letter x. In the example of Figure 3, we get the word ffxfxxxxfxxxxxfxxx. Each sequence of consecutive f's is coupled with the following x in the word. In our example, the coupling phase gives

[FIGURE 3 OMITTED]

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

We associate a cost of 1 to each x and, for a sequence of i consecutive letters f followed by an x, the associated cost is -2i + 1. In the example, we get

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

The new word is composed of n integers. Reversing this word yields a word v = [v.sub.1][v.sub.2] ... [v.sub.n]. To end the map, we obtain a word w belonging to the set [W.sub.n], using the following process:

1. [w.sub.1] = [v.sub.1] = 1;

2. [w.sub.i] = [[w.sub.i-1] + [v.sub.i], for all i = 2, 3, ..., n.

To end this correspondence, we conclude our example:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

We can see easily that this process is invertible.

3 Symmetric structures

This section is devoted to the introduction of discrete structures possessing a symmetry of order two that are enumerated by the integer [omega.sub.n]. We provide, when necessary, bijections between these structures, and relate them to symmetric ternary trees.

3.1 Symmetric 2-trees, cacti and quadrangulations

In this section, we deal with 2-dimensional trees, or in brief 2-trees. A 2-tree is a simple connected graph composed of triangles glued together along edges in a tree-like fashion, i.e., without cycles of triangles. There exists an abundant literature about 2-trees; see [1, 29, 18, 19] and more recently [24, 16, 4, 21, 22, 20, 23] and their references. A 2-tree is (well) oriented if all of its edges are oriented in such a way that each triangle forms an oriented 3-cycle. Therefore, a 2-tree can be oriented in at most two different ways.

We consider two generalizations of 2-trees, namely solid 2-trees and outerplanar 4-gonal 2-trees. A solid 2-tree is a spatial embedding of a 2-tree, i.e., one has to take into account the cyclic order of the triangles around each edge contrarily to classical 2-trees where there is no structure around each edge.

The essential difference is that in a solid 2-tree, triangles cannot interpenetrate themselves. Solid 2-trees have been introduced and enumerated according to edge number and edge degree distribution in [4, 5]. In their papers, the present authors consider the class of planted solid 2-trees. These structures are planted at an oriented edge, implying that the cyclic order of triangles around the root-edge is broken, thus creating a linear order (defined, by convention, by the right hand rule) on the triangles incident to the root-edge. Observe that the orientation of the root-edge can be uniquely extended to the whole structure by first orienting the triangles incident to the root-edge (in a cyclic way) and pursue with all the adjacent triangles until each edge receives an orientation. Therefore, only the orientation of the root-edge is indicated in the pictures. A symmetric solid 2-tree is a planted solid 2-tree invariant by orientation reversing; see Figure 4 (c) for an example of symmetric 2-tree. In [4, 5], the number of symmetric solid 2-trees is shown to be given by formula (1).

[FIGURE 4 OMITTED]

[FIGURE 5 OMITTED]

Let us now consider outerplanar 4-gonal 2-trees. The term 4-gonal means that we have replaced triangles by quadrilaterals; see Figure 5 (a). More generally, we call k-gonal 2-tree, a 2-tree in which triangles are replaced by k-sided polygons, also called k-gons. In [22], enumeration and asymptotics of k-gonal 2-trees are provided and, in [20], we can find a weighted enumeration according to the perimeter of the structures. A graph G is outerplanar if there exists an embedding of G in the plane in such a way that each vertex lies in the outer (infinite) face. We can show that a k-gonal 2-tree is outerplanar if and only if it can be embedded in the plane in such a way that all faces (except possibly the outer face) are k-gons or equivalently if there are no more than two k-gons glued on each edge. Harary et al. give the enumeration of outerplanar k-gonal 2-trees in [19], and more recently, in [21], Labelle et al. propose an explicit classification of outerplanar 2-trees according to their symmetries. In [19], the authors consider some outerplanar k-gonal 2-trees rooted at an external edge (that is, an edge adjacent to at most one polygon) equipped with an orientation; see Figure 5 (b), for k = 4. We call quadrangular 2-tree an outerplanar 4-gonal 2-tree rooted at an external edge equipped with an orientation. A quadrangular 2-tree is symmetric if it is left fixed under orientation reversing of the root-edge. This implies that the quadrangular 2-tree possesses a reflexive symmetry about an axis coinciding with the root-edge mediatrix (if drawn with squares). Figure 5 (c) shows a symmetric quadrangular 2-tree.

[FIGURE 6 OMITTED]

Our first task is to relate symmetric ternary trees and symmetric quadrangular 2-trees. After that, we propose a bijection between symmetric ternary trees and symmetric planted solid 2-trees.

Bijection 3 (From symmetric ternary trees to symmetric quadrangular 2-trees.)

This bijection is extremely simple. Indeed, given a symmetric ternary tree [tau], it suffices to draw it with right angle between edges (see Figure 6 (b)) and then replace each vertex of [tau] by a quadrilateral. Two quadrilaterals are adjacent if the corresponding vertices in [tau] were adjacent.

Observe that the above bijection is also valid for the nonsymmetric case, giving a correspondence between ternary trees on n vertices and quadrangular 2-trees with n quadrilaterals.

Bijection 4 (From symmetric ternary trees to symmetric planted solid 2-trees.)

Let [tau] be a symmetric ternary tree. We begin this bijection by splitting _ along its main middle chain; see Figure 7 (a) and (b). Forgetting the vertices of the main middle chain, we get a linear order of length k (in the example of Figure 7, k = 5) of ternary trees (not symmetric in general). Therefore, the number of triangles sharing the root-edge of the corresponding planted solid 2-tree is k. Put now a triangle for all the vertices of each ternary tree of the linear order using the following process, for a given vertex v (see Figure 7 (c)):

1. a vertex u of the triangle corresponds to v;

2. the opposite triangle's side of u is orthogonal to the edge {v, v'}, where v' is the parent of v in the considered ternary tree.

[FIGURE 7 OMITTED]

[FIGURE 8 OMITTED]

For the clarity of the picture (Figure 7 (c)), the vertices of the tree are drawn inside triangles. Then, each structure obtained this way is contracted. Actually, all the chains of each ternary tree are contracted as indicated by Figure 8, where the chain can be either a left, right or middle one, and the [T.sub.i]'s and T[T.sub.i]'s are structures already contracted or not, that have to be attached on the corresponding edge. After the contraction phase, we get a sequence S of length k of planted solid 2-trees, which can consist only of an oriented edge; see Figure 7 (d).

It is important to note that the resulting planted solid 2-tree is independent of the chosen order of contraction. Take now a k-tuple of triangles whose edges are labelled as shown by Figure 9. We attach

* on the edge labelled i, the [i.sup.th] planted solid 2-tree in S according to the root-edge orientation;

* on the edge labelled i', the image of the [i.sup.th] planted solid 2-tree in S obtained by orientation reversing, according to the root-edge orientation.

[FIGURE 9 OMITTED]

We clearly get a symmetric planted solid 2-tree and it is easy to see that the above process is a bijection. 2

An example of the two previous bijections is given in Figure 10.

We now give another obvious correspondence between symmetric quadrangular 2-trees and rooted plane quadrangulations of polygons. A quadrangulation of a polygon is a dissection of a convex polygon with non-intersecting diagonals into 4-sided cells; see Figure 11 (a) for an example of a quadrangulation of a 12-gon. It corresponds to a generalization of triangulations. We say that a quadrangulation is rooted if an edge of the polygon is distinguished. A quadrangulation is called plane if it is embedded in the plane. Observe that, in a rooted plane quadrangulation, the root edge can be canonically oriented with respect to the plane orientation. A rooted plane quadrangulation is called symmetric if it has a reflexive symmetry about an axis passing through the middle of the root edge (it is in fact the mediatrix of the rooted edge if we draw a regular polygon). Actually, the quadrangulation of Figure 11 (b) is symmetric. We now present a staightforward bijection between symmetric rooted plane quadrangulations and symmetric quadrangular 2-trees.

[FIGURE 10 OMITTED]

Bijection 5 (From symmetric quadrangular 2-trees to symmetric quadrangulations.)

The bijection is obvious: it consists in a planar deformation of quadrangular 2-trees. By this way, from an outerplanar 2-tree built over n squares, we obtain a quadrangulation of a 2(n + 1)-sided polygon with n - 1 dissecting lines. See Figure 11 (a) and (b).

[FIGURE 11 OMITTED]

To end this subsection, we consider plane 3-gonal cacti. A 3-gonal cactus is a simple connected graph in which each 2-connected component is a triangle. Essentially, a 3-gonal cactus is a connected simple graph composed of triangles attached together on vertices in an arborescent way (without cycles of triangles). A plane cactus is an embedding in the plane of a cactus. Thus, in a plane cactus, there is a cyclic configuration of connected components around each vertex. The orientation of this cyclic order is naturally given by the plane orientation. A 3-gonal cactus is symmetric, if it is invariant by reversing the plane orientation. In [5], we can find a bijection between unlabelled oriented solid 2-trees over n triangles and 3-gonal cacti on n triangles. This bijection preserves the symmetry.

Bijection 6 (From symmetric planted solid 2-trees to symmetric vertex-rooted cacti.)

This bijection, illustrated by Figure 12, is quite direct. To map a solid 2-tree into a 3-gonal cactus, construct the dual of each triangle by putting a vertex on each edge and joining vertices belonging to the same triangle; see Figure 12 (c). Keeping the cyclic order around each edge gives naturally a 3-gonal cactus; see Figure 12 (d). This construction is nearly the one of the edge-graph of a solid 2-tree. Obviously, the rooted vertex of the cactus corresponds to the planted edge of the solid 2-tree. It is clear that this bijection preserves the symmetry because it keeps the orientation of the structure.

[FIGURE 12 OMITTED]

3.2 Ternary trees, cacti and factorizations of n-cycles (12 ... n)

It is well known (see for instance Goulden and Jackson [17]) that the study of cacti is closely related to the enumeration of factorizations of particular permutations of the symmetric group. Before expliciting this relation, we give formal definitions of the so-called m-ary cacti and m-ary factorizations.

Definition 1 A plane m-gonal cactus is a plane embedding of a connected simple graph composed of m-gons (m-sided polygons) attached together at vertices in a tree-like fashion, that is, without cycle of m-gons. A m-ary cactus is a plane m-gonal cactus in which the vertices around a polygon are colored with the colors 1, 2, ..., m in the counterclockwise direction.

[FIGURE 13 OMITTED]

Definition 2 An m-ary factorization of the p-cycle [[gamma].sub.p] = (12 ... p) is an m-tuple ([g.sub.1], [g.sub.2], ..., [g.sub.m]) of permutations of the symmetric group Sp such that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Note that we use the convention to compute the product from left to right, that is, applying first g1. Furthermore, the following Euler formula must hold:

[absolute value of C] = 2n + 1,

where [absolute value of C] denotes the total number of cycles in [g.sub.1], [g.sub.2] and [g.sub.3].

In [17], Goulden and Jackson give a bijection between the set of m-ary cacti rooted at a polygon (see Figure 13 (b)) on p polygons and m-ary factorizations of the p-cycle [[gamma].sub.p]. This bijection is described by labelling canonically the polygons of m-ary cacti. Take any polygon-rooted m-ary cactus. First, the root-polygon receives label 1. Next, beginning with the edge incident to the distinguished polygon having endpointsmand 1, walk around each edge keeping the infinite face to the right. This way, we successively meet edges whose endpoints are of colors 1 and 2, 2 and 3, 3 and 4, and so on, until we reach an edge having endpoints m and 1. We associate the label 2 to the polygon incident to this edge. We repeat this process until each polygon is labelled. Figure 13 (c) shows the canonical labelling of the polygon-rooted 3-gonal cactus of Figure 13 (b).

Consider now, for i = 1, 2, ..., m, the set of vertices of color i and the cyclic order (counterclockwise direction) of polygon labels around each one of these vertices. Putting side by side the cycles associated with the color i, we obtain the permutation gi. For instance, along with the cactus of Figure 13 (b), we get the triplet of permutations [g.sub.1], [g.sub.2], [g.sub.3] [member of] [S.sub.8], given by

[g.sub.1] = (15)(34),

[g.sub.2] = (167)(35),

[g.sub.3] = (23)(18),

It is straightforward to confirm that [g.sub.1][g.sub.2][g.sub.3] = (12345678), keeping in mind that, by convention, the product is performed from left to right.

Furthermore, Bousquet in [6, 3] gives a bijection between m-ary trees, m-ary cacti and m-ary factorizations. In the current section, we present it in the special case m = 3 and then study the preservation of the symmetry through this correspondence. Note that, for m = 3, an m-ary factorization is called ternary factorization.

Bijection 7 (([6, 3]) From ternary trees to ternary factorizations.)

Let t be a ternary tree of p vertices. We first label it canonically. The root vertex receives label 1. Observe that each vertex of t belongs to exactly three chains: a left one, a middle one and a right one, where the chains can be of length one (that is, reduced to a single vertex). The starting point of the labelling algorithm is the root. Apply the function g1 at the current vertex, where the action of g1 is to move by a step South-West (left child) in the left chain if its lower node is not reached. If we are now at the end of a chain, the application of g1 sends us back to the North-East end of the chain. If the left chain in which we are located is of length one, then the application of [g.sub.1] corresponds to no move. In a similar way we define [g.sub.2] and [g.sub.3] with respect to the middle and right chains, respectively. After each successive application of [g.sub.1], [g.sub.2] and [g.sub.3], we place a new label. Figure 14 indicates the way labels 2 and 3 are obtained. Follow this process until each vertex receives a label. We get the canonically labelled ternary tree of Figure 14 (b). It is now easy to form the ternary factorization from the canonically labelled ternary tree. It suffices to read left, middle and right chains in the tree leading respectively to the permutations [g.sub.1], [g.sub.2] and [g.sub.3]. In the example of Figure 14, we get

[FIGURE 14 OMITTED]

[g.sub.1] = (15)(34);

[g.sub.2] = (167)(35);

[g.sub.3] = (23)(18):

From these permutations, we can construct a ternary cactus reversing the process of Goulden and Jackson. We notice that Bousquet gives in [6, 3] a direct correspondence from ternary cacti to ternary trees.

The following result is a simple exercise and the proof is left to the reader.

Lemma 1 Let n [less than or equal to] 1 and [pi] [member of] [S.sub.n] be any permutation satisfying [pi](1) = 1. If [sigma] [member of] [S.sub.n] is another permutation such that [pi] = [pi][sigma][[pi.sup.1] and if [c.sub.1] denotes the cycle containing the element 1 in the decomposition into disjoint cycles of [pi], then

On symmetric structures of order two

1. [pi] fixes all the elements of [c.sub.1], that is, [pi](i) = i, for all i [member of] [c.sub.1].

2. If [c.sub.1] is not the identity permutation and [c.sub.1] is of lenght k, then the cycle type of [pi] is ([i.sub.1], [i.sub.2], ..., [i.sub.k], ...), where all the [i.sub.j]'s are even except [i.sub.k].

The previous result remains true for any involution [pi] [member of] [S.sub.n], where the relation [pi] = [pi][sigma][pi.-1] means that [pi] and [sigma] commute: [pi][sigma] = [sigma][pi]. The following lemma is a straightforward consequence of Bijection 7. Recall that the Euler formula must hold for a ternary factorization.

Lemma 2 If a ternary factorization ([sigma.sub.1], [sigma.sub.2], [sigma.sub.3]), [sigma.sub.1][sigma.sub.2][sigma.sub.3] = (1 2 ... n), satisfies [sigma.sub.1] = [sigma.sub.3], then [sigma.sub.3] = [sigma.sub.3] = Id[S.sub.n] and [sigma.sub.2] = (1 2 ... n).

We are now able to prove the main result of the current section.

Proposition 1 The set [T.sub.n] of symmetric ternary trees on n vertices is in bijection with the set of ternary factorizations ([sigma.sub.1], [sigma.sub.2], [sigma.sub.3]) of the n-cycle (1 2 ... n) such that there exists an involution [pi] [member of] [S.sub.n] with [pi](1) = 1 and

[sigma.sub.1] = [pi][sigma.sub.3][pi] = [sigma.sub.2]. (3)

Proof: Let us consider a symmetric ternary tree t on n vertices. Recall first that, by Bijection 7, the triplet ([sigma.sub.1], [sigma.sub.2], [sigma.sub.3]) corresponding to the tree t is a ternary factorization, i.e., [sigma.sub.1][sigma.sub.2][sigma.sub.3] = (1 2 ... n). It is clear that [sigma.sub.1] and [sigma.sub.3] have the same cycle type since each left chain in [tau] corresponds to a unique right chain by the reflexive symmetry. Therefore, the permutations [sigma.sub.1] and [sigma.sub.3] are conjugate permutations of [sigma.sub.1]. Then, there exists a permutation [pi] [member of] [S.sub.n] such that [sigma.sub.1] = [pi][sigma.sub.3][pi.sub.-1]. It is straightforward to see that [pi] is an involution as a product of transpositions, each of these transpositions exchanging pairwise symmetric labels, and fixing 1. For instance, the symmetric ternary tree of Figure 15 leads to the following involution:

[pi] = (7, 14)(8, 20)(2, 17)(6, 15)(3, 16)(4, 18)(5, 19)(11, 13)

In the same way, the same involution [pi] shows that [sigma.sub.2] is self-conjugate . Conversely, let be given a ternary factorization ([sigma.sub.1], [sigma.sub.2], [sigma.sub.3]) such that there exists an involution [pi] fixing 1 with

[FIGURE 15 OMITTED]

[sigma.sub.1] = [pi][sigma.sub.3][pi], [sigma.sub.2] = [pi][sigma.sub.2][pi].

Let t be the ternary tree corresponding to ([sigma.sub.1], [sigma.sub.2], [sigma.sub.3]). We have to show that t is symmetric. Let x be any vertex of t. It is well known that there is a unique path starting at the root (labeled 1) and ending at x. This path can be described as follows:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where k [less than or equal to] 1 and [i.sub.j] [member of] {1, 2, 3}, for all j such that 1 [greater than or equal to] j [greater than or equal to] k. We show, by induction on k, that there exists a vertex y and a path from vertex 1 to vertex y

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

which is symmetric to the one leading to x, that is,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

This is obviously true for k = 0. By hypothesis, we assume this is true for all paths of length k. Using the fact that [pi] is an involution and [pi](1) = 1, we get

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Supppose there is a vertex x' such that x' = _[sigma.sub.1](x) (see Figure 16). We have

[pi](x') = [pi]([sigma.sub.1](x)) = [sigma.sub.3]([pi](x)) = [sigma.sub.3](y):

We argue that [sigma.sub.3](y) is at distance k + 1 from the root of t. Otherwise, [sigma.sub.3](y) is the first vertex in its supporting right chain. But,

[pi]([sigma.sub.3](y)) = [sigma.sub.1] ([pi](y)) = [sigma.sub.1](x)

and [sigma.sub.1](x) would be at a distance strictly less than k + 1 from the root, which is a contradiction. We can apply the same reasonning if x' = [sigma.sub.2](x) or x' = [sigma.sub.3](x). Therefore, if every path admits a symmetric image, the whole tree must be symmetric.

[FIGURE 16 OMITTED]

Remark 1 The ternary factorizations ([sigma.sub.1], [sigma.sub.2], [sigma.sub.3]) of Proposition 1 are called symmetric ternary factorizations of order n.

Corollary 1 The number of symmetric ternary factorizations ([sigma.sub.1], [sigma.sub.2], [sigma.sub.3]) of order n is given by the integer [omega.sub.n] defined in formula (1).

To end this section, we notice that, through the (reverse) bijection of Bousquet [6, 3], a symmetric ternary tree is mapped into a symmetric triangle rooted ternary cactus, where the symmetry of the cactus is expressed in terms of a reflexive symmetry passing through a vertex of the root-triangle and the opposite side of this vertex.

3.3 Ternary, even, non-crossing trees, directed diagonnally convex polyominoes and odd dissections

This section is essentially bibliographic. We first define other symmetric discrete structures enumerated by [omega.sub.n]. Next, we give references for bijections between them. An even tree is an ordered tree in which each node has even outdegree; see [33, 12, 11]. Figure 17 (a) shows an even tree on 11 vertices. An even tree is said to be symmetric if it has a reflexive symmetry about an axis passing through its root, thus splitting the tree into isomorphic subtrees; see Figure 18 (a).

[FIGURE 17 OMITTED]

A non-crossing tree is a plane embedded tree whose vertices coincide with the vertices of a convex polygon and such that the edges do not cross; see [28, 15, 13, 27] and Figure 17 (b). We consider that non-crossing trees are rooted at a vertex. A non-crossing tree is said to be symmetric if it possesses a reflexive symmetry about an axis coinciding with a bisector through the root; see Figure 18 (b). We implicitly assume that non-crossing trees are drawn on regular convex polygons.

[FIGURE 18 OMITTED]

A polyomino P is a finite connected union of unitary cells in the first quadrant of an R x R grid whose interior is supposed to be connected. We call it directed if any cell is reachable from a root-cell (namely, cell [0, 1] x [1, 0]) with a path contained in P with vertical (North) and horizontal (East) steps. A directed polyomino P is diagonally convex if its intersection with any line of slope -1 forms a continuous segment; see Figure 17 (c) and [31, 7, 14, 26]. These continuous chains of cells are called the diagonals of the diagonally directed convex polyomino and the size of such a polyomino is the number of its diagonals. A diagonally directed convex (DDC) polyomino is symmetric if the reflection about the line y = x leaves it unchanged; see Figure 18 (c).

Several papers deal with bijections between DDC polyominoes, ternary trees and non-crossing trees. In [8, 31], we can find rather complex bijections between DDC polyominoes and ternary trees; in [14], the authors presented a correspondence between DDC polyominoes with n diagonals and lattice paths from (0, 0) to (2n, n) never passing above the line y = x/2. We also mention [30] for a bijection between ternary trees and non-crossing trees (which do not preserves symmetry) and [27] in which non-crossing trees are related to Galton-Watson trees.

In [12, 11], Deutsch et al. gave a simple bijection between DDC polyominoes and even trees. They remark that this bijection preserves symmetry. They also proposed direct correspondences between symmetric ternary trees, symmetric even trees, symmetric DDC polyominoes and symmetric non-crossing trees. Moreover, they show, using Lagrange inversion, that each of these structures are counted by [omega.sub.n] defined by formula (1).

Furthermore, we can easily relate even trees with 2n + 1 vertices and dissections of some convex polygons by non intersecting diagonals into polygons with an odd number of sides having a total number of 2n + 1 edges. These dissections are called here odd dissections. Such a dissection is said to be symmetric if it possesses an axis of symmetry coinciding with the root edge mediatrix (if we draw regular convex polygons). Figure 19 shows three symmetric odd dissections for n = 4, where an edge of the convex polygon is distinguished but not oriented.

[FIGURE 19 OMITTED]

Bijection 8 (From symmetric odd dissections to symmetric even trees.)

To obtain bijectively an even tree from an odd dissection, simply place a vertex inside each component polygon. The one placed in the component polygon containing the root of the dissection will be the root of the even tree. Place also a vertex outside the dissected polygon for each non-root edge of it (near the edges). Then, join two vertices if they are on the opposite sides of an edge of the dissection. Notice that these joining lines will cross exactly one edge of the dissection; see Figure 19. If we consider now a symmetric odd dissection, then the corresponding even tree obtained by the above process is obviously a symmetric even tree. The reverse bijection is quite straightforward and details are left to the reader.

3.4 Even case

In the introduction, we noticed that [omega.sub.n], for even values of n, is a generalized Catalan number of order 3: [omega.sub.n] = c3

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

It is well known that [c.sub.3.sub.n] counts ternary trees on n vertices. Therefore, for n even, symmetric ternary trees on n vertices are in bijection with ternary trees on n/2 vertices.

Bijection 9 (From symmetric ternary trees on an even number of vertices to ternary trees.)

Let [tau] be a symmetric ternary tree on n vertices. Observe first that the main middle chain is of even length. We assume this length is k. We denote by 1 the root of [tau], by 2, 3, ..., k the successive middle children of the root and by [T.sub.i] (resp. [T'.sub.i]), the left (resp. right) subtree of vertex i, 1 [greater than or equal to] i [greater than or equal to] k; see Figure 20 (c) and (d). By symmetry, [T.sub.i] and [T'.sub.i] are isomorphic. We build a ternary tree t on n/2 vertices using the following process:

1. the length of the main middle chain of t is k=2 and its vertices are labelled 1, 2, ... k/2, starting with the root;

2. the left subtree of vertex i is [T.sub.2i-1], 1 [greater than or equal to] i [greater than or equal to] k/2;

3. the right subtree of vertex i is [T'.sub.2i-1], 1 [greater than or equal to] i [greater than or equal to] k/2.

It is quite obvious that above process is a bijection.

[FIGURE 20 OMITTED]

The above bijection is illustrated in Figure 20 (a) and (b). A counterpart of this bijection for DDC polyominoes is given in [12] (see Remark on p. 653).

4 Symmetric k-ary trees

In this section we propose a generalization of the integer sequence [{[[omega.sub.n]}.sub.n[member of]N] defined in formula (1). For this purpose, we use k-ary trees, for k [omega] N, any odd integer. A complete k-ary tree is either a single leaf or a root to which a k-tuple of complete k-ary trees is attached. A k-ary tree is obtained from a complete k-ary tree removing all its leaves.

Our first task is to enumerate symmetric k-ary trees. We use functional equations and univariate composite Lagrange inversion. Let

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (4)

be the (ordinary) generating series of (unlabelled) k-ary trees, where x marks the number of vertices. It is well known that the series T(x) satisfies the following functional equation:

T(x) = 1 + x[T.sup.k](x). (5)

A straightforward application of Lagrange inversion formula yields

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

which is a generalized Catalan number of order k; see Section 1, relation (2). Furthermore, the coefficients of the series Tm(x), m [less than or equal to] 1, are given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Let us now introduce the generating series S(x) = [summation.sub.n][member of]N [[tau].sub.n][x.sup.n] of symmetric k- ary trees. It is easy to see that this series is characterized by the relation

S(x) = 1 + x[T.sup.k-1/2]([x.sup.2])x S(x). (8)

We then deduce

S(x) = 1 / 1 - x[T.sup.k-1/2]([x.sup.2]) = T([x.sup.2]) + x[T.sup.k-1/2]([x.sup.2]).

Using relation (7), we get the number _n of symmetric k-ary trees on n vertices

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (10)

Table 1 gives the first few values of the integers [tau.sub.n] for odd integers k = 3, ..., 13 and n = 1, 2, ..., 10.

Our final goal is to generalize most of the symmetric structures previously introduced as well as the bijections linking them. This is the purpose of the following section.

5 Generalization to symmetric k-ary structures

5.1 Generalized words

We first introduce generalized words sets, denoted [W.sup.k.sub.n], where k [greater than or equal to] 3 is any odd integer and n [member of] [N.sup.*].

Definition 3 Let k [greater than or equal to] 3 be any odd integer, n a positive integer and m = k-1/2. We define [W.sup.k.sub.n] as the set of so-called k-words w satisfying the following four conditions:

1. w = [w.sub.1],[w.sub.1,2] ... [w.sub.1,m][w.sub.2,1][w.sub.2,2] ... [w.sub.2,m] ... [w.sub.n,1][w.sub.n,2] ... [w.sub.n,m] = [w.sub.1][w.sub.2] ... [w.sub.nm] is of length nm;

2. [w.sub.i] [member of] [N.sup.*], for all i = 1, 2, ..., nm;

3. [w.sub.1] = 1;

4. [w.sub.i+1] - [w.sub.i] [member of] {-(k - 1)v + 1, v [member of] N}, for all i = 1, 2, ..., nm - 1.

When k = 3 (m = 1), we obviously have [W.sup.3.sub.n] = [W.sub.n] as introduced in Section 1. It is important to note that, to form a word belonging to [W.sup.k.sub.n+1] from one of [W.sup.k.sub.n], (k - 1)/2 letters have to be appended to the word. In the case k = 3 of Section 1, only one letter is added. We give examples of the sets [W.sup.k.sub.n], for k = 5 and k = 7, for the first values of n from 1 up to 4:

[W.sup.5.sub.1] = {12}, [W.sup.5.sub.2] = {1234}, [W.sup.5.sub.3] = {123456, 123452, 123412}, [W.sup.5.sub.4] = {12345678, 12345674, 12345634, 12345234, 12341234},

and

[W.sup.7.sub.1] = {123}, [W.sup.7.sub.2] = {123456}, [W.sup.7.sub.3] = {123456789, 123456783, 123456723, 123456123g, [W.sup.7.sub.4] = {123456789 10 11 12, 123456789 10 11 6, 123456789 10 56, 123456789456, 123456783456, 123456723456, 123456123456}.

Furthermore, both bijections given in Sections 1 and 2 generalize to the k-ary case. Indeed, to obtain lattice paths from k-words, the same bijection applies. By this process, from a word belonging to the set [W.sup.k.sub.n], we get bijectively a lattice path starting at (0, 0), never passing below the x-axis with steps (1, 1) and (2, -2) of length l, where l is given by the following formula:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (11)

Furthermore, these lattice paths have the property that all descents with the possible exception of the last one have length a multiple of 4.

In a similar way, the bijection of Section 2 between symmetric ternary trees and words remains valid in the general k-ary case. Actually, this provides a correspondence between symmetric k-ary trees and the k-words introduced in Definition 3. The bijection is essentially the same and we do not present it in details. The reader can easily convice himself that one symmetric k-ary trees gives a unique k-word and vice versa. However, we illustrate the correspondence in Figure 21, in the special case k = 5. In fact, Figure 21 shows the first step of the correspondence after completion of the symmetric 5-ary tree. Encoding the tree and translating it into an integers sequence using the following cost function c:

[FIGURE 21 OMITTED]

c(x) = 1, and c(f f ... f x) = - (k - 1) x [absolute value of f] + 1, (12)

where [absolute value of f] denotes the number of occurences of the letter f in f f ... f x, we obtain the following word

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

that finally gives, after reversion and summing two by two consecutive integers starting with a 1, the 5-word

1 2 3 4 5 6 7 8 9 2 3 4 5 6 7 4 5 6 7 8 9 10 11 8 5 6 7 8 9 6.

Applying the process described in Section 1, we successively obtain the word

1 1 1 1 1 1 1 1 1 - 2 - 2 - 2 - 2 1 1 1 1 1 1 - 2 - 2 1 1 1 1 1 1 1 1 - 2 - 2 1 - 2 - 2 1 1 1 1 1 - 2 - 2 1 - 2 - 2 - 2

and the lattice path of Figure 22.

[FIGURE 22 OMITTED]

5.2 Symmetric k-ary structures

5.2.1 Cacti, 2-trees and dissections

We first list the generalized discrete k-ary structures involved in this subsection, where k [greater than or equal to] 3 is any odd integer:

* symmetric planted k-gonal solid 2-trees, that is, space embedding of k-gonal 2-trees, planted at an oriented edge and invariant under orientation reversing;

* symmetric (k + 1)-gonal outerplanar 2-trees, see Section 3.1;

* symmetric (k+1)-dissections of polygons, dissections of polygons with non-intersecting diagonals into k-sided cells, possessing an axis of symmetry;

* symmetric k-gonal plane cacti, cacti composed by k-gons embedded in the plane invariant under the reversion of the plane's orientation.

The bijections given in Section 3.1 are quite straightforward to generalize to the k-ary context, and details are left to the reader. However, Figure 23 illustrates the generalized bijections, in the special case k = 5.

[FIGURE 23 OMITTED]

5.2.2 k-ary cacti and k-ary factorizations

In Section 3.2, we have already introduced k-ary cacti and k-ary factorizations. The bijection of Bousquet [6, 3], presented for the ternary case in Section 3.2, applies also in the general k-ary case. Moreover, for any odd integer k [greater than or equal to] 3, we can see that, through this bijection, a symmetric k-ary tree of n vertices is mapped into a k-ary factorization ([[sigma].sub.1], [[sigma].sub.2], ..., [[sigma].sub.k]), where [[sigma].sub.i] [member of] [S.sub.n], for all i = 1, 2, ..., k, such that there exists an involution [pi] [member of] [S.sub.n] with [pi](1) = 1 and satisfying

[pi][[sigma].sub.i] = [[sigma].sub.k-i], for all i [member of] {1, 2, ..., (k - 1)/2},

and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Such factorizations are called symmetric k-ary factorizations. We then get the following enumerative result.

Proposition 2 Let k [greater than or equal to] 3 be any odd integer. Then, the number of symmetric k-ary factorizations ([[sigma].sub.1], [[sigma].sub.2], ..., [[sigma].sub.k]) of the n-cycle (12 ... n) is given by the integer [[tau].sub.n] defined by formula (10).

received Nov. 24, 2005, revised Feb. 18, 2008 and May 22, 2008, accepted June 11, 2008.

References

[1] L. W. Beineke and J. W. Moon. Several proofs of the number of labeled 2-dimensional trees. In Proof Techniques in Graph Theory, volume 27, pages 11-20. Academic Press, New York, 1969.

[2] Miklos Bona, Michel Bousquet, Gilbert Labelle, and Pierre Leroux. Enumeration of m-ary cacti. Adv. Appl. Math., 24(1):22-56, 2000.

[3] M. Bousquet. Quelques resultats sur les cactus planaires. Ann. Sci. Math. Quebec, 24:107-128, 2000.

[4] M. Bousquet and C. Lamathe. Enumeration of solid 2-trees. In Proceedings of the 14th conference on Formal power series and algebraic combinatorics, pages 133-147, 2002.

[5] M. Bousquet and C. Lamathe. Enumeration of solid 2-trees according to edge number and edge degree distribution. Discrete Math., 298(1-3):115-141, 2005.

[6] Michel Bousquet. Especes de structures et applications au denombrement de cartes et de cactus planaires. PhD thesis, 1999.

[7] Mireille Bousquet-Melou. Percolation models and animals. Eur. J. Comb., 17(4):343-369, 1996.

[8] M.-P. Delest and J.-M. Fedou. Exact formulas for fully diagonal compact animals. Technical Report No 89-06, LaBRI, Universite Bordeaux 1, 1989.

[9] N. Dershowitz and S. Zaks. The cycle lemma and some applications. European J. Combin., 11(2):35-40, 1990.

[10] E. Deutsch. Problem 10751. Amer. Math. Monthly, 108:872-873, November 2001.

[11] Emeric Deutsch, Svjetlan Feretic, and Marc Noy. Diagonally convex directed polyominoes and even trees: a bijection and related issues. In Publications du LaCIM, volume 27, pages 141-149. 2001.

[12] Emeric Deutsch, Svjetlan Feretic, and Marc Noy. Diagonally convex directed polyominoes and even trees: a bijection and related issues. Discrete Math., 256(3):645-654, 2002.

[13] Emeric Deutsch and Marc Noy. Statistics on non-crossing trees. Discrete Math., 254(3):75-87, 2002.

[14] Svjetlan Feretic and Dragutin Svrtan. Combinatorics of diagonally convex directed polyominoes. In Proceedings of the 6th conference on Formal power series and algebraic combinatorics, pages 147-168, Amsterdam, The Netherlands, 1996. Elsevier Science Publishers B. V.

[15] Philippe Flajolet and Marc Noy. Analytic combinatorics of non-crossing configurations. Discrete Math., 204(1-3):203-229, 1999.

[16] Tom Fowler, Ira Gessel, Gilbert Labelle, and Pierre Leroux. The specification of 2-trees. Adv. Appl. Math., 28(2):145-168, 2002.

[17] I. P. Goulden and D. M. Jackson. The combinatorial relationship between trees, cacti and certain connection coefficients for the symmetric group. Eur. J. Comb., 13(5):357-365, 1992.

[18] F. Harary and E. Palmer. Graphical Enumeration. Academic Press, New york, 1973.

[19] F. Harary, E. Palmer, and R. Read. On the cell-growth problem for arbitrary polygons. Discrete Math., 11(3):371-389, 1975.

[20] G. Labelle, C. Lamathe, and P. Leroux. Denombrement des 2-arbres k-gonaux selon la taille et le perimetre. To appear in Ann. Sci. Math. Quebec.

[21] G. Labelle, C. Lamathe, and P. Leroux. A classification of plane and planar 2-trees. Theor. Comput. Sci., 307(2):337-363, 2003.

[22] G. Labelle, C. Lamathe, and P. Leroux. Labelled and unlabelled enumeration of k-gonal 2-trees. J. Combin. Theory Ser. A, 106:193-219, 2004.

[23] Cedric Lamathe. Specification de classes de structures arborescentes. PhD thesis, 2003.

[24] Bruno Leclerc and Vladimir Makarenkov. On some relations between 2-trees and tree metrics. In Proceedings of the conference on Discrete metric spaces, pages 223-249, Amsterdam, The Netherlands, 1998. Elsevier Science Publishers B. V.

[25] P. Leroux, E. Rassart, and A. Robitaille. Enumeration of symmetry classes of convex polyominoes in the square lattice. Adv. Appl. Math., 21(3):343-380, 1998.

[26] Alberto Del Lungo, Massimo Mirolli, Renzo Pinzani, and Simone Rinaldi. A bijection for directedconvex polyominoes. In Robert Cori, Jacques Mazoyer, Michel Morvan, and Remy Mosseri, editors, Discrete Models: Combinatorics, Computation, and Geometry, DM-CCG 2001, volume AA of DMTCS Proceedings, pages 133-144. Discrete Mathematics and Theoretical Computer Science, 2001.

[27] Jean-Francois Marckert and Alois Panholzer. Noncrossing trees are almost conditioned Galton-Watson trees. Random Struct. Algorithms, 20(1):115-125, 2002.

[28] Marc Noy. Enumeration of noncrossing trees on a circle. In Proceedings of the 7th conference on Formal power series and algebraic combinatorics, pages 301-313, Essex, UK, 1998. Elsevier Science Publishers Ltd.

[29] E. Palmer and R. Read. On the number of plane 2-trees. J. London Math. Soc., 6:583-592, 1973.

[30] Alois Panholzer and Helmut Prodinger. Bijection for ternary trees and non-crossing trees. Discrete Math., 250(1-3):181-195, 2002.

[31] J.-G. Penaud. Animaux diriges diagonalement convexes et arbres ternaires. Technical Report No 90-61, LaBRI, Universite Bordeaux 1, 1990.

[32] N. J. A. Sloane. The On-Line Encyclopedia of Integer Sequences, http://www.research.att.com/njas/sequences/.

[33] L. Takacs. Enumeration of rooted trees and forests. Math. Sci., 18:1-10, 1993.

Michel Bousquet and Cedric Lamathe

LaCIM, Universite du Quebec a Montreal

Case Postale 8888, succursale Centre-ville

Montreal (Quebec) H3C 3P8
Tab. 1: Values of [[tau].sub.n] for k = 3, 5, 7, 9, 11, 13 for n from 1
up to 10.

k/n   1    2    3    4    5     6     7      8      9       10

3     1    1    2    3    7     12    30     55     143     273
5     1    1    3    5    18    35    136    285    1155    2530
7     1    1    4    7    34    70    368    819    4495    10472
9     1    1    5    9    55    117   775    1785   12350   29799
11    1    1    6    11   81    176   1406   3311   27636   68211
13    1    1    7    13   112   247   2310   5525   53998   135408
COPYRIGHT 2008 DMTCS
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2008 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Bousquet, Michel; Lamathe, Cedric
Publication:Discrete Mathematics and Theoretical Computer Science
Geographic Code:1USA
Date:Jun 1, 2008
Words:8389
Previous Article:On hereditary Helly classes of graphs.
Next Article:On the size of induced acyclic subgraphs in random digraphs.
Topics:

Terms of use | Privacy policy | Copyright © 2019 Farlex, Inc. | Feedback | For webmasters