Abstract
We define and prove isomorphisms between three combinatorial classes involving labeled trees. We also give an alternative proof by means of generating functions .
Access provided by Autonomous University of Puebla. Download conference paper PDF
Similar content being viewed by others
Keywords
1 Introduction
Based on the theory of combinatorial species (see e.g. [1]), Flajolet and Sedjewick [4] wrote a reference book on combinatorial analysis. In particular in the first part, they provided a list of basic constructions for exponential generating functions. Mainly, complex combinatorial structures are obtained by combining the following three combinatorial classes: \(\textsc {Set}, \textsc {Seq}\), and \(\textsc {Cyc}.\) For instance, they described surjections (\(\textsc {Seq}(\textsc {Set})\)), set partitions (\(\textsc {Set}(\textsc {Set})\)), alignments (\(\textsc {Seq}(\textsc {Cyc})\)) and permutations (\(\textsc {Set}(\textsc {Cyc})\)). In this article, we focus on the later one because it has the remarkable property of having the same generating function as the combinatorial class of sequences. More precisely, our starting point consists in giving an explicit bijection between the class of set-of-cycles and the class of sequences (see Sect. 3.4). Our goal is to study an example of a class defined inductively by a combinatorial class equation. We chose the equation \(\textsc {Set}(\textsc {Cyc}(\mathcal {C}))=\mathcal {C}\) because the underlying combinatorics reveal a world rich in interpretation and provide fruitful perspectives. In particular, this equation reveals an isomorphism between sets of necklaces of planar labelled trees, forests of labelled trees, and rooted labelled trees (see Sect. 4). At the heart of the equation we study here are the Catalan numbers. They are involved in the enumeration of numerous classes of combinatorial objects of prime importance in computer science, e.g. Dyck paths, binary trees, non-crossing partitions etc. [4, 5, 16]. Notice that more than 60 possible enumerations are listed in [16] and the enumerated objects lead to several applications in computer science, such as sorting techniques based on binary trees [6]. In our case, Catalan numbers are representing ordered trees. The article ends with Sect. 4.4, where we propose other recursive tree-like combinatorial classes.
2 Background and Notations
We recall here well known definitions and results concerning combinatorial classes and generating functions. The material contained in this section mainly refers to [4].
2.1 Combinatorial Classes
In the most general context, a combinatorial class is a triplet \((\mathcal {O},\mathcal {P},\omega )\) where \(\mathcal {O}\) is the discrete set of the combinatorial objects we want to enumerate, \(\mathcal {P}\) is the discrete set of the properties in regard to which you want to enumerate our objects, and \(\omega :\mathcal {O}\rightarrow \mathcal {P}\) is a map such that for every \(p\in \mathcal {P}\) the preimage \(\omega ^{-1}(p)\) is finite, which is a minimal requirement in order to be able to enumerate the objects of \(\mathcal {O}\) with respect to the properties of \(\mathcal {P}\).
We consider the restricted context where \(\mathcal {P}=\mathbb {N}\) and the preimage of 0 contains only one element. More formally, a combinatorial class is a pair \(\mathcal {C}=(\mathcal {O},\omega )\) where \(\omega : \mathcal {O} \rightarrow \mathbb {N}\) is such that \(\mathrm{card}(\omega ^{-1}(n))<\infty \) for any integer n. For the sake of simplicity, and when there is no ambiguity, we use the same name for a class and the set of its objects. Then, we denote by \(|\mu |\) the degree (or weight) \(\omega (\mu )\) of \(\mu \in \mathcal {C}\) and we set \(\mathcal {C}_n=\{\mu \in \mathcal {C}\mid \omega (\mu )=n\}\). If \(\mathrm{\#}(\omega ^{-1}(0))=1\) then we denote by \(\epsilon \) the unique element of \(\mathcal {C}\) of weight 0. We also set \(\mathcal {C}^+:=\mathcal {C}\setminus \{\epsilon \}\).
2.2 Labelled Combinatorial Classes
Recall that the symmetric group \(\mathcal {S}_n\) is the group of bijections of \(\{1,\dots ,n\}\). It is a group of order n! whose each element is denoted by the word of its images. For instance, the cycle sending 1 to 2, 2 to 3, and 3 to 1 is denoted by 231. Obviously, the set of permutations is closed by composition and all its elements are invertible.
Formally, a labelled combinatorial class is a combinatorial class endowed with a sequence \((\rho _n)_{n\in \mathbb {N}}\) of representations \(\rho _n\) of the symmetric group \(\mathcal {S}_n\) (i.e. an application associating a map \(\rho _n(\sigma ):\mathcal {C}_n\rightarrow \mathcal {C}_n\) to each permutation \(\sigma \in \mathcal {S}_n\) in such a way that \(\rho _n(\sigma \circ \sigma ')=\rho _n(\sigma )\circ \rho _n(\sigma ')\)). An equivalent way (see e.g. [4]) to define labelled combinatorial class consists in considering that each element of \(\mathcal {C}_n\) is a graph whose vertices are labelled by numbers from 1 to n; the image of a permutation by the underlying representation is just the permutation of the labels.
Let \((\mathcal {C},\omega )\) and \((\mathcal {C}',\omega ')\) be two labeled combinatorial class. If the sets \(\mathcal {C}\) and \(\mathcal {C}'\) are disjoint, then we define the class \(\mathcal {C}\boxplus \mathcal {C}'=(\mathcal {C}\cup \mathcal {C}',\omega '')\) with \(\omega ''(e)=\omega (e)\) if \(e\in \mathcal {C}\) and \(\omega (e)=\omega '(e)\) if \(e\in \mathcal {C}'\). One extends to the case where \(\mathcal {C}\cap \mathcal {C}'\ne \emptyset \) by replacing \(\mathcal {C}'\) by a copy which is disjoint of \(\mathcal {C}\) in the definition of \(\mathcal {C}\boxplus \mathcal {C}'\).
We also define \(\mathcal {C}\boxtimes \mathcal {C}'\), i.e., the combinatorial class such that the elements of \((\mathcal {C}\boxtimes \mathcal {C}')_n\) are the pairs \((e,e')\) where e is obtained by relabeling an element of \(\mathcal {C}_i\) and \(e'\) is obtained by relabeling an element of \(\mathcal {C}'_j\), with \(i+j=n\) such that the set of the labels in \((e,e')\) is \(\{1,\dots ,n\}\) and each relabeling preserves the initial order on the vertices. The degree of \((e,e')\) in \(\mathcal {C}\boxtimes \mathcal {C}'\) is the sum of the degree of the respective preimage of e and \(e'\) in \(\mathcal {C}\) and \(\mathcal {C}'\). As a special case, for each labeled class \(\mathcal {C}\), we denote \(\mathcal {C}^\bullet =\bullet \boxtimes \mathcal {C}\), where \(\bullet \) is the class of the unique element of which, denoted also by \(\bullet \), has degree 1.
2.3 The Exponential Generating Function of a Combinatorial Class
The exponential generating function (EGF) of a combinatorial class \(\mathcal {C}\) is the exponential generating function of the numbers \(C_n=\mathrm{\#}(\mathcal {C}_n),\) in other words
We say that two classes are isomorphic if their EGF are equal
Classically, we have [4]
2.4 Labelled Sequences
If \(\mathcal {C}^+\) is a labelled combinatorial class such that \(\mathcal {C}^+_0=\emptyset \) then we define, up to an equivalence, the class \(\textsc {Seq}(\mathcal {C}^+)\) of labelled sequences by the equation
where \([\ ]\) denotes the class having a single element \(\epsilon \) which is degree 0.
It is easy to show that such a class exists and that its associated exponential generating function is
From a combinatorial point of view, the elements of \(\textsc {Seq}(\mathcal {C}^+)_n\) are k-tuple \([\mu _1,\dots ,\mu _k]\) where each \(\mu _i\) is obtained by an order preserving relabelling of an element of \(\mathcal {C}_{j_i}^+\) ,in such a way that the whole set of labels in \([\mu _1,\dots ,\mu _k]\) is \(\{1,\dots ,n\}\) (as a consequence one has \(\sum _{i=1}^k j_i=n\)). So to any element \(s=[\mu _1,\dots ,\mu _k]\in \textsc {Seq}(\mathcal {C}^+)_n\) we associate an ordered partition \(\varPi =[\varPi _1,\dots ,\varPi _k]\) of size n such that each \(\varPi _i\) is the set of the labels of \(\mu _i\).
Let us be a little more precise. A labelled list of elements of \(\mathcal {C}^+\) is a list \(L=[\mu _1,\mu _2,\ldots ,\mu _k]\in \textsc {Seq}(\mathcal {C}^+)\) with each \(\mu _i\) associated to a set \(\varOmega _i\) of non-negative integers with \(\mathrm{card}(\varOmega _i)=|\mu _i|\) and \(\varOmega _i\cap \varOmega _j = \emptyset \) for all i, j. A standard labelled list of elements of \(\mathcal {C}^+\) is a labelled list L of elements of \(\mathcal {C}^+\) such that the set of all the labels of L is \(\{1,\ldots ,|L|\}\).
2.5 Labelled Sets and Labelled Cycles
We consider the labelled combinatorial classe \(\textsc {Set}(\mathcal {C}^+)\) such that \(\textsc {Set}(\mathcal {C}^+)_n\) is the quotient of the set \(\textsc {Seq}(\mathcal {C}^+)_n\) by the relation \([\mu _1,\dots ,\mu _k]\equiv _S [\mu _{\sigma (1)},\dots ,\mu _{\sigma (k)}]\) for any permutation \(\sigma \in \mathcal {S}_k\). Straightforwardly, each element of \(\textsc {Set}(\mathcal {C})\) can be represented by a set of (order preserved) relabelled elements of \(\mathcal {C}^+\). The exponential generating function
is easily deduced from the construction.
If one consider the equivalence relation generated by \([\mu _1,\dots ,\mu _k]\equiv _C [\mu _{2},\dots ,\mu _{k},\mu _1]\), the one obtains an other labelled combinatorial class \(\textsc {Cyc}(\mathcal {C}^+)\) whose elements can be represented by necklace of (order preserved) relabelled elements of \(\mathcal {C}^+\). We denote a necklace by \((\mu _1,\dots ,\mu _k)=(\mu _2,\dots ,\mu _k,\mu _1)\). Again, the generating series
is deduced from the construction.
3 Set Partitions and Related Constructions
3.1 Three Constructions Based on Set Partitions
A set partition of size n is a set \(\pi =\{\pi _1,\dots ,\pi _k\}\) such that \(\pi _1\cup \cdots \cup \pi _k=\{1,\dots ,n\}\) and \(\pi _i\cap \pi _j=\emptyset \) for any two indices \(1\le i\ne j\le k\). The set of set partitions \(\mathcal {S}_p\) endowed with the size is a combinatorial classes satisfying \( \mathcal {S}_p\equiv \textsc {Set}(\textsc {Set}(\bullet )^+) \), and so, \(S_{\mathcal {S}_p}(x)=\exp (\exp (x)-1)\). The numbers \(\mathtt Sp_n= 1, 1, 2, 5, 15, 52, 203, 877, 4140\dots \) are the well known Bell numbers (see sequence A000110 in [15]).
If \(\mathcal {C}^+\) is a labeled combinatorial class such that \(\mathcal {C}^+_0=0\) and \(\mathcal {P}\equiv \textsc {Set}(\mathcal {C}^+)\) then the definitions above allows to associate to each element \(p=\{p_1,\dots ,p_k\}\in \mathcal {P}_n\) a set partitions \(\pi (p)=\{\mathtt {labels}(p_1),\dots ,\mathtt {labels}(p_k)\}\) of size n where for each \(1\le i\le k\), \(\mathtt {labels}(p_i)\) denotes the set of the labels of \(p_i\).
An ordered partition of size n is a sequence \(\varPi =[\varPi _1,\dots ,\varPi _k]\) of non empty sets such that \(\{\varPi _1,\dots ,\varPi _k\}\) is a set partition of \(\{1,\dots ,n\}\). The set of ordered partitions \(\mathcal {O}p\) endowed with the size is a combinatorial classes satisfying \( \mathcal {O}p\equiv \textsc {Seq}(\textsc {Set}(\bullet )^+)\) and \(S_{\mathcal {O}p}(x)=\frac{1}{2-\exp (x)}\).
The numbers \(\mathtt Op_n=1, 1, 3, 13, 75, 541, 4683, 47293, 545835,\dots \) are the Fubini numbers (see sequence A000670 in [15]). If \(\mathcal {L}\equiv \textsc {Seq}(\mathcal {C}^+)\) then the definitions above allows to associate to each element \(\ell =[\ell _1,\dots ,\ell _k]\in \mathcal {L}_n\) a set partition \(\varPi (\ell )=[\mathtt {labels}(\ell _1),\dots ,\mathtt {labels}(\ell _k)]\) of size n.
A cyclic partition of size n is a necklace \(\mathfrak p=(\mathfrak p_1,\dots ,\mathfrak p_k)\) such that \(\{\mathfrak p_1,\dots ,\mathfrak p_k\}\) is a set partition of size n. The set of ordered partitions \(\mathcal {C}p\) endowed with the size is a combinatorial classes satisfying \( \mathcal {C}p\equiv \textsc {Cyc}(\textsc {Set}(\bullet )^+)\) and \(S_{\mathcal {C}p}(x)=\log (\frac{1}{2-\exp (x)})\).
The numbers \(\mathtt Cp_n=1, 1, 3, 13, 75, 541, 4683, 47293, 545835,\dots \) are listed in sequence A000670 [15]. If \(\mathcal {N}e\equiv \textsc {Cyc}(\mathcal {C}^+)\) then the above definitions allow us to associate to each element \(c=(c_1,\dots ,c_k)\in \mathcal (Ne)_n\) a cyclic partition \(\mathfrak p(c)=(\mathtt {labels}(c_1),\dots ,\mathtt {labels}(c_k))\) of size n.
3.2 An Explicit Isomorphism
From the generating series we have \(\textsc {Set}(\mathcal {C}p)\equiv \mathcal {O}p\). Indeed, this equality translates in terms of generating function as \(\exp \left( \log \left( \frac{1}{2-e^x}\right) \right) =\frac{1}{2-e^x}\). In order to understand a more general identity introduced later in the paper, we make explicit this bijection. Assume that \(c=\{c^{(1)},\dots ,c^{(k)}\}\in \textsc {Set}(\mathcal {C}p)\). If \(c^{(i)}=(c^{(i)}_1,\dots ,c^{(i)}_{h_i})\) then we consider \(\sigma _i\) the only circular permutation on the indices \(\{1,\dots ,h_i\}\) such that \(\min \bigcup _j\mathtt {labels}(c^{(i)}_{(j)})=\min \mathtt {labels}(c^{(i)}_{\sigma _i^{-1}(1)})\). In other words, if \(\ell _i=[\ell ^{(i)}_1,\dots , \ell ^{(i)}_{h_i}]=[c^{(i)}_{\sigma _i(1)},\dots ,c^{(i)}_{\sigma _i(h_i)}]\) then \(\min \bigcup _j\mathtt {labels}(\ell ^{(i)}_{(j)})=\min \mathtt {labels}(\ell ^{(i)}_{1})\). Now, consider the unique permutation \(\rho \in \mathcal {S}_k\) such that
and set
For instance,
Let \(\ell =[\ell _1,\dots ,\ell _k]\in \mathcal {O}p\) and \(1=i_0\le \dots \le i_{h-1}<i_{h}=k+1\in \{1,\dots ,k+1\}\) be the set of indices satisfying
with h maximal.
For instance, the indices associated to \([\{8,12\},\{2,5\},\{10\},\{11\},\{1,3,4\},\)\(\{7,9\},\{6\}]\) are \(1\le 2\le 5< 8\). We define
where \(c_j\) denotes the necklace \((\ell _{i_{j-1}},\dots ,\ell _{i_{j}-1})\). For instance,
It is easy to check that \(\mathtt {ltos}(\mathtt {stol}(c))=c\) and \(\mathtt {stol}(\mathtt {ltos}(\ell ))=\ell \). So we have
Proposition 1
The map \(\mathtt {stol}\) is an isomorphism of combinatorial classes and \(\mathtt {ltos}\) is its reverse map.
3.3 About Lyndon Words
Recall that the free monoid (e.g. [9]) \(\varSigma ^*\) on a set \(\varSigma \) is the monoid whose elements are all the finite sequences endowed with the catenation product \(\cdot \) that consists of pasting one sequence to the right of another. The empty sequence plays the role of the identity element. For instance, in the free monoid \(\{a,b\}^*\) we have \([a,b,a,a,b]\cdot [b,a,a]=[a,b,a,a,b,b,a,a]\). In literature, brackets and commas are often omitted; the elements of a free monoid are then noted as juxtapositions of letters called words (the empty word, noted by \(\varepsilon \), corresponds to the sequence \([\ ]\)). The name of the free monoid comes from the fact that it fulfills the universal property, that is every monoid having a generating set in bijection with \(\varSigma \) is isomorphic to a quotient of \(\varSigma ^*\).
Any pair of sequences under the form \(u\cdot v\) and \(v\cdot u\) are said conjugate. In other words, the conjugates of a sequence are all its circular shift. This is obviously an equivalence relation that preserves the periods, i.e., the conjugate sequences of \(u^{\cdot k}\) are exactly the sequences \(v^{\cdot k}\) where v is conjugate to u. In terms of combinatorial class the free monoid is nothing but \(\textsc {Seq}(\varSigma )\) and its quotient by conjugation is \(\textsc {Cyc}(\varSigma )\).
Assume that the alphabet \(\varSigma \) is totally ordered by the order <. Then the free monoid is totaly ordered with the lexicographic order \(\prec \). The minimal element for the lexicographic order is the empty sequence \([\ ]\) and we have \([a]\cdot u\prec [b]\cdot v\) if \(a<b\) or \(a=b\) and \(u\prec v\).
A Lyndon words a non periodic sequence which is minimal in its conjugacy class. Their name comes from the mathematician Roger Lyndon who studied them in 1954 [10]. Nevertheless, it should be noted that they had been introduced a year earlier by Anatoly Shirshov [14]. Lyndon words play a very important role for understanding of free groups [2], free associative algebras, and free Lie algebras [13]. Readers may refer to [11] for a rather complete survey.
Among all the properties of Lyndon’s words, one of the most interesting is that they play for the free monoid the same role as prime numbers play for integers. This property is that any sequence factorizes as a unique weakly decreasing catenation of Lyndon words [12]. In other words, the free monoid \(\varSigma ^*\) is in bijection with the multisets of aperiodic sequences over \(\sigma \). For instance, if we assume \(a<b\) the sequence \( u=[a,b,a,b,b,a,b,a,b,a,a,a,b,a,b,a]\) factorizes as \(u=[a,b,a,b,b]\cdot [a,b]\cdot [a,b]\cdot [a,a,a,b,a,b]\cdot [a]\). This means that the sequence u is assimilated to the multiset \(\{(a,a,a,b,a,b),(a,b,a,b,b),(a,b),(a,b),(a)\}\) (remark the multiplicity of (a, b)). It is interesting to note that this correspondence is precisely the one that is calculated when applying \(\mathtt {ltos}\). Indeed, let \(\ell =[\ell _1,\dots ,\ell _k]\in \mathcal {O}p\), the alphabet \(\varSigma =\{\ell _1,\dots ,\ell _k\}\) is totally ordered by \(\ell _i<\ell _j\) if and only if \(\min \ell _i<\min \ell _j\). In fact, since each numbers of \(\{1,\dots ,n\}\) appears only one time in the sequence, only the minimal elements the sets are relevant and all works as if our alphabet be \(\{1,\dots ,n\}\). For instance, \([\{8,12\},\{2,5\},\{10\},\{11\},\{1,3,4\},\{7,9\},\{6\}]\) is assimilated to [8, 2, 10, 11, 1, 7, 6]. The indices of Eq. (2), except the larger which is not relevant, indicate where to catenate in order to apply the complete factorization. In our example, we found the indices \(\{1,2,5,8\}\) and, then, we have \([8,2,10,11,1,7,6]=[8]\cdot [2,10,11]\cdot [1,7,6]\). Notice that, since the components are two by two distinct, the bijection with multisets of cycles class sends the sequences we consider on set of necklaces. For instance, \([8]\cdot [2,10,11]\cdot [1,7,6]\sim \{(1,7,6),(2,10,11),(8)\}\). We recover the \(\mathtt {ltos}(\ell )\) by replacing each integer by the set of which it is the minimum. In our example we have
Of course, this may seem like a very sophisticated way to revisit the bijection of the previous section. Nevertheless, this remark is valuable because it will allow us to link our constructions to notions of algebras (enveloping algebras, Hopf algebras, Lie algebras of primitive elements etc.) that we will explore in future works.
3.4 Set of Cycles and Sequences
Let \(\mathcal {C}^+\) be a labeled combiatorial sequences such that \(\mathcal {C}^+_0=\emptyset \). We define \( \mathcal {J}=\textsc {Set}(\textsc {Cyc}(\mathcal {C}^+))\) and \(\mathcal {S}=\textsc {Seq}(\mathcal {C}^+)\).
Let us show that the map \(\mathtt {stol}\) allows us to compute an explicit isomorphism from \(\mathcal {J}\) to \(\mathcal {S}\). We define \(\mathtt {jtoset}_{\mathcal {C}^+}:\mathcal {J}\rightarrow \textsc {Set}(\mathcal {C}p) \) by
We define also \(\mathtt {jtoseq}_{\mathcal {C}^+}:\mathcal {J}\rightarrow \mathcal {S}\) such that
is the unique permutation of the vector \([c^{(1)}_1,\dots ,c^{(1)}_{h_1},\cdots ,c^{(k)}_1,\dots ,c^{(k)}_{h_k}]\) such that \(\varPi (\ell )=\mathtt {stol}(\mathtt {jtoset}_{\mathcal {C}^+}((\{(c^{(1)}_1,\dots ,c^{(1)}_{h_1}),\cdots ,(c^{(k)}_1,\dots ,c^{(k)}_{h_k})\})))\).
Let \(c=\{(c_1^{(1)},c_2^{(1)}),(c_1^{(2)}),(c_1^{(3)},c_2^{(3)})\}\) be a set of labelled graphs as shown in Fig. 1.
Then \(\mathtt {jtoset}_{\mathcal {C^+}}(c)\) equals
Furthermore, \(\varPi (l)=\mathtt {stol}\left( \mathtt {jtoset}_{\mathcal {C^+}}(c)\right) =\)
Since \(\mathtt {stol}\) is one to one, the equality on generating functions allows us to deduce that \(\mathtt {jtoseq}_{\mathcal {C}^+}\) is an isomorphism of combinatorial classes. The inverse bijection \(\mathtt {seqtoj}_{\mathcal {C}^+}:\textsc {Set}(\mathcal {C}p)\rightarrow \mathcal {J}\) is defined by
where \([c^{(1)}_1,\dots ,c^{(1)}_{h_1},\cdots ,c^{(k)}_1,\dots ,c^{(k)}_{h_k}]\) is the unique permutation of \(\ell \) such that \(\mathtt {ltos}(\varPi (\ell ))=\mathtt {jtoset}_{\mathcal {C}^+}(\{(c^{(1)}_1,\dots ,c^{(1)}_{h_1}),\cdots ,(c^{(k)}_1,\dots ,c^{(k)}_{h_k})\})\).
In the aforementioned example, we deduce the indices of the minimum elements in \(\varPi (l)\) being \(1<3<5\). Hence, \(\mathtt {ltos}(\varPi (l))=\)
We summarize the results of this section in the following theorem.
Theorem 1
The maps which make commuting the following diagram are explicit isomorphisms of combinatorial classes
4 Labelled and Unlabelled Trees
We illustrate the previous result by investigating the combinatorial classes \(\mathcal {R}\) satisfying
This isomorphism can be translated into the following functional equation:
This equation has a unique solution
which is also the ordinary generating function of the Catalan numbers \(\mathtt C_n=\frac{1}{n+1}\left( 2n\atop n\right) \) [4, 16]. Hence, \(\mathcal {R}\) is unique up to an isomorphism and
The sequence of \(R_n\) is
4.1 Labelled Trees from Unlabelled Trees
Definition 1
A tree is a list of trees (possibly empty) connected to a node, called its root, by an edge (also called branch). Notice that this is a valid recursive definition which base case is a root together with an empty list. The degree \(\omega (t)\) of a tree t is the number of its edges or, equivalently the number of its nodes which are not its root.
Let \(\mathcal {D}\) be the set of trees. There are a finite number of trees having a given degree, so the pair \((\mathcal {D},\omega )\) is a (unlabelled) combinatorial class. The number \(D_n\) is known to be the Catalan number \(\mathtt C_n\) (see e.g. [16]). So the ordinary generating function of the class \(\mathcal {D}\), i.e.,
fulfills the same functional equation (6) as the exponential generating function of \(\mathcal {R}\). So each \(\mathcal {R}_n\) is in one to one correspondence with \(\mathcal {D}_n\times \mathcal {S}_n\). This suggests that one can exhibit an explicit realization of the class \(\mathcal {R}\) by labeling the nodes which are not the root of each tree \(t\in \mathcal {D}\) by \(\{1,\dots ,\omega (t)\}\), without repetition and in any possible way.
4.2 Shifted Structure
The class \(\mathcal {R}^\bullet \) is isomorphic to the class \(\mathcal {R}_r\) of trees with labeled root endowed with the weight \(\omega _r\) counting the total number of nodes, including the root. More precisely, for a given n, a tree of \((\mathcal {R}_r)_{n+1}\) is obtained by labelling the root of a tree in \(\mathcal {R}_n\) with any of the possible value from the set \(\{1,\dots ,n+1\}\) and relabel, if necessary, the nodes with respect to the order induced by the initial permutation.
Example 1
Let t be a rooted labelled tree in \(\mathcal {R}_5\), and its associated permutation is \(\pi =(1,2,4,5,3)\). Then the set of all rooted labeled trees where the root is labeled obtained from t is given by the set of permutations \(\{(6,1,2,4,5,3),(5,1,2,4,6,3),(4,1,2,5,6,3),(3,1,2,5,6,4),(2,1,3,5,6,4),(1,2,3,5,6,4)\}.\)
In terms of generating function, this operation leads to
and so
for any \(n\ge 1.\) The sequence of \({R_r}_n\) is given by
We insists on the fact that at this point \({(\mathcal {R}_r)}_n\) counts trees having n nodes including the root.
4.3 Hanging Trees in Necklaces
A labelled necklace of planar trees is a necklaces on which trees are hung and all the nodes (comprising the roots) are labeled by \(\{1,\dots ,n\}\) where n is the total numbers of nodes (comprising roots). We denote by \(\mathcal {N}\) the set of such necklaces. The cyclic structure comes from the fact that a necklace is invariant by rotation. The weight \(\omega _N(\mathtt n)\) of a necklace \(\mathtt n\) is the total number of the nodes, comprising roots, of the trees it contains. The pair \((\mathcal {N},\omega _N)\) is a labeled combinatorial class that satisfies
We depict in Fig. 2 elements of \(\mathcal {N}\) that are equivalent under cyclic rotation.
Notices that Labeled necklaces of rooted trees appear under the name of “planar labelled trees” in the work of Miloudi [8]. To be more precise, he studied combinatorial class which is straightforwardly isomorphic to \(\mathcal {N}\) and he proved \(N_n=(2n-3)!/(n-1)!\) for any \(n\ge 2\) and \(N_1=1.\) We recover this result from the interpretation of (10) in terms of generating function. Indeed,
Hence,
and the exact formula for \(N_n\) is obtained by expanding the function as a Taylor series.
These numbers are also mentioned by Wolfdieter Lang in [15], see the sequence below
-
1, 1, 3, 20, 210, 3024, 55440, 1235520, 32432400 A006963.
We now have all the material to make explicit the isomorphisms suggested by (5). To this aim we consider jewellery boxes which are sets of necklaces and forests which are sequences of trees. More formally, in terms of combinatorial classes we define \(\mathcal {J}=\textsc {Set}(\mathcal {N})\) and \(\mathcal {F}=\textsc {Seq}(\mathcal {R}^\bullet )\). Let \(\mathtt {jtof}=\mathtt {jtoseq}_{\mathcal {R}^\bullet }:\mathcal {J}\rightarrow \mathcal {F}\) and its inverse bijection \(\mathtt {ftoj}=\mathtt {seqtoj}_{\mathcal {R}^\bullet }:\mathcal {F}\rightarrow \mathcal {J}\). An explicit isomorphism \(\mathtt {rtof}:\mathcal {R}\rightarrow \mathcal {F}\) is obtained by removing the root to any tree in \(\mathcal {R}\). The reciprocal isomorphism \(\mathtt {ftor}:\mathcal {F}\rightarrow \mathcal {R}\) consists in connecting all the trees of a given sequence to an additional node called the root.
All these constructions are summarized in the following result which is a corollary of Theorem 1.
Corollary 1
The maps which make commuting the following diagram are explicit isomorphisms of combinatorial classes
In Fig. 3 we illustrate the bijections from (12) using two examples.
4.4 Other Recursive Tree-Like Combinatorial Classes
The tree-like structure constructed from sequences is the most rigid one. It involves rooted trees that are embedded in a plan in such a way that the branches are always pointing downwards and so, the order of the sequences of the subtrees is relevant. If we relax the constraint of the orientation of the branches then the trees become invariant by rotation. In that context, a tree is a non-oriented graph without cycle with a privileged vertex called a root. Each root can be seen as a labeled necklace on which the subtrees are hanged, forming a sort of windmill (see Fig. 4 for examples). In other words, a tree is either an isolated root or a root with a cycle of trees. The combinatorial class satisfies the isomorphism
and its generating function satisfies
Expanding both sides of the equation and identifying the coefficients, we get a system, the resolution of which allows us to obtain the first cases of the enumeration:
This is another example of a tree-like structure studied among others in [1]. Notice that no closed form for the generating function is known but there exists a formula for the coefficients as a combination of Stirling numbers of first kind,
where \(s_{n,i}\) denotes the (unsigned) Stirling number of first kind that counts the number of permutations of n objects with exactly i cycles. Indeed, from (14), \(S_{\mathcal {W}}(x)\) is the inverse of \(g(x)={x\over 1-\log (1-x)}\) for the composition. The Lagrange inversion theorem [7] is a classical combinatorial tools allowing us to compute the Taylor expansion of inverse function. In our case, the direct application of the Lagrange inversion Theorem implies that
is the coefficient of \(x^{n-1}\) in \(\left( 1-\log \left( 1\over 1-x\right) \right) ^n\) multiplied by \((n-1)!\). Knowing that the exponential generating function of Stirling’s numbers \(s_{i,k}\) (k fixed) is \(\frac{1}{k}!\log \left( \frac{1}{1-x}\right) ^k=\sum _{i}s_{i,k}{x^i\over i!}\), an easy computation allows us to deduce (15) from (16).
The last example we consider is the one where no more order constraints are imposed on the sub-trees of the same node. In this context, a tree is a root with a (possibly empty) set of trees. The trees of this kind can be drawn as nesting of disjointed discs with numbered surfaces (see some examples in Fig. 5). Notice that, in these examples nested disk configurations, of degree 3 are as numerous as the windmills of degree 3 (see Fig. 4). Of course, this is not always the case and generally, there are fewer nested discs configurations than windmills. For instance, there are two windmills of degree 4 the roots of which is labeled by 1 with three sub-windmills of degree 1 while there is only one nested discs configuration the root of which is labeled by 1 containing three discs (see Fig. 6).
The combinatorial class satisfies the isomorphism
and its generating series satisfies the functional equation
Solving these equation, one finds
where W(x) denotes the Lambert W function that is the principal branch of the functional inverse of \(x\rightarrow xe^x\) [3]. The Taylor expansion of W(x) is obtained by applying Lagrange inversion Theorem and implies \(Npt_n=n^{n-1}\). The sequence of the \(Npt_n\)’s can also be found in [15]:
-
1, 2, 9, 64, 625, 7776, 117649, 2097152,... A000169.
References
Bergeron, F., Labelle, G., Leroux, P.: Combinatorial Species and Tree-like Structures. Encyclopedia of Mathematics and its Applications. Cambridge University Press, Cambridge (1997)
Chen, K.T., Fox, R.H., Lyndon, R.C.: Free differential calculus, iv. the quotient groups of the lower central series. Ann. Math. 68(1), 81–95 (1958)
Corless, R.M., Gonnet, G.H., Hare, D.E.G., Jeffrey, D.J., Knuth, D.E.: On the lambertW function. Adv. Comput. Math. 5(1), 329–359 (1996)
Flajolet, P., Sedgewick, R.: Analytic Combinatorics, 1st edn. Cambridge University Press, New York (2009)
Hivert, F., Novelli, J.-C., Thibon, J.-Y.: The algebra of binary search trees. Theor. Comput. Sci. 339(1), 129–165 (2005). Combinatorics on Words
Knuth, D.E.: The Art of Computer Programming. Sorting and Searching, vol. 3, 2nd edn. Addison Wesley Longman Publishing Co. Inc., Boston (1998)
Lagrange, J.-L.: Nouvelle méthode pour résoudre les équations littérales par le moyen des séries. Mémoires de l’Académie Royale des Sciences et Belles-Lettres de Berlin 24, 251–326 (1770)
Leroux, P., Miloudi, B.: Généralisations de la formule d’otter. Annales des sciences mathématiques du Québec 16(1), 53–80 (1992)
Lothaire, M.: Combinatorics on Words. Cambridge Mathematical Library, 2nd edn. Cambridge University Press, Cambridge (1997)
Lyndon, R.C.: On burnside’s problem. Trans. Am. Math. Soc. 77(2), 202–215 (1954)
Reutenauer, C.: Free Lie Algebras. Handbook of Algebra, vol. 3. North-Holland, Amsterdam (2003)
Schützenberger, M.P.: On a factorisation of free monoids. Proc. Am. Math. So. 16, 02 (1965)
Shirshov, A.: On free lie rings. Mat. Sb. 45, 77–87 (2009)
Shirshov, A.: Subalgebras of free lie algebras. Algebra and Logic 11, 3–13 (2009)
Sloane, N.J.A.: Oeis Foundation Inc., The On-line Encyclopedia of Integer Sequences. http://oeis.org/
Stanley, R.P.: Catalan Numbers. Cambridge University Press, Cambridge (2015)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG
About this paper
Cite this paper
Chouria, A., Drăgoi, VF., Luque, JG. (2021). On Recursively Defined Combinatorial Classes and Labelled Trees. In: Dzitac, I., Dzitac, S., Filip, F., Kacprzyk, J., Manolescu, MJ., Oros, H. (eds) Intelligent Methods in Computing, Communications and Control. ICCCC 2020. Advances in Intelligent Systems and Computing, vol 1243. Springer, Cham. https://doi.org/10.1007/978-3-030-53651-0_2
Download citation
DOI: https://doi.org/10.1007/978-3-030-53651-0_2
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-53650-3
Online ISBN: 978-3-030-53651-0
eBook Packages: EngineeringEngineering (R0)