Bijections of \(k\)-plane trees

1. Introduction

Plane trees (or ordered trees) have computer science and mathematics applications alike. These are rooted trees with the property that all the children of the vertices are ordered. These trees have been generalized by labeling the vertices to obtain \(k\)-plane trees, which we now define. When the vertices of the plane trees are labeled with integers in the set \(\{1,2,\ldots,k\}\) such that there are no edges \((i,j)\) with the property that \(i+j>k+1\) then such trees are called \(k\)-plane trees. These trees were introduced and studied by Gu, Prodinger, and Wagner in [1]. The aforementioned authors showed that the number of \(k\)-plane trees with root labelled by \(h\) on \(n>1\) vertices is given by

and the total number of \(k\)-plane trees with \(n>1\) vertices is \[\frac{k}{n} \binom{(k+1)(n-1)}{n-1}.\] In [2], Okoth and Wagner showed that the total number of \(k\)-plane trees on \(n>1\) vertices whose root is labelled by \(k\) such that there are \(v_j\) vertices labelled by \(j\in\{1,2,\ldots,k\}\) is Here, empty sums and empty products are considered to be \(0\) and 1 respectively.

Setting \(k=2\) and \(h=2\) in Eq. (1), we find that the number of \(2\)-plane trees on \(n\) vertices whose root is labelled by 2 is given by

\[\frac{1}{2n-1} \binom{3n-3}{n-1}.\] This formula also counts the number of noncrossing trees on \(n\) vertices and ternary trees on \(n-1\) vertices among other structures, see sequence https://oeis.org/A001764 in [3]. A bijection between the set of 2-plane trees and the set of ternary trees was constructed by Gu and Prodinger in an earlier paper [4]. Of course, setting \(k=h=1\) in Eq. (1), we recover Catalan's number that counts the number of plane trees with \(n\) vertices.

A \(k\)-noncrossing tree is a noncrossing tree whose vertices are labelled with integers in the set \(\{1,2,\ldots,k\}\) such that if an edge \((i,j)\) is an ascent in the path from the root then \(i+j\leq k+1\). These trees were first studied by Pang and Lv [5]. When \(k=2\) we obtain \(2\)-noncrossing trees, introduced and enumerated by Yan and Liu [6]. The author recently refined the formula of Yan and Liu in [7]. Similarly, when \(k=1\) we recover noncrossing trees.

In 2015, Okoth and Wagner [8] obtained counting formulas for the number of noncrossing trees whose edges are locally oriented. By local orientation, we mean that the edges are oriented from vertices of the lower label towards vertices of the higher label. The said authors coined the words locally-oriented noncrossing trees for these trees. In the same paper, they called a vertex of in-degree 0 (resp. outdegree 0) as source (resp. sink). A \(k\)-noncrossing tree whose edges have local orientation will be referred to as locally-oriented \(k\)-noncrossing tree.

A noncrossing increasing tree [9] is a noncrossing tree whose labels increase along the paths from the root of the tree. The number of these trees on \(n\) vertices is also given by the Catalan number \[\dfrac{1}{n}{2n-2\choose n-1}.\] In [10], Okoth introduced and enumerated 2-noncrossing increasing trees by root degree and the number of vertices labeled by 2. These are 2-noncrossing trees whose labels increase as one moves away from the root. In the same spirit, a \(k\)-noncrossing increasing tree is a \(k\)-noncrossing tree whose labels increase as one moves away from the root.

Lattice paths have been studied for centuries. For example, a Dyck path of length \(n\) is a path from point \((0,0)\) to point \((n,0)\) which consists of up steps and down steps such that the path does not go below the \(x\)-axis. In this paper, we also consider lattice paths starting at \((0,0)\) and consisting of unit vertical and unit horizontal steps such that the path either touches or lies above the line \(x=ky.\) We shall call these lattice paths as restricted lattice paths.

This paper is organized as follows: We construct bijections between the set of \(k\)-plane trees and the set of \(k\)-noncrossing increasing trees in §2, locally oriented \((k-1)\)-noncrossing trees in §3, Dyck paths in §4 and restricted lattice paths in §5 respectively. We conclude the paper in §6 and expose some problems.

