The enumeration of noncrossing trees has attracted significant attention since the turn of 21st century. These trees have been studied with respect to various statistics, including the number of vertices, leaves, root degree, and levels. In contrast, plane trees have a longer history of exploration. In 2010, Deutsch and his co-authors introduced and enumerated a class of plane trees in which a rightmost edge may be marked, provided it does not lead to a leaf. Their enumeration formula involved the Catalan numbers, which also count plane trees. In this work, we extend the concept of marking rightmost edges to noncrossing trees, introducing a new combinatorial structure. We enumerate this structure according to the number of edges, marked edges, root degree, and leaves. We use symbolic method and Lagrange Inversion Formula to derive our results. Furthermore, we establish connections between these new structures and both labelled plane trees and ternary trees.
Consider \(n\) points labelled counterclockwise from \(1\) to \(n\) on a circle. A noncrossing tree is a tree whose vertices are these points and whose edges do not intersect when drawn inside the circle. Marc Noy introduced and enumerated such trees in [5], where he also coined the term noncrossing trees. Interestingly, the formula that counts noncrossing trees turns out to be a generalization of the Catalan numbers. The classical Catalan numbers are known to enumerate a wide variety of combinatorial structures, including plane trees, binary trees, and Dyck paths [12, A000108]. In 2002, Panholzer and Prodinger [10] introduced a representation of noncrossing trees as plane trees, now commonly referred to as the \((l,r)\)-representation. In this representation, the root of the noncrossing tree (vertex 1) becomes the root of the plane tree. For any edge from a parent vertex to a child vertex, if the parent has a smaller label than the child then the child is assigned label \(r\); otherwise, it is assigned label \(l\). Figure 1 illustrates an example of a noncrossing tree alongside its corresponding \((l,r)\)-representation.
In any plane tree (a noncrossing tree is a labelled plane tree by this representation), a vertex \(i\) that is adjacent to another vertex \(j\) but appears on a lower level is a child of \(j\). The number of children of \(j\) is the degree of \(j.\) A vertex of degree \(0\) is a leaf. The length of the longest path from the root to the leaf is the height of the tree. A forest is a collection of trees. Noncrossing trees have been enumerated by root degree [2], leaves, forests, degree sequence [3] etc.
In 1999, Flajolet and Noy [3] introduced the notion of a butterfly of noncrossing trees. A butterfly consists of two noncrossing trees sharing a common root, with each tree referred to as a wing of the butterfly. The two wings are distinguished as the left wing and the right wing, either of which may be empty. In the \((l,r)\)-representation, vertices labelled \(l\) (respectively, \(r\)) belong to the left (respectively, right) wing. Equivalently, a butterfly is obtained by identifying the roots of two noncrossing trees and taking the resulting vertex as the root of the butterfly. Consequently, if \(N(x)\) denotes the generating function for noncrossing trees, where \(x\) marks vertices, then the generating function for butterflies is \(N(x)^2/x.\) Indeed, the factor \(N(x)^2\) counts ordered pairs of noncrossing trees, while the division by \(x\) accounts for the identification of their roots. Since the two roots merge into a single vertex in the butterfly, the total number of vertices is reduced by one.
In 2010, Deutsch, Munarini and Rinaldi [1] introduced and enumerated plane trees in which a rightmost edge may be marked if it does not lead to a leaf. They called these trees as marked plane trees. The aforementioned authors showed that the number of marked plane trees on \(n\) vertices is given by
Therefore, this formula involves Catalan number which also counts plane trees. The authors showed that the same formula counts skew Dyck paths of semilength \(n-1,\) hex trees on \(n\) vertices and 3-Motzkin paths of length \(n.\) The formula has since been refined to enumerate the trees by number of marked edges [1], leaves and height [11]. In [11], Prodinger showed that (1) gives the number of weighted unary-binary trees, plane trees with multiple edges, ternary trees with given number of middle edges among other structures. A generalization of (1) was subsequently obtained by Nyariaro, Okoth and Nyamwala [6].
We now introduce the objects of our investigation. A marked noncrossing tree is a noncrossing tree whose \((l,r)\)-representation is a rooted plane tree in which, for each internal vertex, the edge to its rightmost child in a wing may be marked if and only if that child is not a leaf. In Figure 2, we get a depiction of a marked noncrossing tree on 20 vertices.
The sequence that enumerates marked noncrossing trees is \(1,5,29, 186,\ldots\). The first term corresponds to a tree with 2 vertices. In Figure 3, we display all the 29 marked noncrossing trees on 4 vertices.
A one-vertex tree is regarded as a marked noncrossing tree. Let \(N=N(x)\) denote the generating function for marked noncrossing trees, where \(x\) marks vertices. Let \(y(x)\) denote the generating function for marked noncrossing trees with at least two vertices. Then the decomposition according to the size of the tree yields \[N = x + x y.\]
Here, the term \(x\) accounts for the single-vertex tree, while \(xy\) accounts for marked noncrossing trees with at least two vertices, where the factor \(x\) marks the root vertex and \(y\) records the remaining structure.
In this work, we use the following version of the Lagrange inversion formula to extract coefficients from generating functions.
Theorem 1.1 (Lagrange Inversion Formula, [13]). Let \(y\) be a generating function defined implicitly by the functional equation \[y = x \Phi(y),\] where \(\Phi(0) \neq 0\). Then, for integers \(a \ge 1\) and \(n \ge a\), the coefficient extraction is given by \[[x^n]\, y^a = \frac{a}{n} [t^{\,n-a}] \Phi(t)^n.\]
The following identities, which are standard results in elementary combinatorics, play a key role in the derivation of our results.
Identity 1.2 (Vandermonde Convolution). Let \(n\), \(m\), and \(k\) be nonnegative integers. Then \[\sum_{a=0}^k {n \choose a}{m \choose k-a} = {n+m \choose k}.\]
Identity 1.3 (Binomial Theorem). Let \(x\) and \(y\) be variables. Then, for a nonnegative integer \(n\), we have \[(x+y)^n = \sum_{a=0}^n {n \choose a} x^{\,n-a} y^a.\]
Throughout this paper, we adopt the convention that \[{m \choose k} = 0 \quad \text{if } k > m, \quad \text{and } {0 \choose 0} = 1.\]
While noncrossing trees and marked plane trees have been enumerated with respect to numerous combinatorial parameters, the enumeration of noncrossing trees with distinguished marked edges remains largely unexplored. Incorporating edge markings into noncrossing trees gives rise to new combinatorial structures and leads to several interesting counting formulas.
This paper is organized as follows. In Section 2, we derive closed-form formulas for the number of marked noncrossing trees according to the number of vertices, marked edges, root degree, and leaves. Section 3 extends the study to two combinatorial structures naturally associated with marked noncrossing trees. Finally, Section 4 concludes the paper with a summary of the main results and a discussion of several directions for future research. The results obtained contribute new enumeration formulas to the theory of noncrossing trees and broaden the scope of tree enumeration.
A marked noncrossing tree in its \((l,r)\)-representation is composed of a root vertex and a sequence of butterflies rooted at the children of the root. Allowing the edge incident with the rightmost child in a wing of a butterfly to be marked leads to the symbolic specification shown in Figure 4, where \(\mathcal{N}\) denotes the class of marked noncrossing trees and \(\mathcal{B}\) denotes the class of butterflies associated with marked noncrossing trees.
Let \(N=N(x)\) and \(B=B(x)\) be the generating functions for marked noncrossing trees and butterflies of marked noncrossing trees, respectively, where \(x\) marks vertices. The symbolic specification translates into
where \[B=\frac{N(x)^2}{x}.\]
In the unmarked case, the term \(x/(1-B)\) corresponds to a root vertex marked by \(x\), together with a (possibly empty) sequence of butterflies attached to the children of the root, accounted for by \(1/(1-B)\).
In the marked case, the factor \(B-x\) accounts for the presence of a butterfly rooted at the rightmost child of the root, which is incident to the distinguished marked edge. The subtraction of \(x\) excludes the degenerate butterfly consisting of a single vertex, since an edge incident to a leaf cannot be marked.
Substituting \(B=N(x)^2/x\) into (2) yields
Let \(N(x)=x+xy\) so that Eq. (3) becomes
or
upon simplification. We now proceed to extract the coefficient of \(x^n\) in \(N(x)\) by means of Lagrange Inversion Formula and Eq. (5): \[\begin{aligned} {}[x^n]N(x)&=[x^{n-1}]y\\&=\dfrac{1}{n-1}[t^{n-2}]((1+t)^3+t(t+2))^{n-1}\\ &=\dfrac{1}{n-1}[t^{n-2}]\sum_{i\geq 0}{n-1\choose i}(1+t)^{3i}(t+2)^{n-i-1}t^{n-i-1}\\ &=\dfrac{1}{n-1}[t^{n-2}]\sum_{i,j,k\geq 0}{n-1\choose i}{3i\choose j}{n-i-1\choose k}2^{n-i-k-1}t^{n-i+j+k-1}\\ &=\dfrac{1}{n-1}\sum_{i,k\geq 0}{n-1\choose i}{3i\choose i-k-1}{n-i-1\choose k}2^{n-i-k-1}. \end{aligned}\]
We announce the result of the discussions above as a theorem.
Theorem 2.1. The number of marked noncrossing trees on \(n\geq 2\) vertices is given by
We first observe that Eq. (4) can be expressed as \(y=x((1+y)^2(2+y)-1)\). Applying Lagrange inversion formula, we obtain: \[\begin{aligned} {}[x^n]N(x)&=[x^{n-1}]y\\&=\dfrac{1}{n-1}[t^{n-2}]((1+t)^2(2+t)-1)^{n-1}\\ &=\dfrac{1}{n-1}[t^{n-2}]\sum_{i\geq 0}{n-1\choose i}(1+t)^{2i}(2+t)^{i}(-1)^{n-i-1}\\ &=\dfrac{1}{n-1}[t^{n-2}]\sum_{i,j,k\geq 0}{n-1\choose i}{2i\choose j}{i\choose k}(-1)^{n-i-1}2^{i-k}t^{j+k}\\ &=\dfrac{1}{n-1}\sum_{i=0}^{n-1}\sum_{k=0}^{i}{n-1\choose i}{2i\choose n-k-2}{i\choose k}(-1)^{n-i-1}2^{i-k} \end{aligned}\]
Therefore, the number of trees described in Theorem 2.1 can also be given as \[\begin{aligned} \dfrac{1}{n-1}\sum_{i=0}^{n-1}\sum_{k=0}^{i}{n-1\choose i}{2i\choose n-k-2}{i\choose k}(-1)^{n-i-1}2^{i-k}. \end{aligned}\]
By rewriting (5) as \(y=x((1+y)^3+y(1+(1+y)))\) and extracting the coefficient of \(x^{n-1}\) in \(y\), we find that (6) can also expressed as \[\begin{aligned} \dfrac{1}{n-1}\sum_{i=1}^{n-1}\sum_{k=0}^{n-i-1}{n-1\choose i}{3i+k\choose i-1}{n-i-1\choose k}. \end{aligned}\] That is, \[\begin{aligned} {}[x^n]N(x)&=[x^{n-1}]y\\&=\dfrac{1}{n-1}[t^{n-2}]((1+t)^3+t(1+(1+t)))^{n-1}\\ &=\dfrac{1}{n-1}[t^{n-2}]\sum_{i\geq 0}{n-1\choose i}(1+t)^{3i}(1+(1+t))^{n-i-1}t^{n-i-1}\\ &=\dfrac{1}{n-1}[t^{n-2}]\sum_{i,k\geq 0}{n-1\choose i}{n-i-1\choose k}(1+t)^{3i+k}t^{n-i-1}\\ &=\dfrac{1}{n-1}[t^{n-2}]\sum_{i,j,k\geq 0}{n-1\choose i}{n-i-1\choose k}{3i+k\choose j}t^{n+j-i-1}\\ &=\dfrac{1}{n-1}\sum_{i=1}^{n-1}\sum_{k=0}^{n-i-1}{n-1\choose i}{3i+k\choose i-1}{n-i-1\choose k}. \end{aligned}\]
Also expanding the right hand side of (4) and collecting the like terms, we obtain \(y=x(1+5y+4y^2+y^3).\) So, \[\begin{aligned} {}[x^n]N(x)&=[x^{n-1}]y\\&=\dfrac{1}{n-1}[t^{n-2}](1+5t+4t^2+t^3)^{n-1}\\ &=\dfrac{1}{n-1}[t^{n-2}]\sum_{i\geq 0}{n-1\choose i}(5+4t+t^2)^it^i\\ &=\dfrac{1}{n-1}[t^{n-2}]\sum_{i,k\geq 0}{n-1\choose i}{i\choose k}5^{i-k}t^{i+k}(4+t)^k\\ &=\dfrac{1}{n-1}[t^{n-2}]\sum_{i,j,k\geq 0}{n-1\choose i}{i\choose k}{k\choose j}4^{k-j}\cdot 5^{i-k}t^{i+k+j}\\ &=\dfrac{1}{n-1}\sum_{i,k\geq 0}{n-1\choose i}{i\choose k}{k\choose n-i-k-2}4^{2k+i+2-n}\cdot 5^{i-k}. \end{aligned}\]
This reveals that (6) is the same as \[\begin{aligned} \dfrac{1}{n-1}\sum_{i=0}^{n-1}\sum_{k=0}^{i}{n-1\choose i}{i\choose k}{k\choose n-i-k-2}4^{2k+i+2-n}\cdot 5^{i-k}. \end{aligned}\]
The equation \(y=x(1+5y+4y^2+y^3)\) can be rewritten as \(y=x((1+5y)+y^2(4+y))\). So, \[\begin{aligned} {}[x^n]N(x)&=[x^{n-1}]y\\&=\dfrac{1}{n-1}[t^{n-2}]((1+5t)+t^2(4+t))^{n-1}\\ &=\dfrac{1}{n-1}[t^{n-2}]\sum_{i\geq 0}{n-1\choose i}(1+5t)^{n-i-1}t^{2i}(4+t)^{i}\\ &=\dfrac{1}{n-1}[t^{n-2}]\sum_{i,j,k\geq 0}{n-1\choose i}{i\choose j}{n-i-1\choose k}4^{i-j}\cdot 5^kt^{2i+j+k}\\ &=\dfrac{1}{n-1}\sum_{i,k\geq 0}{n-1\choose i}{i\choose n-2i-k-2}{n-i-1\choose k}4^{3i+k+2-n}\cdot 5^k. \end{aligned}\]
Thus, \[\begin{aligned} \dfrac{1}{n-1}\sum_{i=0}^{n-1}\sum_{k=0}^{n-2i-2}{n-1\choose i}{i\choose n-2i-k-2}{n-i-1\choose k}4^{3i+k+2-n}\cdot 5^{k}, \end{aligned}\] is also another form of (6). The sequence counting marked noncrossing trees is thus \(1,5,29,186,\ldots.\) This sequence is not listed in the Online Encyclopedia of Integer Sequences [12]. The result therefore contributes a new sequence and combinatorial interpretation to the theory of tree enumeration.
We prove the following theorem:
Theorem 2.2. There are
marked noncrossing trees on \(n\geq 2\) vertices with \(m\geq 0\) marked edges.
Proof. Let \(N(x,e)\) be the bivariate generating function for marked noncrossing trees where \(x\) and \(e\) mark vertex and marked edge respectively. Then \[\begin{aligned} N(x,e)=\dfrac{x}{1-\frac{N(x,e)^2}{x}}+\dfrac{xe(\frac{N(x,e)^2}{x}-x)}{1-\frac{N(x,e)^2}{x}}. \end{aligned}\]
This equation reduces to \[\begin{aligned} xN(x,e)=N(x,e)^3+exN(x,e)^2+x^2-ex^3. \end{aligned}\]
As before, let \(N=x+xy.\) Then the bivariate generating function can be written as \[\begin{aligned} y=x((1+y)^3+ey(2+y)). \end{aligned}\]
The required formula is the coefficient of \(x^ne^m\) in the generating function which we now obtain using Lagrange inversion: \[\begin{aligned} {}[x^ne^m]N(x,e)&=[x^{n-1}e^m]y=\dfrac{1}{n-1}[t^{n-2}e^m]((1+t)^3+et(t+2))^{n-1}\\ &=\dfrac{1}{n-1}[t^{n-2}e^m]\sum_{i\geq 0}{n-1\choose i}(1+t)^{3i}(t+2)^{n-i-1}t^{n-i-1}e^{n-i-1}\\ &=\dfrac{1}{n-1}{n-1\choose m}[t^{n-2}][(1+t)^{3(n-m-1)}(t+2)^{m}t^{m}]\\ &=\dfrac{1}{n-1}{n-1\choose m}[t^{n-2}]\sum_{j,k\geq 0}{3(n-m-1)\choose j}{m\choose k}2^{m-k}t^{m+j+k}\\ &=\dfrac{1}{n-1}{n-1\choose m}\sum_{k=0}^{m}{3(n-m-1)\choose n-k-m-2}{m\choose k}2^{m-k}. \end{aligned}\]
This completes the proof.
Table 1 lists the number of marked noncrossing trees on \(2 \leq n \leq 6\) vertices, classified by the number of marked edges. In the case \(n=4\), these counts can be directly confirmed from Figure 3.
| \(n \backslash m\) | 0 | 1 | 2 | 3 | 4 | Total |
|---|---|---|---|---|---|---|
| 2 | 1 | 1 | ||||
| 3 | 3 | 2 | 5 | |||
| 4 | 12 | 13 | 4 | 29 | ||
| 5 | 55 | 81 | 42 | 8 | 186 | |
| 6 | 273 | 506 | 362 | 120 | 16 | 1277 |
Corollary 2.3. The number of noncrossing trees on \(n\geq 2\) vertices is given by \[\begin{aligned} \dfrac{1}{n-1}{3n-3\choose n-2}. \end{aligned}\]
Proof. Set \(m=0\) in (7).
In the sequel, we find a formula for the number of marked noncrossing trees with a given root degree, number of marked edges and number of vertices.
Theorem 2.4. The number of marked noncrossing trees on \(n\geq 2\) vertices with root degree \(n-1\) (with no marked edge) is 1 and for root degree \(d\neq n-1\) and \(m\geq 0\) marked edges, the number is
where \[\begin{aligned} N_{n,m,d}=\dfrac{d}{n-d-1}{n-d-1\choose m}\sum_{k=0}^m{3n-3m-d-4\choose n-d-m-k-2}{m\choose k}2^{m-k+1}. \end{aligned}\]
Proof. Let \(N(x,e)\) be the bivariate generating function for marked noncrossing trees with \(x\) and \(e\) marking vertices and marked edges respectively. Then the generating function satisfies the functional equation \[\begin{aligned} N(x,e)=\dfrac{x}{1-\frac{N(x,e)^2}{x}}+\dfrac{ex\left(\frac{N(x,e)^2}{x}-x\right)}{1-\frac{N(x,e)^2}{x}}. \end{aligned}\] We have \[\begin{aligned} N(x,e)=&x\left(1+\frac{N(x,e)^2}{x}+\left(\frac{N(x,e)^2}{x}\right)^2+\cdots\right)\\&+ex\left(\frac{N(x,e)^2}{x}-x\right)\left(1+\frac{N(x,e)^2}{x}+\left(\frac{N(x,e)^2}{x}\right)^2+\cdots\right)\\ =&(x-ex^2)\left(1+\frac{N(x,e)^2}{x}+\left(\frac{N(x,e)^2}{x}\right)^2+\cdots\right)\\&+xe\left(\frac{N(x,e)^2}{x}+\left(\frac{N(x,e)^2}{x}\right)^2+\cdots\right), \end{aligned}\] which reduces to \[\begin{aligned} N(x,e)=&(x-ex^2)+(1+e)x\left(\frac{N(x,e)^2}{x}+\left(\frac{N(x,e)^2}{x}\right)^2+\cdots\right)\\&-ex^2\left(\frac{N(x,e)^2}{x}+\left(\frac{N(x,e)^2}{x}\right)^2+\cdots\right). \end{aligned}\]
The required equation is therefore the coefficient of \(x^ne^m\) in \[(1+e)x\left(\frac{N(x,e)^2}{x}\right)^d-ex^2\left(\frac{N(x,e)^2}{x}\right)^{d-1}.\] We have \[\begin{aligned} {}[x^ne^m]x(N(x,e)^2/x)^d&=[x^{n+d-1}]N(x,e)^{2d}\\&=[x^{n-d-1}e^m](1+y)^{2d}\sum_{a\geq 0}{2d\choose a}[x^{n-d-1}e^m]y^a\\ &=\sum_{a\geq 0}{2d\choose a}\dfrac{a}{n-d-1}[t^{n-d-a-1}e^m]((1+t)^3+et(t+2))^{n-d-1}. \end{aligned}\]
Binomial theorem gives \[\begin{aligned} &[x^ne^m]x(N(x,e)^2/x)^d\\&=\sum_{a\geq 0}{2d\choose a}\dfrac{a}{n-d-1}[t^{n-d-a-1}e^m]\\&\quad \;\sum_{i\geq 0}{n-d-1\choose i}(1+t)^{3i}(t+2)^{n-d-i-1}e^{n-d-i-1}t^{n-d-i-1}\\ &={n-d-1\choose m}\sum_{a\geq 0}{2d\choose a}\dfrac{a}{n-d-1}[t^{n-d-a-1}](1+t)^{3(n-m-d-1)}(t+2)^{m}t^{m}\\ &={n-d-1\choose m}\sum_{a\geq 0}{2d\choose a}\dfrac{a}{n-d-1}[t^{n-d-a-1}]\\&\quad \;\sum_{j,k\geq 0}{3(n-m-d-1)\choose j}{m\choose k}2^{m-k}t^{m+j+k}\\ &={n-d-1\choose m}\sum_{a\geq 0}{2d\choose a}\dfrac{a}{n-d-1}\sum_{k\geq 0}{3(n-m-d-1)\choose n-d-m-k-a-1}{m\choose k}2^{m-k}\\ &=\dfrac{2d}{n-d-1}{n-d-1\choose m}\sum_{k\geq 0}\sum_{a\geq 1}{2d-1\choose a-1}{3(n-m-d-1)\choose n-d-m-k-a-1}{m\choose k}2^{m-k}. \end{aligned}\]
By Vandermonde Convolution, we get \[\begin{aligned} {}[x^n&e^m]x(N(x,e)^2/x)^d\\&=\dfrac{2d}{n-d-1}{n-d-1\choose m}\sum_{k\geq 0}{3n-3m-d-4\choose n-d-m-k-2}{m\choose k}2^{m-k}\\ &=\dfrac{d}{n-d-1}{n-d-1\choose m}\sum_{k\geq 0}{3n-3m-d-4\choose n-d-m-k-2}{m\choose k}2^{m-k+1}. \end{aligned}\]
Similarly, \[\begin{aligned} &[x^ne^m]xe(N(x,e)^2/x)^{d-1}\\&=\dfrac{d}{n-d-1}{n-d-1\choose m-1}\sum_{k\geq 0}{3n-3m-d-1\choose n-d-m-k-1}{m-1\choose k}2^{m-k}. \end{aligned}\]
Also, \[\begin{aligned} &[x^ne^m]x^2e(N(x,e)^2/x)^{d-1}\\&=\dfrac{d-1}{n-d-1}{n-d-1\choose m-1}\sum_{k\geq 0}{3n-3m-d-3\choose n-d-m-k-1}{m-1\choose k}2^{m-k}. \end{aligned}\]
Thus, \[\begin{aligned} {}[x^ne^m]x&\left(\frac{N(x,e)^2}{x}\right)^d+[x^ne^m]xe\left(\frac{N(x,e)^2}{x}\right)^d-[x^ne^m]ex^2\left(\frac{N(x,e)^2}{x}\right)^{d-1}\\&=\dfrac{d}{n-d-1}{n-d-1\choose m}\sum_{k\geq 0}{3n-3m-d-4\choose n-d-m-k-2}{m\choose k}2^{m-k+1}\\&+\dfrac{d}{n-d-1}{n-d-1\choose m-1}\sum_{k\geq 0}{3n-3m-d-1\choose n-d-m-k-1}{m-1\choose k}2^{m-k}\\&-\dfrac{d-1}{n-d-1}{n-d-1\choose m-1}\sum_{k\geq 0}{3n-3m-d-3\choose n-d-m-k-1}{m-1\choose k}2^{m-k}. \end{aligned}\]
This completes the proof.
Table 2 lists the numbers of marked noncrossing trees on \(2 \le n \le 6\) vertices classified by root degree \(d\) and number of marked edges \(m\). In the case \(n=4,\) the entries of the table agree with the configurations shown in Figure 3.
| \(n\) | \(d\backslash m\) | 0 | 1 | 2 | 3 | 4 | Total |
|---|---|---|---|---|---|---|---|
| 2 | 1 | 1 | 1 | ||||
| 3 | 1 | 2 | 2 | 4 | |||
| 2 | 1 | 1 | |||||
| 4 | 1 | 7 | 11 | 4 | 22 | ||
| 2 | 4 | 2 | 6 | ||||
| 3 | 1 | 1 | |||||
| 5 | 1 | 30 | 60 | 38 | 8 | 136 | |
| 2 | 18 | 19 | 4 | 41 | |||
| 3 | 6 | 2 | 8 | ||||
| 4 | 1 | 1 | |||||
| 6 | 1 | 143 | 343 | 296 | 112 | 16 | 910 |
| 2 | 88 | 134 | 62 | 8 | 292 | ||
| 3 | 33 | 27 | 4 | 64 | |||
| 4 | 8 | 2 | 10 | ||||
| 5 | 1 | 1 |
We get the following corollary by setting \(m=0\) in (8):
Corollary 2.5. There are \[\begin{aligned} \dfrac{2d}{n-d-1}{3n-d-4\choose n-d-2}, \end{aligned}\] marked noncrossing trees on \(n\geq 2\) vertices with root degree \(1\leq d\leq n-2\) and exactly 1 marked noncrossing tree on \(n\) vertices with root degree \(n-1.\)
The following theorem can also be obtained by summing over all values of \(m\) in (8).
Theorem 2.6. The number of marked noncrossing trees on \(n\geq 2\) vertices with root degree \(n-1\) is 1 and for root degree \(d\neq n-1\), the number is
where \[\begin{aligned} N_{n,d}=\dfrac{d}{n-d-1}\sum_{i=1}^{n-d-1}\sum_{k=0}^{i-1}{n-d-1\choose i}{3i+2d-1\choose i-k-1}{n-d-i-1\choose k}2^{n-d-i-k}. \end{aligned}\]
Proof. From the generating function \[\begin{aligned} N(x)=\dfrac{x}{1-\frac{N(x)^2}{x}}+\dfrac{x(\frac{N(x)^2}{x}-x)}{1-\frac{N(x)^2}{x}}, \end{aligned}\] we have \[\begin{aligned} N(x)&=(x-x^2)+2x\left(\frac{N(x)^2}{x}+\left(\frac{N(x)^2}{x}\right)^2+\cdots\right)-x^2\left(\frac{N(x)^2}{x}+\left(\frac{N(x)^2}{x}\right)^2+\cdots\right). \end{aligned}\]
The required equation is therefore the coefficient of \(x^n\) in \(2x\left(\frac{N(x)^2}{x}\right)^d-x^2\left(\frac{N(x)^2}{x}\right)^{d-1}\) which we aim to find now. \[\begin{aligned} &[x^n]x(N(x)^2/x)^d=[x^{n+d-1}]N(x)^{2d}=[x^{n-d-1}](1+y)^{2d}\sum_{a\geq 0}{2d\choose a}[x^{n-d-1}]y^a\\ &=\sum_{a\geq 0}{2d\choose a}\dfrac{a}{n-d-1}[t^{n-d-a-1}]((1+t)^3+t(t+2))^{n-d-1}\\ &=\sum_{a\geq 0}{2d\choose a}\dfrac{a}{n-d-1}[t^{n-d-a-1}]\sum_{i\geq 0}{n-d-1\choose i}(1+t)^{3i}(t+2)^{n-d-i-1}t^{n-d-i-1}\\ &=\sum_{a\geq 0}{2d\choose a}\dfrac{a}{n-d-1}[t^{n-d-a-1}]\\&\quad \;\sum_{i,j,k\geq 0}{n-d-1\choose i}{3i\choose j}{n-d-i-1\choose k}2^{n-d-i-k-1}t^{n-d-i+j+k-1}\\ &=\sum_{a\geq 0}{2d\choose a}\dfrac{a}{n-d-1}\sum_{i,k\geq 0}{n-d-1\choose i}{3i\choose i-k-a}{n-d-i-1\choose k}2^{n-d-i-k-1}\\ &=\dfrac{2d}{n-d-1}\sum_{i,k\geq 0}{n-d-1\choose i}{3i+2d-1\choose i-k-1}{n-d-i-1\choose k}2^{n-d-i-k-1}. \end{aligned}\]
The last equality follows by Vandermonde Convolution. Likewise, \[\begin{aligned} {}[x^n]&x^2\left(\frac{N(x)^2}{x}\right)^{d-1}\\&=\dfrac{2(d-1)}{n-d-1}\sum_{i,k\geq 0}{n-d-1\choose i}{3i+2d-3\choose i-k-1}{n-d-i-1\choose k}2^{n-d-i-k-1}. \end{aligned}\]
So, \[\begin{aligned} {}[x^n]2x&\left(\frac{N(x)^2}{x}\right)^d-[x^n]x^2\left(\frac{N(x)^2}{x}\right)^{d-1}\\&=\dfrac{4d}{n-d-1}\sum_{i,k\geq 0}{n-d-1\choose i}{3i+2d-1\choose i-k-1}{n-d-i-1\choose k}2^{n-d-i-k-1}\\&-\dfrac{2(d-1)}{n-d-1}\sum_{i,k\geq 0}{n-d-1\choose i}{3i+2d-3\choose i-k-1}{n-d-i-1\choose k}2^{n-d-i-k-1}\\ &=\dfrac{d}{n-d-1}\sum_{i,k\geq 0}{n-d-1\choose i}{3i+2d-1\choose i-k-1}{n-d-i-1\choose k}2^{n-d-i-k+1}\\&-\dfrac{d-1}{n-d-1}\sum_{i,k\geq 0}{n-d-1\choose i}{3i+2d-3\choose i-k-1}{n-d-i-1\choose k}2^{n-d-i-k}. \end{aligned}\]
Thus the proof.
Table 3 presents the numbers of marked noncrossing trees on \(2\le n\le 6\) vertices classified by root degree \(d\). For \(n=4\), the entries in the table can be confirmed by counting the corresponding trees displayed in Figure 3.
| \(n\backslash d\) | 1 | 2 | 3 | 4 | 5 | Total |
|---|---|---|---|---|---|---|
| 2 | 1 | 1 | ||||
| 3 | 4 | 1 | 5 | |||
| 4 | 22 | 6 | 1 | 29 | ||
| 5 | 136 | 41 | 8 | 1 | 186 | |
| 6 | 910 | 292 | 64 | 10 | 1 | 1277 |
Setting \(d=1\) in (9), we get the formula \[\begin{aligned} \dfrac{1}{n-2}\sum_{i=1}^{n-2}\sum_{k=0}^{i-1}{n-2\choose i}{3i+1\choose i-k-1}{n-i-2\choose k}2^{n-i-k}, \end{aligned}\] for the number of marked noncrossing trees on \(n\geq 3\) vertices with root degree 1 (could be thought of as planted noncrossing trees). The sequence that enumerates these trees is \(1, 4, 22, 136, 886,\ldots\). This is listed as sequence A069835 in [12]. A number of categories of lattice paths are listed therein to be enumerated by the same sequence. It would be interesting to construct bijections between the sets of these lattice paths and the set of marked noncrossing trees with root degree 1.
We are concerned with enumeration of marked noncrossing trees based on count of leaves.
Theorem 2.7. There are
marked noncrossing trees on \(n\geq 2\) vertices with \(m\geq 0\) marked edges and \(\ell\geq 1\) leaves.
Proof. Let \(N(x,u,e)\) be the trivariate generating function for marked noncrossing trees, where \(x\), \(u\), and \(e\) mark vertices, leaves, and marked edges, respectively. The generating function for butterflies is \[\frac{N(x,u,e)^2}{x}+xu-x.\]
Indeed, a butterfly is obtained by gluing together two marked noncrossing trees at their roots, which contributes the term \(N(x,u,e)^2/x\). When both wings of the butterfly are empty, the resulting structure consists of a single leaf, contributing the term \(xu\). Since the root vertex of this leaf is already counted in \(N(x,u,e)^2/x\), we subtract \(x\) to avoid double counting. Hence, the generating function for butterflies is \[B(x,u,e)=\frac{N(x,u,e)^2}{x}+xu-x.\]
Using the same decomposition as for marked noncrossing trees, we obtain \[N(x,u,e)=\frac{x}{1-B(x,u,e)} +\frac{xe\bigl(B(x,u,e)-x\bigr)}{1-B(x,u,e)}.\]
Substituting the expression for \(B(x,u,e)\) yields \[N(x,u,e) = \frac{x}{1-\frac{N(x,u,e)^2}{x}-xu+x} + \frac{xe\left(\frac{N(x,u,e)^2}{x}-x\right)} {1-\frac{N(x,u,e)^2}{x}-xu+x}.\]
This reduces to \[\begin{aligned} xN(x,u,e)=N(x,u,e)^3+x^2uN(x,u,e)-x^2N(x,u,e)+x^2+xeN(x,u,e)^2-ex^3. \end{aligned}\]
Let \(N(x,u,e)=x+xy\) so that \[\begin{aligned} y=x((1+y)^3+u(1+y)-(1+y)+e(1+y)^2-e) , \end{aligned}\] or
We proceed as follows to extract the coefficient of \(x^nu^{\ell}e^m\) in \(N(x,u,e)\): \[\begin{aligned} &[x^nu^{\ell}e^m]N(x,u,e)=[x^{n-1}u^{\ell}e^m]y\\&=\dfrac{1}{n-1}[t^{n-2}u^{\ell}e^m]((1+t)(t(2+t)+u)+e(t(2+t)))^{n-1}\\ &=\dfrac{1}{n-1}[t^{n-2}u^{\ell}e^m]\sum_{i\geq 0}{n-1\choose i}(1+t)^{i}(t(2+t)+u)^i(t(2+t))^{n-i-1}e^{n-i-1}\\ &=\dfrac{1}{n-1}{n-1\choose m}[t^{n-2}u^{\ell}](1+t)^{n-m-1}(t(2+t)+u)^{n-m-1}(2+t)^{m}t^{m}\\ &=\dfrac{1}{n-1}{n-1\choose m}[t^{n-2}u^{\ell}]\sum_{j,k\geq 0}{n-m-1\choose j}{n-m-1\choose k}(2+t)^{n-k-1}u^{k}t^{n-k+j-1}\\ &=\dfrac{1}{n-1}{n-1\choose m}[t^{n-2}]\sum_{j\geq 0}{n-m-1\choose j}{n-m-1\choose \ell}(2+t)^{n-\ell-1}t^{n-\ell+j-1}\\ &=\dfrac{1}{n-1}{n-1\choose m}[t^{n-2}]\sum_{i,j\geq 0}{n-m-1\choose j}{n-m-1\choose \ell}{n-\ell-1\choose i}2^{n-\ell-i-1}t^{n-\ell+i+j-1}\\ &=\dfrac{1}{n-1}{n-1\choose m}\sum_{j=0}^{\ell-1}{n-m-1\choose j}{n-m-1\choose \ell}{n-\ell-1\choose \ell-j-1}2^{n-2\ell+j}. \end{aligned}\]
Table 4 presents the distribution of marked noncrossing trees on \(2\le n\le 6\) vertices classified by the number of marked edges \(m\) and leaves \(\ell\). In the case \(n=4\), the values in the table can be verified directly from the marked noncrossing trees displayed in Figure 3.
| \(n\) | \(m\backslash \ell\) | 1 | 2 | 3 | 4 | 5 | Total |
|---|---|---|---|---|---|---|---|
| 2 | 0 | 1 | 1 | ||||
| 3 | 0 | 2 | 1 | 3 | |||
| 1 | 2 | 2 | |||||
| 4 | 0 | 4 | 7 | 1 | 12 | ||
| 1 | 8 | 5 | 13 | ||||
| 2 | 4 | 4 | |||||
| 5 | 0 | 8 | 30 | 16 | 1 | 55 | |
| 1 | 24 | 48 | 9 | 81 | |||
| 2 | 24 | 18 | 42 | ||||
| 3 | 8 | 8 | |||||
| 6 | 0 | 16 | 104 | 122 | 30 | 1 | 273 |
| 1 | 64 | 264 | 164 | 14 | 506 | ||
| 2 | 96 | 216 | 50 | 362 | |||
| 3 | 64 | 56 | 120 | ||||
| 4 | 16 | 16 |
The following corollary is obtained by setting \(e=1\) in (11) and extracting the coefficient of \(x^{n-1}u^{\ell}\) from \(y\).
Corollary 2.8. The number of marked noncrossing trees on \(n\geq 2\) vertices with \(\ell\geq 1\) leaves is given by \[\begin{aligned} \dfrac{1}{n-1}{n-1\choose \ell}\sum_{j=0}^{\ell}{\ell\choose j}{2(n-\ell-1)\choose \ell-j-1}2^{2n-3\ell+j-1}. \end{aligned}\]
Table 5 presents the resulting distribution of marked noncrossing trees according to the number of vertices and leaves. The entries for \(n=4\) are consistent with the marked noncrossing trees illustrated in Figure 3.
| \(n\backslash \ell\) | 1 | 2 | 3 | 4 | 5 | Total |
|---|---|---|---|---|---|---|
| 2 | 1 | 1 | ||||
| 3 | 4 | 1 | 5 | |||
| 4 | 16 | 12 | 1 | 29 | ||
| 5 | 64 | 96 | 25 | 1 | 186 | |
| 6 | 256 | 640 | 336 | 44 | 1 | 1277 |
By setting \(m=0\) in (10), we rediscover the formula, first obtained by Flajolet and Noy in [3], for the number of noncrossing trees on \(n\geq 2\) vertices with \(\ell\geq 1\) leaves as \[\begin{aligned} \dfrac{1}{n-1}{n-1\choose \ell}\sum_{j=0}^{\ell-1}{n-1\choose j}{n-\ell-1\choose \ell-j-1}2^{n-2\ell+j}. \end{aligned}\]
Let \(\mathcal{T}\) be a family of plane trees in which outdegree (number of children) of each internal vertex is 1, 2 or 3, the rightmost edge coming out of a vertex of outdegree 2 is labelled 1, 2, 3 or 4, and each edge emanating from a vertex of outdegree 1 is labelled from the set \(\{1,2,3,4,5\}.\) In Figure 5, we get all the 29 plane trees on 3 vertices.
The symbolic representation for these trees is shown in Figure 6.
Let \(T(x)=T\) be the generating function for the trees in \(\mathcal{T}\) with \(x\) marking a vertex. So, by the symbolic representation \[\begin{aligned} T(x)=x+5xT+4xT^{2}+xT^{3}. \end{aligned}\]
This equation is simplified to get
Eq. (12) is also the generating function for marked noncrossing trees with \(x\) marking non-root vertices. So, we have that the formula that counts the plane trees described in this subsection on \(n-1\) vertices is the same formula that enumerates marked noncrossing trees with \(n\) vertices.
Consider ternary trees (plane trees with left, middle or right edges) in which an edge emanating from a vertex of outdegree 1 is labelled 1, 2 or 3 if it is the right edge and an edge emanating from a vertex of outdegree 2 is labelled 1 or 2 if it is a right edge and the other edge emanating from the said vertex is a left edge. Figure 7 lists all the 29 ternary trees on 3 vertices.
Let \(T(x)\) be the generating function for these trees, where \(x\) marks a non-root vertex. A tree may consist solely of a root vertex, contributing \(x\) to the generating function. If the root has exactly one child, then the child may be attached to the root by a left, middle, or right edge, with the right edge carrying one of three possible labels. This yields a contribution of \(5xT(x).\) If the root has exactly two children, then the edges incident to the root may be of types left–middle, middle–right, or left–right. In the left–right case, the right edge may receive one of two labels. Consequently, this configuration contributes \(4xT(x)^2.\) Finally, if the root has exactly three children, there is a unique admissible configuration, contributing \(xT(x)^3.\)
Summing over all possible root configurations gives \[T(x)=x+5xT(x)+4xT(x)^2+xT(x)^3.\]
Equivalently, \[T(x) = x\bigl(1+5T(x)+4T(x)^2+T(x)^3\bigr) = x\bigl((1+T(x))^3+T(x)(2+T(x))\bigr).\]
This is precisely the functional equation satisfied by the generating function for marked noncrossing trees when \(x\) marks non-root vertices. Therefore, the enumeration formula obtained for the ternary trees described in this subsection with \(n-1\) vertices also counts marked noncrossing trees on \(n\) vertices. In particular, the coincidence of the generating functions establishes the equinumerosity of the two classes and hence the equality of their counting formulas. It is not difficult to construct the bijection between the set of ternary trees and the set of plane trees described in the previous subsection.
In this paper, we introduced and studied marked noncrossing trees, a natural extension of classical noncrossing trees obtained by distinguishing an edge. Using generating function techniques and the Lagrange inversion formula, we derived explicit counting formulas for marked noncrossing trees with respect to several fundamental parameters, including the number of vertices, marked edges, root degree, and leaves. These formulas reveal rich combinatorial structures and provide new enumerative results that complement the existing theory of noncrossing trees. We also established connections between marked noncrossing trees and other combinatorial structures. In particular, we described two classes of objects that are equinumerous with marked noncrossing trees and obtained corresponding counting formulas. These relationships provide additional combinatorial interpretations of the enumeration results and highlight the versatility of the generating-function approach.
Future research could explore enumeration by further parameters such as endpoints, components for forests and vertex levels among others. It would also be interesting to seek direct bijective proofs of the equinumerosity results obtained in this paper and to explore connections with related classes of plane trees and lattice paths. Recently, Okoth and Kasyoki [7] unified various results on the enumeration of plane trees and noncrossing trees by introducing \(d\)-dimensional plane trees, where 1-dimensional and 2-dimensional cases correspond to ordinary plane trees and noncrossing trees, respectively. As such, the results of this paper have the potential to be extended to marked \(d\)-dimensional plane trees. Moreover, bijections involving structures counted by the sequence enumerating marked noncrossing trees present a promising direction for further study. The families of \(k\)-plane trees, introduced by Gu, Prodinger and Wagner [4], and \(k\)-noncrossing trees [9], are also enumerated by the Fuss-Catalan numbers. Considerable work on the enumeration of these structures, especially in [8] and related papers, has been carried out using various parameters. An intriguing avenue for future research would be to investigate whether these \(k\)-plane and \(k\)-noncrossing trees bear meaningful connections to marked plane trees, noncrossing trees or their generalizations.
The authors are grateful to the anonymous reviewers for their insightful comments and valuable suggestions, which greatly improved the quality of this paper. The first author acknowledges the financial support of the German Academic Exchange Service (DAAD) towards his PhD studies at Moi University.