Recursive Generation of k-ary Trees

K. Manes, A. Sapounakis, I. Tasoulas and P. Tsikouras Department of Informatics University of Piraeus 18534 Piraeus Greece

                        kmanes@unipi.gr
                       arissap@unipi.gr
                         jtas@unipi.gr
                        pgtsik@unipi.gr

Abstract

In this paper we present a construction of every k-ary tree using a forest of (k − 1)- ary trees satisfying a particular condition. We use this method recursively for the construction of the set of k-ary trees from the set of (k −1)-Dyck paths, thus obtaining a new bijection ϕ between these two sets. Furthermore, we introduce a new order on [k]^{∗} which is used for the full description of this bijection. Finally, we study some new statistics on k-ary trees which are transferred by ϕ to statistics concerning the occurrence of strings in (k − 1)-Dyck paths.

1 Introduction

The notion of k-ary trees has been studied extensively in the literature. Some authors deal with the generation of k-ary trees using some encoding of them as integer sequences, which are generated in a specific order (see for example [3, 10, 11, 17, 20, 21]). In another direction k-ary trees are related to other k-Catalan structures such as staircase tilings, the tennis ball problem, noncrossing contractions and K-trees (see for example [6, 7, 12, 13, 14]). Finally, there are some papers dealing with the enumeration of k-ary trees according to some parameters (see for example [5, 19, 22]).

A well known procedure for the study of trees contained in a certain set T is to introduce a decomposition of these trees with respect to the size and then, using this decomposition, to rebuild T from trees of smaller size.

In this paper, we use a different procedure for the construction of the set T_{k} of all kary trees. First, we present a decomposition of each k-ary tree to a forest of (k − 1)-ary trees satisfying certain properties and we show how these trees can be reconstructed from the associated forest. Next, by introducing an operation on forests, we present a recursive construction (in terms of k) of T_{k} using unary trees, thus obtaining a new bijection from k-ary trees to (k − 1)-Dyck paths.

In Section 2 we give some definitions and preliminary results.

In Section 3 we associate every k-ary tree with a forest of (k − 1)-ary trees such that the path with ascent sequence consisting of the sizes of the trees in this forest is a Dyck path. Conversely, every such forest generates the tree uniquely; consequently an algorithmic construction is given.

In Section 4, the method used in the previous section is applied recursively for every k-ary tree, and terminates with a forest of unary trees such that the path with ascent sequence consisting of the sizes of the trees in this forest is a (k − 1)-Dyck path. Conversely, this forest generates the tree uniquely, so that a new bijection ϕ between T_{k} and the set of all (k − 1)-Dyck paths is obtained.

In Section 5 we fully describe ϕ, by introducing a new order on the set of maximal paths of the k-ary tree.

Finally, in Section 6 we enumerate the set T_{k} according to some parameters related to the notions of the previous sections.

2 Preliminaries

A k-ary tree, k ≥ 1, is either the empty tree □ or a vertex (or internal node), called the root of the tree, with k ordered children which are k-ary trees. We define T_{k,n} to be the set of all k-ary trees with n vertices, and T_{k} = ⋃_{n≥0} T_{k,n}. Thus, every T ∈ T_{k} can be uniquely

decomposed as follows:

T = □ or T = T_{1}T_{2} ⋯ T_{k}, T_{i} ∈ T_{k}, i ∈ [k]  (1)

(see Figure 1).

Figure 1: The k-ary tree T = T_{1}T_{2} ⋯ T_{k}.

An empty child of a vertex is called a leaf (or external node) of the tree. The size of a k-ary tree T is the number of its vertices and it is denoted by s(T); (see for example Figure 2).

Clearly, every T ∈ T_{k,n} contains kn + 1 nodes (k children for each of the n internal nodes plus the root of the tree) and (k − 1)n + 1 leaves.

Figure 2: A 3-ary tree of size 8.

It is well known (see for example [8], p.589) that |T_{k,n}| is equal to the n-th k-Catalan number

C_{n}^{(k)} = \frac{1}{kn + 1}\binom{kn + 1}{n} = \frac{1}{(k − 1)n + 1}\binom{kn}{n}.

We note that C_{n}^{(2)} are the ordinary Catalan numbers C_{n} ([15], \underline{A000108}).

Furthermore, the generating function C_{k}(x) = ∑_{n≥0} C_{n}^{(k)}x^{n} of the k-Catalan sequence satisfies the equation

C_{k}(x) = 1 + x(C_{k}(x))^{k},

from which it can be easily shown using the Lagrange inversion formula ([2], Appendix A) that the coefficients of (C_{k}(x))^{s}, s ∈ ℕ, are given by the formula

[x^{n}](C_{k}(x))^{s} = \frac{s}{kn + s}\binom{kn + s}{n}.

Every non-empty (k − 1)-ary tree can be considered as a k-ary tree which has all its k-th children empty.

A maximal (k − 1)-ary subtree of a k-ary tree T is any tree obtained by choosing a k-th child in T (or T itself) and by deleting every k-th child in it. Obviously, two maximal k − 1-ary subtrees of T are disjoint; (see for example Figure 3).

Consequently, if T has n vertices, then it contains n + 1 maximal (k − 1)-ary subtrees. A (totally ordered) forest of k-ary trees is an element F of the cartesian product T_{k}^{λ}, for

some λ ∈ ℕ^{∗}. We denote, for simplicity, the forest which consists of a single tree T by T. The concatenation of the forests F_{1}, F_{2}, …, F_{ρ} is a new forest which consists of the trees of each F_{j}, j ∈ [ρ], ordered by extending the orders of every F_{j}, preserving at the same time their natural order. The length and the size of a forest F = (T_{1}, T_{2}, …, T_{λ}) are defined respectively by

|F| = λ and s(F) = ∑_{i=1}^{λ} s(T_{i}).