2. \(k\)-Noncrossing increasing trees

In the sequel, we show that the number of \(k\)-noncrossing increasing trees on \(n\) vertices such that the root is labeled by \(h\) is given by Eq. (1), the same formula that enumerates \(k\)-plane trees by root label and several vertices.

Theorem 1. There is a bijection between the set of \(k\)-plane trees on \(n\) vertices whose root is labelled by \(h\) and the set of \(k\)-noncrossing increasing trees on \(n\) vertices whose root is labelled by \(h\).

Proof. Let \(T\) be a \(k\)-plane tree on \(n\) vertices whose root is labeled by \(h\). We obtain a corresponding \(k\)-noncrossing increasing tree \(T'\) on \(n\) vertices whose root is labelled by \(h\) as follows: Each vertex in \(T\) becomes a vertex of \(T'\) and the children of a given vertex in \(T\) become right wing of a butterfly rooted at a corresponding vertex in \(T'\) such that if \(v_1, v_2,\ldots,v_i\) are the left-to-right children of the root \(v\) in \(T\) then \(v_1\) receives the highest label, followed by \(v_2\), and so on in \(T'\). Vertex \(v_i\) receives the least label. If a vertex is labeled by \(j\) in plane tree \(T\), the corresponding vertex in the noncrossing tree \(T'\) is labeled by \(j\). Therefore, the root of the \(k\)-noncrossing increasing tree is labeled by \(h\).

We now obtain the reverse procedure: Let \(T'\) be a \(k\)-noncrossing increasing tree with root \(r\) labeled by \(h\) and have \(n\) vertices. Let \(r_{1}< r_{2}< \cdots< r_{d}\) be the vertices of \(T'\) incident to \(r\). Vertex \(r\) corresponds to the root in the \(k\)-plane tree \(T\) and vertices \(r_{1},r_{2},\ldots, r_{d}\) correspond to the right-to-left children of the root in the \(k\)-plane tree. (So if the root in the \(k\)-noncrossing increasing tree is labeled by \(h\), the corresponding \(k\)-plane tree has its root labeled by \(h\).) Now, consider vertex \(r_1\) and all the vertices incident to it apart from \(r\), which is already in the \(k\)-plane tree. Draw these vertices as the children of \(r_1\). Again the ordering of the children is done with the vertex, with the largest label being the leftmost vertex. We repeat the process, and the algorithm stops when all the vertices have been drawn in the \(k\)-plane tree.

An example is given in Figure 1.

3. Locally oriented \((k-1)\)-noncrossing trees

In this section, we use number of vertices of each kind and the number of sources labelled by \(1\) as the statistics of enumeration. In the following theorem, we show that Eq. (2) which counts the number of \(k\)-plane trees with root labelled by \(k\), on \(n\) vertices, \(v_i\) of which are labelled by \(i\) for \(1\leq i\leq k\), also counts the number of locally oriented \((k-1)\)-noncrossing trees on \(n\) vertices such that the root is labelled by \(1\), the total number of sources labelled by \(1\) is \(v_k\), the total number of non-source vertices labelled by 1 is \(v_1\) and the number of vertices labelled by \(i\) is \(v_i\) for \(2\leq i\leq k-1\).

Theorem 2. There is a bijection between the set of \(k\)-plane trees with root labelled by \(k\) on \(n\) vertices, \(v_i\) of which are labelled by \(i\) for \(1\leq i\leq k\), and the set of locally oriented \((k-1)\)-noncrossing trees with root labelled by 1 on \(n\) vertices such that the total number of sources labelled by 1 is \(v_k\), non-source vertices labelled by 1 is \(v_1\) and for \(i\in\{1,2,\ldots,k-1\}\), there are \(v_i\) vertices labelled by \(i\).

Proof. By Theorem 1, it suffices to construct a bijection between the set of \(k\)-noncrossing increasing trees with root labelled by \(k\) on \(n\) vertices, \(v_i\) of which are labelled by \(i\) for \(1\leq i\leq k\), and the set of locally oriented \((k-1)\)-noncrossing trees with root labelled by 1 on \(n\) vertices such that the total number of sources labelled by 1 is \(v_k\), non-source vertices labelled by 1 is \(v_1\) and for \(i\in\{1,2,\ldots,k-1\}\), there are \(v_i\) vertices labelled by \(i\).

Consider a \(k\)-noncrossing increasing tree on \(n\) vertices with root labelled by \(k\). For \(i\in\{1,2,\ldots,k\}\), let the number of vertices labelled by \(i\) be \(v_i\). We obtain the corresponding locally oriented \((k-1)\)-noncrossing tree by the following steps:

• (i) Relabel the root of the \(k\)-noncrossing increasing tree by 1.
• (ii) Starting at the root, we visit the vertices of the \(k\)-noncrossing increasing tree in clockwise direction. Let \(v\) be the first vertex labelled by \(k\) (other than the root). Let \(u\) be the vertex incident to \(v\) such that \(u< v\). Vertex \(u\) is labelled by 1 so as to satisfy the ascent rule.
• (iii) Insert a new vertex \(v'\) labelled by 1 just before \(u\). Delete the edge \(uv\) and create a new edge \(uv'\). Adjoin \(v\) and the butterflies rooted at \(v\) as the right wing of the butterfly rooted at \(v'.\)
• (iv) Repeat the procedure until there are no vertices labelled by \(k\).
• (v) Rename the vertices in clockwise direction as \(1,2,\ldots,n\) and use local orientation to give directions to the edges.

The tree obtained is a locally oriented \((k-1)\)-noncrossing tree on \(n\) vertices with \(v_k\) sources labelled by 1 (all the vertices labelled by \(k\) in the \(k\)-noncrossing increasing tree become sources labelled by 1), \(v_1\) non-source vertices labelled by 1 (these were the vertices labelled by 1 in the \(k\)-noncrossing increasing tree) and \(v_i\) vertices labelled by \(i\) for \(i\in\{1,2,\ldots,k-1\}\) (the vertices labelled by \(i\) for \(2\leq i\leq k-1\) retain their labels in the locally oriented \((k-1)\)-noncrossing tree).

We now obtain the reverse procedure:

• (i) Relabel the root of the locally oriented \(k\)-noncrossing tree as \(k\).
• (ii) Starting at the root, we visit the vertices of the locally oriented \(k\)-noncrossing tree in clockwise direction. Let \(v\) be a source labelled by 1 with the largest vertex label. Let \(u\) be the vertex incident to \(v\) such that \(u>v\) and \(u\) is the vertex with the largest label.
• (iii) Insert a new vertex \(u'\) after \(v\). Label the new vertex by \(k.\) Delete the edge \(uv\) and create a new edge \(vu'\). Adjoin \(u\) and the butterflies rooted at \(u\) as the right wing of the butterfly rooted at \(u'.\)
• (iv) Rename the vertices in clockwise direction as \(1,2,\ldots,n\).
• (v) Repeat the procedure until there is no source labelled by 1.

We obtain a \(k\)-noncrossing increasing tree on \(n\) vertices of which \(v_i\) vertices are labeled by \(i\), and the root is labeled by \(k\). That is, a source labeled by 1, a non-source vertex labeled by 1, and a vertex labeled by \(i\) for \(2\leq i\leq k-1\) in a locally oriented \((k-1)\)-noncrossing tree corresponds to a vertex labeled by \(k\), a vertex labeled by \(1\) and a vertex labeled by \(i\) for \(2\leq i\leq k-1\) respectively in the \(k\)-noncrossing increasing tree whose root is labeled by \(k\).

For an example of the bijection, see Figure 2.

Setting \(k=2\) in Eq. (2), we recover the formula for the number of locally oriented noncrossing trees on \(n\) vertices with \(i\) sources obtained by Okoth and Wagner in [8]. In [7], the present author obtained the number of locally oriented \(2\)-noncrossing trees on \(n\) vertices whose root is labeled by 2 with a given number of vertices labeled by 2 and number of sources labeled by 1.

4. Dyck paths

In this section, we show that there is a bijection between the set of \(k\)-plane trees, with root labeled by 1, on \(n\) vertices and the set of Dyck paths from \((0,0)\) to \((2n-2,0)\) where the up steps are labeled with integers in the set \(\{1,2,3,\ldots,k\}\) such that if an up step labeled \(i\) is followed by another up step labeled \(j\) then the coherence condition \(i+j\leq k+1\) must be satisfied.

Let \(T\) be a \(k\)-plane tree with root labeled by 1 on \(n\) vertices. We obtain the Dyck path \(D\) of length \(2n-2\) as follows: Starting to the left of a given plane tree \(T\), we move around the tree, always moving away from the root on the left-hand side of an edge and moving towards the root on the right-hand side of an edge. Each edge corresponds to one-up step and one down step is as follows:

• (i) Draw an up step (labelled by \(i\)) if the vertex visited, as one traverses an edge on the left hand side of the edge, is labelled by \(i\).
• (ii) Draw a down step if one traverses an edge on the right hand side of the edge (towards the root).

We obtain a Dyck path \(D\) of length \(2n-2\) with up steps labeled by \(i\in\{1,2,\ldots,k\}\) and satisfying the condition \(i+j\leq k+1\) for any adjacent labels \(i\) and \(j\). Since the condition is satisfied in the \(k\)-plane tree, it must be true for Dyck paths obtained here.

For a bijection, we obtain the reverse procedure: Let \(D\) be a Dyck path of length \(2n-2\) such that its up steps are labelled with integers in the set \(\{1,2,\ldots,k\}\) and that label \(i\) is never followed by label \(j\) if \(i+j>k+1.\) We obtain a corresponding \(k\)-plane tree with a root labeled by 1 on \(n\) vertices by the following procedure: Draw a vertex \(v\) and label it 1. Starting at the beginning of the Dyck path, if the up step is labeled \(i\) then draw an edge connecting \(v\) to a new vertex labeled by \(i\). Continue the process with the Dyck path until you get a down step. For each down step, move up an edge (on the right-hand side of the edge, in the tree already drawn, towards the root). Continue until you find an up step. Let \(u\) be the vertex reached before the up step. If the up step is labeled \(j\) then draw an edge connecting \(u\) to a new vertex labeled by \(j\). Repeat the procedure until all paths in the Dyck path are visited. The tree obtained is a \(k\)-plane tree with roots labeled by 1 on \(n\) vertices.

Figure 3 below gives an example of the bijection.

Based on the bijection above, we give the following theorem:

Theorem 3. The number of Dyck paths from \((0,0)\) to \((2n-2,0)\), consisting of \((n-1)\) down steps of unit length and \((n-1)\) up steps of unit length labelled by integers in the set \(\{1,2,\ldots,k\}\) such that if label \(i\) is followed by label \(j\) then \(i+j\leq k+1\), is given by \begin{align*} \dfrac{1}{n}{(k+1)n-2\choose n-1}. \end{align*}

We note that the case of \(k=2\) in Theorem 3 was obtained in [10] and of \(k=1\) gives the equivalent result for unlabelled Dyck paths, given by Catalan numbers.

5. Restricted lattice paths

Consider lattice paths made up of \(kn-k\) vertical steps of unit length and \(n-1\) horizontal steps, also of unit length, such that the paths lie above or touch the line \(x=ky\). In this section, we construct a bijection between the set of these paths and the set of \(k\)-plane trees with roots labelled by \(k\) on \(n\) vertices.

Let \(T\) be a \(k\)-plane tree with root labelled by \(1\) on \(n\) vertices. We obtain the corresponding lattice path with \(n-1\) vertical steps and \(kn-k\) horizontal steps such that the paths never go below the line \(x=ky\). We use the procedure of Gu, Prodinger and Wagner in [1] to move from a \(k\)-plane tree to a Dyck path. We shall then construct a bijection beween the set of the Dyck paths and the set of the lattice paths defined here. Before we present our bijection and for the benefit of clarity, we present the bijection obtained by the said authors in the next subsection.

5.1. Bijection between \(k\)-plane trees and Dyck paths

We begin by giving the procedure of obtaining a Dyck path from a \(k\)-plane tree with root labelled by \(k\). Starting to the left of a given tree \(T\), we move around the tree, always moving away from the root on the left hand side of an edge and towards the root on the right hand side of an edge, as was in §3. Each edge contributes a total of \(k\) down steps and one up step as follows:

• (i) Draw \(i-1\) down steps (\((1,-1)\) steps), followed by an up step (\((k,k)\) step) if the vertex visited, as one traverses an edge on the left hand side of the edge, is labelled by \(i\).
• (ii) Draw \(k-i+1\) down steps (\((1,-1)\) steps)) if one traverses an edge on the right hand side of the edge and the initial vertex is labelled by \(i\).

The resultant path is a Dyck path \(D\) from \((0,0)\) to \((2kn-2k, 0).\)

Let us now obtain the reverse procedure: Let \(D\) be a Dyck path from \((0,0)\) to \((2kn-2k,0)\). We obtain a corresponding \(k\)-plane tree on \(n\) vertices whose root is labelled by \(k\) by the following procedure: We visit all up steps and down steps of the Dyck path starting at point \((0,0)\).

• (i) Draw a root (call it \(u\)) of the \(k\)-plane tree and label it by \(k\).
• (ii)If an up step is preceded by a down step of length \(i-1\) then draw an edge from \(u\) to new vertex \(v\), labelled by \(i\). Next, if the following up step is preceded by another down step of length \(j-1\) for \(1\leq j\leq k\) then draw an edge from \(v\) to a new vertex \(w\) labelled by \(j\).
• (iii) Otherwise, if the terminal vertex in the tree is labelled by \(i\) then for consecutive \(k-i+1\) down steps, move up the edge of the tree on the right hand side of the edge towards the root.
• (iv) Repeat steps (ii) and (iii) until all the steps in the Dyck path are visited.

We obtain a \(k\)-plane tree on \(n\) vertices whose root is labelled by \(k\).

An example to explain the bijection is given in Figure 4.

5.2. Bijection between Dyck paths and restricted lattice paths

Let \(D\) be the Dyck path defined in §5.1. We obtain a lattice path from \((0,0)\) to \((kn-k, n-1)\) with \(n-1\) vertical steps by the following steps.

• (i) For each up step, draw a vertical step.
• (ii) For each down step, draw a horizontal step.

The lattice path obtained is never goes below the line \(x=ky\).

We obtain the reverse procedure: Let \(L\) be a lattice path comprising of \(n-1\) unit vertical steps and \(kn-k\) unit horizontal steps such that the lattice path lies above or touches the line \(x=ky\). We obtain its corresponding Dyck path as follows:

• (i) For each horizontal step, draw a down step.
• (ii) For each vertical step, draw an up step.

An example is given in Figure 5 which corresponds to the 4-plane tree and Dyck path in the last subsection.

6. Conclusion

In this paper, we have constructed bijections between the set of \(k\)-plane trees and the sets of \(k\)-noncrossing increasing trees, locally oriented \((k-1)\)-noncrossing trees, Dyck paths, and some restricted lattice paths. It would be interesting to enumerate these structures from a generating function approach. Setting \(k=2\) and \(h=1\) in Eq. (1), we obtain the number of \(2\)-plane trees on \(n\) vertices whose root is labelled by 1. It is given by the sequence \(1,2,7,30,\ldots\) which is recorded as https://oeis.org/A006013 in the Neil Sloane's celebrated On-Line Encyclopedia of Integer Sequences (OEIS) [3]. Among the structures listed to be counted by the same formula include \(S\)-Motzkin paths introduced and enumerated by Prodinger and his coauthors in [11], \((3/2)\)-ary trees introduced and studied by Knuth in his Annual Christmas Tree Lecture [12], pattern avoidance patterns, Dyck paths, restricted lattice paths, and plane trees with \(n\) internal vertices and \(n\) leaves. It would be interesting to construct bijections between the set of \(k\)-plane trees and the sets of generalizations of \(S\)-Motzkin paths, \((3/2)\)-ary trees, pattern avoidance patterns among other structures listed under sequence https://oeis.org/A006013 in [3].

Conflicts of Interest:

The author declares no conflict of interest.