A non-empty i-path, i ∈ ℕ^{∗}, is a lattice path starting at the point (0, 0) and consisting of steps u_{i} = (1, i) (rises) and d = (1, −1) (falls). The empty path ε is the path with no steps.

Figure 3: The 3-ary tree of Figure 2 and all its binary maximal subtrees.

For every i-path P we denote by r(P) (respectively f(P)) the number of rises (respectively falls) of P. An i-Dyck path is an i-path that never falls below the x axis and ends at the x axis. If P is an i-Dyck path, then f(P) = i·r(P) and P ends at the point ((i+1)r(P), 0). We will refer to a 1-path (respectively a 1-Dyck path) as a path (respectively a Dyck path); in this case we write u instead of u_{1}. The set of all i-Dyck paths with n rises is denoted by D_{n}^{(i)} and D^{(i)} = ⋃_{n≥0} D_{n}^{(i)}. In particular, we write D (respectively D_{n}) instead of D^{(1)} (respectively

D_{n}^{(1)}) for the ordinary Dyck paths.

Every non empty i-Dyck path P is written in the following form, called the first return decomposition (for i = 1, see [2]):

P = u_{i}Q_{1}dQ_{2}d ⋯ Q_{i}dQ_{i+1}  (2)

where Q_{j} ∈ D^{(i)}, j ∈ [i + 1]. Using this decomposition and the Lagrange inversion formula, it can be easily obtained that i-Dyck paths with n rises are counted by C_{n}^{(i+1)}. A simple bijection θ between the k-ary trees and the (k − 1)-Dyck paths is given as follows:

θ(□) = ε and θ(T_{1}T_{2} ⋯ T_{k}) = u_{k−1}θ(T_{1})dθ(T_{2})d ⋯ θ(T_{k−1})dθ(T_{k}).

Another well known decomposition of non-empty i-Dyck paths which will be used in this paper is based on the length of the first ascent, i.e.,

P = u_{i}^{μ}dQ_{1}dQ_{2}d ⋯ Q_{μi}  (3)

where Q_{j} ∈ D^{(i)} and j ∈ [μi].

Every i-path P is uniquely determined by its sequence of ascents (l_{m})_{m∈[μ]}, μ ∈ ℕ^{∗}, according to the formula P = u_{i}^{l_{1}}du_{i}^{l_{2}}d ⋯ u_{i}^{l_{μ−1}}du_{i}^{l_{μ}}, where u_{i}^{j} = u_{i}u_{i} ⋯ u_{i} (j times). Clearly, if P ends at the x axis (as in the case of i-Dyck paths), then l_{μ} = 0. The sum of the elements of this sequence equals the number of rises in the path and the number of its elements is one more than the number of falls; (see for example Figure 4).

We note that the path P = u_{i}^{l_{1}}du_{i}^{l_{2}}d ⋯ u_{i}^{l_{μ−1}}du_{i}^{l_{μ}} is an (i − 1)-Dyck path if and only if

Figure 4: The Dyck path having ascent sequence (4, 0, 0, 2, 0, 1, 0, 1, 0).

the following two conditions hold:

(i − 1) ∑_{j=1}^{m} l_{j} ≥ m, for all m ∈ [μ − 1] and (i − 1) ∑_{j=1}^{μ} l_{j} = μ − 1.

For every forest F we denote by P_{i}(F) the i-path with ascent sequence the sequence of sizes of the trees in F. If i = 1 we write P (F) instead of P_{1}(F). It is evident that r(P_{i}(F)) = s(F) and f(P_{i}(F)) = |F| − 1.

We note that if F is the concatenation of the forests F_{1}, F_{2}, …, F_{ρ}, then

P_{i}(F) = P_{i}(F_{1})dP_{i}(F_{2})d ⋯ P_{i}(F_{ρ−1})dP_{i}(F_{ρ}).  (4)

3 Generation of k-ary trees from (k − 1)-ary trees

For every non-empty T ∈ T_{k}, k ≥ 2, we denote by F(T) the forest consisting of all maximal (k − 1)-ary subtrees of T, ordered according to the first time visit (in preorder) of the trees of F(T) in T and by T^{∗} the first component of F(T); (see for example Figure 5).

Figure 5: The forest F(T) and its corresponding path P (F(T)) for the tree T of Figure 2.

Clearly, T^{∗} is rooted at the root of T and can be obtained by deleting every k-th child of T. If T is empty then T^{∗} is empty and F(□) = □. It is clear that the last tree of F(T) is always the empty tree.

Using decomposition (1), we can easily check that F(T) is the concatenation of T^{∗}, F̃(T_{1}), F̃(T_{2}), …, F̃(T_{k−1}), F(T_{k}), where T^{∗} = T_{1}^{∗}T_{2}^{∗} ⋯ T_{k−1}^{∗} and F̃(T_{j}), j ∈ [k − 1], is F(T_{j}) excluding T_{j}^{∗}.

We have the following result.

Proposition 1. For every T = T_{1}T_{2} ⋯ T_{k} ∈ T_{k} we have

i) s(T^{∗}) = 1 + ∑_{j=1}^{k−1} s(T_{j}^{∗}).

ii) s(F(T)) = s(T).

iii) |F(T)| = s(T) + 1.

iv) P (F(T)) = u^{ν}dP (F̃(T_{1}))dP (F̃(T_{2})) ⋯ dP (F̃(T_{k−1}))dP (F(T_{k})), where ν = s(T^{∗}).

v) P (F(T)) is a Dyck path.

Proof. The proof of (i) is obvious, whereas the proof of (iv) follows immediately from relation (4). The proofs of (ii), (iii) and (v) use induction as follows:

s(F(T)) = s(T^{∗}) + ∑_{j=1}^{k−1}(s(F(T_{j})) − s(T_{j}^{∗})) + s(F(T_{k}))

= s(T^{∗}) + ∑_{j=1}^{k}(s(T_{j})) − ∑_{j=1}^{k−1} s(T_{j}^{∗}) = 1 + ∑_{j=1}^{k} s(T_{j}) = s(T).

|F(T)| = 1 + ∑_{j=1}^{k−1}(|F(T_{j})| − 1) + |F(T_{k})| = 1 + ∑_{j=1}^{k−1} s(T_{j}) + 1 + s(T_{k}) = 1 + s(T).

Finally, since each P (F(T_{i})), i ∈ [k] is a Dyck path, it follows that the path

uP (F(T_{1}))P (F(T_{2})) ⋯ P (F(T_{k−1}))dP (F(T_{k}))

is also a Dyck path and hence, using the equalities P (F(T_{j})) = u^{s(T_{j}^{∗})}dP (F̃(T_{j})), j ∈ [k − 1], and (i), (iv), we obtain that P (F(T)) is a Dyck path.

In the sequel we will show that k-ary trees can be generated by certain forests of (k − 1)- ary trees. For this, we will introduce a new decomposition of k-ary trees. For T ∈ T_{k}, we denote by Z_{i} the k-th child in T of the i-th (in postorder) vertex of T^{∗}. Clearly, T can be uniquely recovered by attaching each Z_{i} as the k-th child to the i-th (in postorder) vertex of T^{∗}. The trees T^{∗}, Z_{1}, Z_{2}, …, Z_{ν}, where ν = s(T^{∗}), form a decomposition of T called the first component decomposition; (see for example Figure 6).

Proposition 2. For every T ∈ T_{k}, the forest F(T) is the concatenation of the forests T^{∗}, F(Z_{1}), F(Z_{2}), …, F(Z_{ν}).

Figure 6: The first component decomposition of the tree of Figure 2.

Proof. It is enough to show that if X, Y are two trees in F(Z_{i}), F(Z_{j}) respectively then X precedes Y in F(T) if and only if i < j or i = j and X precedes Y in F(Z_{i}).

We will prove this using induction on the size of the tree T.

If T = T_{1}T_{2} ⋯ T_{k}, then it is evident that Z_{ν} = T_{k}.

Clearly, each Z_{i}, i ∈ [ν − 1] is a subtree of a unique T_{ξ_{i}}, ξ_{i} ∈ [k − 1], such that ξ_{i} ≤ ξ_{j} whenever i < j. Then X, Y belong to F(T_{ξ_{i}}), F(T_{ξ_{j}}) respectively and X ≠ T_{ξ_{i}}^{∗}, Y ≠ T_{ξ_{j}}^{∗}. We consider two cases:

1. If ξ_{i} ≠ ξ_{j} then X precedes Y in F(T) if and only if ξ_{i} < ξ_{j} or equivalently i < j.

2. If ξ_{i} = ξ_{j} then X precedes Y in F(T) if and only if X precedes Y in F(T_{ξ_{i}}) or equivalently, by the induction hypothesis i < j or i = j and X precedes Y in F(Z_{i}).

Hence, in every case X precedes Y in F(T) if and only if i < j or i = j and X precedes Y in F(Z_{i}).

From Proposition 2 and relation (4) we obtain a new, simpler expression for P (F(T)), using the Dyck paths P (F(Z_{j})), j ∈ [ν].

P (F(T)) = u^{ν}dP (F(Z_{1}))dP (F(Z_{2})) … dP (F(Z_{ν})), where ν = s(T^{∗}).  (5)

Proposition 3. The mapping T → F(T) is a size preserving bijection between T_{k} and the set of forests F of (k − 1)-ary trees with P (F) ∈ D.

Proof. Given a forest F of (k − 1)-ary trees such that P (F) ∈ D, we will show by induction that there exists a unique tree T ∈ T_{k} such that F = F(T).

Using the first ascent decomposition (3) we have P (F) = u^{ν}dQ_{1}dQ_{2} ⋯ dQ_{ν}, where ν is the size of the first element S of F and Q_{j} ∈ D, for all j ∈ [ν]. Since

∑_{j=1}^{ν}(r(Q_{j}) + 1) = ∑_{j=1}^{ν} r(Q_{j}) + ν = r(P (F)) = s(F) = |F| − 1,

it follows that there exists a sequence of forests (F_{j}), j ∈ [ν], such that F is the concatenation of S, F_{1}, F_{2}, …, F_{ν} and |F_{j}| = r(Q_{j}) + 1,

It follows from relation (4) that P (F_{j}) = Q_{j} and hence it is a Dyck path, for every j ∈ [ν]. Thus, by the induction hypothesis, there exists Z_{j} ∈ T_{k}, j ∈ [ν], such that F_{j} = F(Z_{j}). Then T is the tree constructed by attaching Z_{j} to the j-th (in postorder) vertex of S as its k-th child; from Proposition 2 it follows immediately that F = F(T).

For the proof of the uniqueness, let F(X) = F(T); then T^{∗} = X^{∗}. If T^{∗}, Z_{1}, Z_{2}, …, Z_{ν} and T^{∗}, Y_{1}, Y_{2}, …, Y_{ν} are the first component decompositions of T and X respectively, then since P (F(T)) = P (F(X)), by relation (5) it follows that P (F(Z_{i})) = P (F(Y_{i})), for every i ∈ [ν]. Furthermore, since |F(Z_{i})| = f(P (F(Z_{i}))) + 1 = f(P (F(Y_{i}))) + 1 = |F(Y_{i})| for every i ∈ [ν], by Proposition 2 we obtain that F(Z_{i}) = F(Y_{i}), for every i ∈ [ν]. Thus, by the induction hypothesis, Z_{i} = Y_{i} for each i ∈ [ν], so that T = X.

We close this section with the following algorithmic construction of the tree T ∈ T_{k} such that F(T) = F, where F is a given forest of (k − 1)-ary trees with P (F) ∈ D:

We start with the first tree of F. At each step, we add as the k-th child of the first (in postorder) vertex which does not have a k-th child, the first tree of F that has not already been used. For example, the tree T of Figure 2 can be constructed from the forest of Figure 5 as shown in Figure 7.

Figure 7: Construction of T from F.

4 Generation of k-ary trees from unary trees

In this section we show how every k-ary tree can be uniquely decomposed into a forest of unary trees which leads to a new bijection between the sets T_{k} and D^{(k−1)}. For this, we first introduce a mapping on forests denoted by ( )′.

For every forest F = (T_{1}, T_{2}, …, T_{λ}) of k-ary trees, we define the forest F′ of (k − 1)-ary trees to be the concatenation of the forests F(T_{1}), F(T_{2}), …, F(T_{λ}). Using Proposition 1 (ii), (iii), we deduce the following equalities:

s(F′) = s(F) and |F′| = s(F) + |F|.  (6)

Furthermore, it can be easily checked that if F is the concatenation of the forests F_{1}, F_{2}, …, F_{ρ}, then F′ is the concatenation of the forests F′_{1}, F′_{2}, …, F′_{ρ}.

The following two results establish additional properties of ( )′.

Proposition 4. For any pair of forests F, G, we have that if F′ = G′ then F = G.

Proof. Since |F| = |F′| − s(F′) = |G′| − s(G′) = |G|, we can write

F = (T_{1}, T_{2}, …, T_{λ}) and G = (X_{1}, X_{2}, …, X_{λ}).

We assume that F ≠ G and we choose ρ to be the least element of [λ] such that T_{ρ} ≠ X_{ρ}. Since F′ = G′ and F(T_{ρ}) ≠ F(X_{ρ}), it follows that |F(T_{ρ})| ≠ |F(X_{ρ})|; without loss of generality we assume that |F(T_{ρ})| < |F(X_{ρ})|. Then, there exists a forest H such that F(X_{ρ}) is the concatenation of F(T_{ρ}) and H. It follows that P (F(X_{ρ})) = P (F(T_{ρ}))dP (H) which is not a Dyck path, giving the required contradiction.

Proposition 5. For every forest F, we have that P_{i−1}(F) ∈ D^{(i−1)} if and only if P_{i}(F′) ∈ D^{(i)}.

Proof. Let F = (T_{1}, T_{2}, …, T_{λ}); then

P_{i−1}(F) = u_{i−1}^{s(T_{1})}du_{i−1}^{s(T_{2})}d ⋯ u_{i−1}^{s(T_{λ−1})}du_{i−1}^{s(T_{λ})}

and by relation (4)

P_{i}(F′) = P_{i}(F(T_{1}))dP_{i}(F(T_{2}))d ⋯ P_{i}(F(T_{λ−1}))dP_{i}(F(T_{λ})).

Clearly, since for every j ∈ [λ] the path P (F(T_{j})) is a Dyck path, the path P_{i}(F(T_{j})) lies above the x axis and ends at height (i − 1)s(T_{j}). Furthermore, the fall following P_{i}(F(T_{j})) in the path P_{i}(F′) is at the same height as the fall following the ascent u_{i−1}^{s(T_{j})} in the path P_{i−1}(F), for all j ∈ [λ − 1], giving the required result.

We now have the following result.

Proposition 6. For every forest of (k − 1)-ary trees F such that P_{i}(F) ∈ D^{(i)}, there exists a unique forest G of k-ary trees such that G′ = F and |G| = 1 + (i − 1)s(F).

Proof. Clearly, if F = □, the result holds for G = □, while , if i = 1 the result follows from Proposition 3. Otherwise, since P_{i}(F) ∈ D^{(i)}, the path P (F) starts at the origin with a rise and ends at a point below the x-axis attaining the least possible height; so, there exists a sequence (Q_{j})_{j∈[λ]} of Dyck paths, such that

P (F) = Q_{1}dQ_{2}d ⋯ Q_{λ−1}dQ_{λ}

and Q_{1} ≠ ε. Then, since

|F| = 1 + f(P (F)) = 1 + λ − 1 + ∑_{j=1}^{λ} f(Q_{j}) = ∑_{j=1}^{λ}(r(Q_{j}) + 1),

there exists a unique sequence (F_{j})_{j∈[λ]} of forests of (k−1)-ary trees such that |F_{j}| = r(Q_{j})+1, for all j ∈ [λ] and F is the concatenation of the forests F_{1}, F_{2}, …, F_{λ}. Then, by relation (4), it follows that

P (F) = P (F_{1})dP (F_{2})d ⋯ P (F_{λ−1})dP (F_{λ}).

Since for all j ∈ [λ] we have that f(P (F_{j})) = |F_{j}| − 1 = f(Q_{j}), from the above two expressions of P (F) it follows that P (F_{j}) = Q_{j}. Thus, P (F_{j}) is a Dyck path and by Proposition 3 there exists a unique T_{j} ∈ T_{k} such that F_{j} = F(T_{j}). Then, for G = (T_{1}, T_{2}, …, T_{λ}), we obtain G′ = F.

Now, since P_{i}(F) ∈ D^{(i)} and Q_{j} ∈ D for each j ∈ [λ], we have that

ir(P_{i}(F)) = f(P_{i}(F)) = f(P (F)) = λ−1+∑_{j=1}^{λ} f(Q_{j}) = λ−1+∑_{j=1}^{λ} r(Q_{j}) = λ−1+r(P (F)).

Furthermore, since r(P_{i}(F)) = r(P (F)) = s(F) and |G| = λ, it follows that |G| = 1 + (i − 1)s(F).

The uniqueness of G follows from Proposition 4.

The next result follows directly from Propositions 5 and 6.

Proposition 7. The mapping ( )′ from the set of forests of (k−i+1)-ary trees with P_{i−1}(F) ∈ D^{(i−1)} to the set of forests of (k − i)-ary trees with P_{i}(F) ∈ D^{(i)} where i ≥ 2, is a bijection.

Using the mapping ( )′, for every T ∈ T_{k} and i ∈ [k − 1], we define recursively the forest F^{i}(T) by the relations

F^{0}(T) = T and F^{i}(T) = (F^{i−1}(T))′.

For example, for the tree T of Figure 2 for which F(T) has been already constructed (see Figure 5), we can easily obtain that F^{2}(T) is the forest of Figure 8.

Clearly, the forest F^{i}(T) consists of (k − i)-ary trees. Furthermore, from (6) we obtain inductively the following generalization of equalities (ii), (iii) of Proposition 1:

s(F^{i}(T)) = s(T) and |F^{i}(T)| = is(T) + 1.

Figure 8: The forest F^{2}(T).

In particular, the second equality for i = k − 1 shows that we have a 1-1 correspondence between the leaves of the tree T and the unary trees of F^{k−1}(T).

Using Propositions 5 and 6 we can easily show by induction that P_{i}(F^{i}(T)) ∈ D^{(i)}, for every i ∈ [k − 1]. Furthermore, using Proposition 7 we deduce by induction the following result which is a generalization of Proposition 3.

Proposition 8. For every i ∈ [k − 1], the mapping T → F^{i}(T) is a size preserving bijection between T_{k} and the set of forests F of (k − i)-ary trees with P_{i}(F) ∈ D^{(i)}.

An application of the previous result for i = k−1 gives that the mapping T → F^{k−1}(T ) is a size preserving bijection between T_{k} and the set of forests F of unary trees with P_{k−1}(F) ∈ D^{(k−1)}. Clearly, since any such forest F can be identified with the associated path P_{k−1}(F), we obtain the following result.

Proposition 9. The mapping ϕ : T_{k} → D^{(k−1)} with ϕ(T) = P_{k−1}(F^{k−1}(T)) is a bijection such that s(T) = r(ϕ(T)).

Notice that the classical bijection θ mentioned in Section 2 is different from the bijection ϕ of the previous Proposition. For example, for the tree T of Figure 2 we have

θ(T) = u_{2}u_{2}du_{2}ddddu_{2}ddu_{2}u_{2}ddddu_{2}dddu_{2}dd,

whereas

ϕ(T) = u_{2}u_{2}du_{2}ddu_{2}ddddu_{2}u_{2}ddddu_{2}dddu_{2}dd.

Both bijections use recursion, θ with respect to the size, whereas ϕ with respect to k.

5 Maximal paths of k-ary trees

In this section we show that every k-ary tree can be uniquely expressed by the set of its maximal paths. Furthermore, using this expression, we give an equivalent simple formula for the bijection ϕ.

Let A_{k} be the set of all subsets A of [k]^{∗} (the set of all words on the alphabet [k]) satisfying the following two conditions:

i) If x = ρα ∈ A, where ρ, α ∈ [k]^{∗} and α ≠ ε, then, for all i ∈ [k], the set A contains at least one word of the form ρiγ_{i}, where γ_{i} ∈ [k]^{∗}.

ii) If ρ ∈ A and α ∈ [k]^{∗}, then ρα ∈ A if and only if α = ε.

From the above two conditions, it follows easily that {ε} ∈ A_{k} and ε ∉ A for all A ∈ A_{k} with A ≠ {ε}.

We define recursively the mapping ψ : T_{k} → A_{k} by

ψ(□) = {ε} and ψ(T_{1}T_{2} ⋯ T_{k}) = {iα : α ∈ ψ(T_{i}), i ∈ [k]}.

For example, for the tree T of Figure 2 we have

ψ(T) = {11, 121, 122, 123, 13, 21, 22, 2311, 2312, 2313, 232, 2331, 2332, 2333, 31, 32, 33}.

It is easy to check that ψ is a bijection, such that |ψ(T)| = (k −1)s(T)+1, for all T ∈ T_{k}. Furthermore, the elements of ψ(T) code the maximal paths of T. In fact, the maximal path S = v_{1}v_{2} ⋯ v_{ℓ+1} of T or, equivalently, its associated leaf v_{ℓ+1}, is coded by the word α = a_{1}a_{2} ⋯ a_{ℓ} ∈ ψ(T) if and only if v_{i+1} is the a_{i}-th child of v_{i}, for all i ∈ [ℓ].

Additionally, since |F^{k−1}(T)| = |ψ(T)|, there exists a 1-1 correspondence between the sequences of ψ(T) and the trees of F^{k−1}(T) such that every x ∈ ψ(T) corresponds to a unique unary tree T_{x} of F^{k−1}(T), which is the left path of the leaf which is coded by x. For example, the word x = 2311 of ψ(T) in the tree T of Figure 2 corresponds to the 8-th element of the forest F^{2}(T) of Figure 8.

Using the above expression of k-ary trees, we will give a method for the construction of a (k − 1)-Dyck path from a set A ∈ A_{k} endowed with a total order. Firstly, for each x ∈ [k]^{∗}, we set l(x) to be the number of trailing 1’s of x. Clearly, l(x) = s(T_{x}), for every x ∈ ψ(T).

Proposition 10. Let ⪯ be a partial order on [k]^{∗} satisfying the following conditions:

1. the restriction of ⪯ on A is a total order and min A is the element of A which contains only 1’s,

2. iα ⪯ iβ if and only if α ⪯ β, for all α, β ∈ A and i ∈ [k],

for each A ∈ A_{k}. Then we have that

u_{k−1}^{l(α_{1})}du_{k−1}^{l(α_{2})}d ⋯ u_{k−1}^{l(α_{μ−1})}du_{k−1}^{l(α_{μ})} ∈ D^{(k−1)},

for all A ∈ A_{k}, where A = {α_{1}, α_{2}, …, α_{μ}} and α_{1} ⪯ α_{2} ⪯ ⋯ ⪯ α_{μ}.

Proof. In order to prove that the above path is a (k − 1)-Dyck path, it suffices to prove that

(k − 1) ∑_{\begin{matrix}x∈A \\ x⪯y \end{matrix}} l(x) ≥ |\{x ∈ A : x ⪯ y\}|, and (k − 1) ∑_{x∈A} l(x) = |A| − 1,

where y ∈ A \ {α_{μ}}. We will use induction with respect to the cardinality of A ∈ A_{k}.

For A = {ε}, the result is true. For A ≠ {ε} we will prove only the inequality, since the equality can be proved analogously.

We define A_{i} = {α ∈ [k]^{∗} : iα ∈ A}, for each i ∈ [k]. It is easy to check that A_{i} ∈ A_{k}, for every i ∈ [k]. Furthermore, we define I = {i ∈ [k] : iα ⪯ y for some α ∈ A_{i}}. Obviously, 1 ∈ I. For each i ∈ I, we denote by α_{i} the maximum element of A_{i} with iα_{i} ⪯ y. Then, we have

(k − 1) ∑_{\begin{matrix}x∈A \\ x⪯y \end{matrix}} l(x) = (k − 1) ∑_{i∈I} ∑_{\begin{matrix}α∈A_{i} \\ iα⪯y \end{matrix}} l(iα) = (k − 1) ∑_{i∈I} ∑_{\begin{matrix}α∈A_{i} \\ α⪯α_{i} \end{matrix}} l(iα)

= (k − 1) ∑_{i∈I\\{1\}} ∑_{\begin{matrix}α∈A_{i} \\ α⪯α_{i} \end{matrix}} l(α) + (k − 1)(1 + ∑_{\begin{matrix}α∈A_{1} \\ α⪯α_{1} \end{matrix}} l(α))

= ∑_{i∈I}(k − 1) ∑_{\begin{matrix}α∈A_{i} \\ α⪯α_{i} \end{matrix}} l(α) + (k − 1)

≥ ∑_{i∈I\{k}}(|{α ∈ A_{i} : α ⪯ α_{i}}| − 1) + ∑_{i∈I∩{k}} |{α ∈ A_{i} : α ⪯ α_{i}}| + (k − 1)

= ∑_{i∈I} |{α ∈ A_{i} : α ⪯ α_{i}}| − |I \ {k}| + k − 1 ≥ |{x ∈ A : x ⪯ y}|.

From the previous proposition, it follows that given a partial order “⪯” on [k]^{∗} satisfying conditions 1, 2, we have that

(k − 1) ∑_{j=1}^{m} l(α_{j}) ≥ m, for every m ∈ [μ − 1] and (k − 1) ∑_{j=1}^{μ} l(α_{j}) = μ − 1,

for every set A = {α_{1}, α_{2}, …, α_{μ}} ∈ A_{k} with α_{t} ⪯ α_{s} if and only if t ≤ s. Thus, the mapping χ on A_{k} defined by

χ({ε}) = ε, χ(A) = u_{k−1}^{l(α_{1})}du_{k−1}^{l(α_{2})}d ⋯ u_{k−1}^{l(α_{μ−1})}d

takes values in D^{(k−1)}.

Clearly, this mapping depends on the choice of the partial order “⪯”. If “⪯” is the lexicographic order on [k]^{∗} (which obviously satisfies the conditions of Proposition 10), then the resulting mapping χ may be used in order to give an explicit formula of the bijection θ.

In order to describe the bijection ϕ using the above equivalent expression of k-ary trees, we need an ordering for the elements of each A ∈ A_{k}. Thus we define a partial order on [k]^{∗}, denoted by “⪯”, as follows: If x = ρα and y = ρβ, where ρ is the maximal common initial part (possibly empty) of x and y, then

x ⪯ y ⇔ \begin{cases}α = β = ε, or \\ max α < max β, or \\ max α = max β and first element of α < first element of β. \end{cases}

Clearly, from condition ii) in the definition of A_{k}, it follows that “⪯” is a total order on each A ∈ A_{k}.

For example, the elements of ψ(T) for the tree T of Figure 2 are ordered as follows:

11 ⪯ 121 ⪯ 122 ⪯ 21 ⪯ 22 ⪯ 123 ⪯ 13 ⪯ 2311
⪯ 2312 ⪯ 232 ⪯ 2313 ⪯ 2331 ⪯ 2332 ⪯ 2333 ⪯ 31 ⪯ 32 ⪯ 33.

So, for the set A = ψ(T), we have the following 2-Dyck path:

χ(A) = u_{2}^{2}du_{2}ddu_{2}ddddu_{2}^{2}ddddu_{2}dddu_{2}dd.

Proposition 11. For every k ∈ ℕ^{∗} and T ∈ T_{k}, we have that

χ(ψ(T)) = ϕ(T).

Proof. Using the first component decomposition T^{∗}, Z_{1}, …, Z_{ν}, where ν = s(T^{∗}), of a tree T ∈ T_{k}, it follows inductively using Proposition 2 that F^{k−1}(T) is the concatenation of the forests F^{k−2}(T^{∗}), F^{k−1}(Z_{1}), …, F^{k−1}(Z_{ν}). We will show by induction with respect to k and to the size of the tree, that if x, y ∈ ψ(T) and T_{x}, T_{y} are their associated trees in F^{k−1}(T), then T_{x} precedes T_{y} in F^{k−1}(T) if and only if x ⪯ y.

We consider the following cases:

1. T_{x}, T_{y} are in F^{k−2}(T^{∗}). Then x, y ∈ ψ(T^{∗}) and hence, using the induction hypothesis (with respect to k), we deduce that x ⪯ y.

2. T_{x} is in F^{k−2}(T^{∗}) and T_{y} is in F^{k−1}(Z_{i}), for some i ∈ [ν]. Then x ≺ y, since max x < k = max y.

3. T_{x}, T_{y} are in F^{k−1}(Z_{i}), for some i ∈ [ν]. Then x = ρkα and y = ρkβ, where ρ ∈ [k −1]^{∗} and α, β ∈ [k]^{∗}. It follows that α, β ∈ ψ(Z_{i}) and hence, using the induction hypothesis (with respect to the size of the tree), we deduce that α ⪯ β and therefore x ⪯ y.

4. T_{x} is in F^{k−1}(Z_{i}) and T_{y} is in F^{k−1}(Z_{j}), where i, j ∈ [ν] and i ≠ j. Then i < j, so that the parent of Z_{i} precedes the parent of Z_{j} (in postorder). Thus, x = ρα and y = ρβ, ρ ∈ [k − 1]^{∗} (where ρ is the initial common part of x and y) and α, β ∈ [k]^{∗}. It follows that max α = max β = k and first element of α < first element of β, and hence x ⪯ y.

This shows that in all cases, x ⪯ y.

The converse now follows obviously, since F^{k−1}(T) is totally ordered.

Finally, since l(x) = s(T_{x}), for every x ∈ ψ(T), the (k − 1)-paths χ(ψ(T)) and ϕ(T) have the same ascent sequence and therefore they are identical.

6 Enumerations

In this section, we study some statistics on k-ary trees related to the notions studied in the previous sections.

6.1 Enumeration of T_{k} according to the number of non-empty trees of F^{i}(T)

Given i, k ∈ ℕ^{∗} with i ≤ k − 1 and T ∈ T_{k}, we denote by p_{i,k}(T) the number of non-empty trees of F^{i}(T) and by F_{i,k} the generating function

F_{i,k}(x, y) = ∑_{T ∈T_{k}} x^{s(T)}y^{p_{i,k}(T)}.

It follows that

p_{i,k}(□) = 0 and p_{i,k}(T_{1}T_{2} ⋯ T_{k}) = 1 + ∑_{j=1}^{k} p_{i,k}(T_{j}) − ∑_{j=1}^{k−i}[T_{j} ≠ □],

where [P] is the well known Iverson notation defined by [P] = \begin{cases}1, & if P is true; \\ 0, & if P is false. \end{cases}

The above equality can be proved by induction (with respect to k). Indeed, since the forest F(T) is the concatenation of T^{∗}, F̃(T_{1}), F̃(T_{2}), …, F̃(T_{k−1}), F(T_{k}), where T^{∗} = T_{1}^{∗}T_{2}^{∗} ⋯ T_{k−1}^{∗}, we can easily check that the forest F^{i}(T) is the concatenation of

F^{i−1}(T^{∗}), F̃^{i}(T_{1}), F̃^{i}(T_{2}), …, F̃^{i}(T_{k−1}), F^{i}(T_{k}).

Furthermore, using the induction hypothesis for the tree T^{∗} ∈ T_{k−1}, we obtain that

p_{i,k}(T) = p_{i−1,k−1}(T^{∗}) + ∑_{j=1}^{k−1}(p_{i,k}(T_{j}) − p_{i−1,k−1}(T_{j}^{∗})) + p_{i,k}(T_{k})

= 1 + ∑_{j=1}^{k−1} p_{i−1,k−1}(T_{j}^{∗}) − ∑_{j=1}^{k−1−(i−1)}[T_{j}^{∗} ≠ □] + ∑_{j=1}^{k−1} p_{i,k}(T_{j}) − ∑_{j=1}^{k−1} p_{i−1,k−1}(T_{j}^{∗}) + p_{i,k}(T_{k})

= 1 + ∑_{j=1}^{k} p_{i,k}(T_{j}) − ∑_{j=1}^{k−i}[T_{j} ≠ □].

From the above relation, it follows that the generating function F_{i,k}(x, y) satisfies the following equation:

F_{i,k}(x, y) = 1 + xy(F_{i,k}(x, y))^{i}(1 + \frac{1}{y}(F_{i,k}(x, y) − 1))^{k−i}.

Using the Lagrange inversion formula, we obtain the following result.

Proposition 12. The number of all k-ary trees of size n for which the forest F^{i}(T), i ∈ [k − 1], contains exactly j non-empty trees is equal to

[x^{n}y^{j}]F_{i,k} = \frac{1}{n}\binom{ni}{j − 1}\binom{(k − i)n}{n − j}.

The above result is of special interest for the cases i = k−1 and i = 1. In particular, using the bijection φ, we can easily check that p_{k−1,k}(T) = N_{ud}(ϕ(T)), where N_{ud}(ϕ(T)) denotes the number of ud’s (peaks) in ϕ(T); thus the above two parameters are equidistributed, which implies that the number of (k − 1)-Dyck paths having n rises and j peaks is equal to \frac{1}{n} \binom{(k−1)n}{j−1}\binom{n}{j}.

We note that since the number p_{k−1,k}(T)−1, which counts the non-empty trees in F^{k−1}(T) other than the first one, is equal to N_{du}(ϕ(T)) we can easily deduce that the number of (k − 1)-Dyck paths with n rises and j valleys is equal to \frac{1}{n} \binom{(k−1)n}{j}\binom{n}{j+1}.

Furthermore, since |F^{k−1}(T)| = (k−1)s(T)+1, we obtain that the number of empty trees in F^{k−1}(T) other than the last one (which is always empty) is equal to (k−1)s(T)−p_{k−1,k}(T). Since we can easily check that this number is equal to N_{dd}(ϕ(T)), we deduce that the number of (k − 1)-Dyck paths having n rises and j doublefalls is equal to \frac{1}{n} \binom{(k−1)n}{j+1}\binom{n}{(k−1)n−j}.

On the other hand, using a variation θ′ of θ defined by

θ′(□) = ε and θ′(T_{1}T_{2} ⋯ T_{k}) = uθ′(T_{k})dθ′(T_{k−1}) ⋯ dθ′(T_{2})dθ′(T_{1}),

we can easily check by induction that N_{uu}(θ′(T)) = p_{1,k}(T) − [T ≠ □], for every T ∈ T_{k}. From this equality, it follows easily that the number of all (k − 1)-Dyck paths having n rises and j doublerises is equal to \frac{1}{n} \binom{n}{j}\binom{(k−1)n}{n−j−1}.

S. Heubach et al. [6] give analogous results on similar generalized Dyck paths.

6.2 Enumeration according to the size of the first element of F^{i}(T)

For every T ∈ T_{k} we denote by q_{i,k}(T), i ∈ [k − 1], the size of the first element of F^{i}(T) and G_{i,k}(x, y) the generating function

G_{i,k}(x, y) = ∑_{T ∈T_{k}} x^{s(T)}y^{q_{i,k}(T)}.

It follows that

q_{i,k}(□) = 0 and q_{i,k}(T_{1}T_{2} ⋯ T_{k}) = 1 + ∑_{j=1}^{k−i} q_{i,k}(T_{j}).

The above equality can be proved easily by induction (with respect to k), using the equality q_{i,k}(T) = q_{i−1,k−1}(T^{∗}).

From the above relation, it follows that the generating function G_{i,k}(x, y) satisfies the following equation:

G_{i,k}(x, y) = 1 + xy(G_{i,k}(x, 1))^{i}(G_{i,k}(x, y))^{k−i} = 1 + xy(C_{k}(x))^{i}(G_{i,k}(x, y))^{k−i}.

Using the Lagrange inversion formula, we obtain the following result.

Proposition 13. The number of all k-ary trees T of size n, for which the first element of F^{i}(T), i ∈ [k − 1], has size j is equal to

[x^{n}y^{j}]G_{i,k}(x, y) = \frac{i}{(n − j)k + ij} \binom{(n − j)k + ij}{n − j}\binom{(k − i)j}{j − 1}.

For the case i = k − 1, using the bijection φ, we can easily check that q_{k−1,k}(T) is the length of the first ascent of ϕ(T), thus the number of (k − 1)-Dyck paths having n rises and length of first ascent equal to j is \frac{(k−1)j}{kn−j} \binom{kn−j}{n−j}.

References

[1] H. Ahrabian and A. Nowzari-Dalini, Parallel generation of t-ary trees in A-order, Computer J. 50 (2007), 581–588.

[2] E. Deutsch, Dyck path enumeration, Discrete Math. 204 (1999), 167–202.

[3] M. C. Er, Lexicographic listing and ranking of t-ary trees, Computer J. 30 (1987), 569–572.

[4] M. C. Er, Efficient generation of k-ary trees in natural order, Computer J. 35 (1992), 306–308.

[5] I. M. Gessel and S. Seo, A refinement of Cayley’s formula for trees, Electron. J. Combin. 11 (2006), #R2.

[6] S. Heubach, N. Y. Li and T. Mansour, Staircase tilings and k-Catalan structures, Discrete Math. 308 (2008), 5954–5964.

[7] M. Jani, R. G. Rieper, and M. Zeleke, Enumeration of K-trees and applications, Ann. Comb. 6 (2002), 375–382.

[8] D. E. Knuth. The Art of Computer Programming. Fundamental Algorithms, Vol. 1, Addison-Wesley, 3rd edition, 1997.

[9] J. F. Korsh, A-order generation of k-ary trees with 4k − 4 letter alphabet, J. Inform. Opt. Sci. 16 (1995), 557–567.

[10] J. F. Korsh and P. LaFollette, Loopless generation of Gray codes for k-ary trees, Inform. Process. Lett. 70 (1999), 7–11.

[11] J. F. Korsh and S. Lipschutz, Shifts and loopless generation of k-ary trees, Inform. Process. Lett. 65 (1998), 235–240.

[12] T. Mansour, M. Schork and S. Severini, Noncrossing normal ordering for functions of boson operators, Internat. J. Theoret. Phys. 47 (2008), 832–849.

[13] D. Merlini, R. Sprugnoli and M. C. Verri, The tennis ball problem, J. Combin. Theory Ser. A 99 (2002), 307–344.

[14] A. Mier and M. Noy, A solution to the tennis ball problem, Theoret. Comput. Sci. 346 (2005), 254–264.

[15] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, 2009.

[16] J. Pallo, Generating trees with n nodes and m leaves, Int. J. Comput. Math. 21 (1987), 133–144.

[17] D. Roelants van Baonaigien and F. Ruskey, Generating t-ary trees in A-order, Inform. Process. Lett. 27 (1988), 205–213.

[18] F. Ruskey, Generating t-ary trees lexicographically, SIAM J. Comput. 7 (1978), 424– 439.

[19] G. Seroussi, On the number of t-ary trees with a given path length, Algorithmica 46 (2006), 557–565.

[20] L. Xiang, K. Ushijima and C. Tang, On generating k-ary trees in computer representation, Inform. Process. Lett. 77 (2001), 231–238.

[21] S. Zaks, Generation and ranking of k-ary trees, Inform. Process. Lett. 14 (1982), 44–48.

[22] M. Zeleke and M. Jani, k-trees and Catalan identities, Congr. Numer. 165 (2003), 39–49.

2000 Mathematics Subject Classification: Primary 05A15; Secondary 05A19. Keywords: Generalized Dyck words, k-ary trees, k-Catalan numbers.

(Concerned with sequence \underline{A000108}.)

Received July 14 2009; revised version received November 3 2009. Published in Journal of Integer Sequences, November 4 2009.

Return to Journal of Integer Sequences home page.