Ranking and Unranking of a Generalized Dyck Language and the

Application to the Generation of Random Trees

Jens Liebehenschel Johann Wolfgang Goethe-Universität, Frankfurt am Main Fachbereich Informatik D-60054 Frankfurt am Main, Germany e-mail: jens@sads.informatik.uni-frankfurt.de

Abstract

Given two disjoint alphabets T_{[} and T_{]} and a relation R ⊆ T_{[} × T_{]}, the generalized Dyck language D^{R} over T_{[} ∪ T_{]} consists of all words w ∈ (T_{[} ∪ T_{]})^{⋆} which are equivalent to the empty word ε under the congruence δ defined by x y ≡ ε mod δ for all (x, y) ∈ R. If the Dyck words are arranged according to the lexicographical order, then ranking means to determine the rank, i. e. the position, of a Dyck word. Unranking creates the Dyck word from its position. We present a ranking and an unranking algorithm for the generalized Dyck language. Given a Dyck word, the ranking algorithm reads a prefix as short as possible to compute the rank. Thus, this algorithm is optimal with respect to that mesure. The unranking algorithm creates the Dyck word symbol by symbol from left to right. Further, we analyze the ranking algorithm. For the computation of the rank of a Dyck word for arbitrary R, we compute the s-th moments of the random variable describing the length of the prefix to be read. No computation is necessary for the analysis of the unranking algorithm, because the whole Dyck word has to be created. The generalized Dyck language can be used for the coding of trees. Not only the shape of the tree is coded but also its labels of the nodes and/or edges. The algorithms discussed here can be used for the ranking and unranking of different types of trees. With a random number generator and the unranking algorithm we are able to generate random trees with diverse properties. Some classes of labelled trees will be discussed. Keywords: Dyck language, ranking, unranking, random trees, lexicographical order, one-to-one correspondence, average-case analysis.

1 Introduction and Basic Definitions

In this paper we examine the generalized Dyck language that was introduced in [Ke96b]. In comparison with the normal Dyck language, the generalized Dyck language has more than only one type of brackets. An ordering on the alphabet will be extended to an ordering on the Dyck words, called lexicographical order. In [Li98], an algorithm for the generation of all Dyck words according to their lexicographical order was presented. Following a frequently used method [Ke98], the algorithm computes from one Dyck word its successor according to the lexicographical order by reading and changing a suffix of the Dyck word. The algorithm works without any knowledge about the Dyck words generated before. In general, the length of the suffix to be read and changed is as short as possible, if the words are generated according to their lexicographical order. The algorithm presented in [Li98] is optimal with respect to the length of the suffix to be read and changed. As there is a connection between [Li98] and this paper, we consider the Dyck words to be ordered lexicographically in this paper, too.

There is a nice property of lexicographically ordered lists of words: Normally, one can find a simple algorithm to obtain a list of shorter words by deleting words and shortening the remaining words, such that the words in this list are also arranged according to the lexicographical order. This is another reason for using the lexicographical order here. Given a set of ordered words, every word has a position that is called rank; the computation of the rank is called ranking. Unranking is the inverse operation, i. e. the generation of a word from its position. First, we introduce the generalized Dyck language and the lexicographical order, then we give a short example. In the next section, the ranking and unranking algorithms are presented. In Section 3, the algorithms are analyzed. In Section 4, we give an application for the unranking algorithm of Dyck words: The generation of random trees for several classes of labelled trees. Various representations of the shape of trees are known, for example the integer sequences: level-representation, leaf-representation and leaf-level-representation, e. g. [Ke98]. These representations do not allow to code the labels of the nodes and/or edges. Thus, the labels have to be coded in an additional sequence. Another possibility to code trees is the normal Dyck language, e. g. [Za80]. In Section 4, we will see that the generalized Dyck language is a handy coding for several classes of labelled trees, because the shape and the labels of the tree are coded in a Dyck word, not in two independent parts, one for coding the shape of the tree, the other for the representation of its labels. Nevertheless, the structure of the tree and its labels can be determined from its coding in a very simple way using a unique factorization of Dyck words. Definition 1: Let t_{1}, t_{2} ∈ ℕ and T_{[} := {[_{1}, [_{2}, …, [_{t_{1}}} (resp. T_{]} := {]_{1},]_{2}, …,]_{t_{2}}}) be the set of opening (resp. closing) brackets. Let |S| be the cardinality of the set S, so |T_{[} | = t_{1} and |T_{]} | = t_{2}. With T := T_{[} ∪ T_{]} and a relation R ⊆ T_{[} × T_{]} we obtain the generalized Dyck language associated with R by D^{R} := {w ∈ T^{⋆} | w ≡ ε mod δ} , where ε denotes the empty word and δ is the congruence over T which is defined by (∀[_{a},]_{b} ∈ T )([_{a}]_{b} ≡ ε mod δ ⟺ ([_{a},]_{b}) ∈ R). The set of all Dyck words of length 2n is given by D_{2n}^{R} := D^{R} ∩ T^{2n}. _{□} Remark 1: Obviously, to each opening (resp. closing) bracket there is a unique corresponding closing (resp. opening) bracket in every Dyck word w ∈ D^{R}. The closing bracket corresponding to an opening bracket in a Dyck word w ∈ D^{R} can be found by searching for the first closing bracket behind the shortest word w_{2} ∈ D^{R} (w_{2} might be ε) on the right side of the opening bracket. If the opening (resp. its corresponding closing) bracket is [_{a} (resp. ]_{b}) and ([_{a},]_{b}) ∈ R, we have w = w_{1} [_{a} w_{2} ]_{b} w_{3} with w_{1} w_{3}, w_{2} ∈ D^{R}. The opening bracket corresponding to a closing bracket in a Dyck word can be found in an analogous way. Definition 2: Let close^{R}([_{a}) := {]_{b} | ([_{a},]_{b}) ∈ R} be the set of all closing brackets corresponding to a given opening bracket according to the relation R. _{□} Definition 3: Let <_{lex}⊆ T × T be an irreflexive linear ordering on T. The lexicographical order ≺_{lex} over T^{+} is defined as the extension of <_{lex} to ≺_{lex}⊆ T^{+} × T^{+} by x ≺_{lex} y :⇔ (∃z ∈ T^{+}) (xz = y) ∨ (∃ (u, x̃, ỹ, v, ṽ) ∈ T^{⋆3} × T^{2}) (x = u v x̃ ∧ y = u ṽỹ ∧ v <_{lex} ṽ) [Ke98]. _{□} Note that in this paper we consider the lexicographical order on Dyck words of length 2n only.

We use the following ordering on T:

[_{|T_{[} |} <_{lex} … <_{lex} [_{1} <_{lex} ]_{1} <_{lex} … <_{lex} ]_{|T_{]} |} .

If all Dyck words of D_{2n}^{R} are arranged according to the lexicographical order, then ranking means to determine the rank, i. e. the position of a Dyck word w ∈ D_{2n}^{R}. The rank of w is the number of lexicographically smaller Dyck words in the generalized Dyck language, i. e. rank(w) := |{w̃ | w̃ ∈ D_{2n}^{R} ∧ w̃ ≺_{lex} w}|. Thus, we immediately get 0 ≤ rank(w) < |D_{2n}^{R}|. Given the rank of w ∈ D_{2n}^{R}, unranking computes w. Let us demonstrate the above definitions by a simple example. Example 1: Let T := {[_{1}, [_{2},]_{1},]_{2}}, R := {([_{1},]_{1}), ([_{1},]_{2}), ([_{2},]_{2})} and n := 2. The relation R implies close^{R}([_{1}) = {]_{1},]_{2}} and close^{R}([_{2}) = {]_{2}}. We obtain the ordering on the alphabet [_{2} <_{lex} [_{1} <_{lex} ]_{1} <_{lex} ]_{2}. In Figure 1 all Dyck words of this example are arranged lexicographically. Considering the rank of the Dyck words, we find rank([_{2} [_{2} ]_{2} ]_{2}) = 0, rank([_{1} [_{1} ]_{2} ]_{1}) = 10 and rank([_{1} ]_{2} [_{1} ]_{2}) = 17 = |D_{4}^{R}| − 1, for example.

[_{2} [_{2} ]_{2} ]_{2} ≺_{lex} [_{2} [_{1} ]_{1} ]_{2} ≺_{lex} [_{2} [_{1} ]_{2} ]_{2} ≺_{lex} [_{2} ]_{2} [_{2} ]_{2} ≺_{lex} [_{2} ]_{2} [_{1} ]_{1} ≺_{lex} [_{2} ]_{2} [_{1} ]_{2} ≺_{lex} [_{1} [_{2} ]_{2} ]_{1} ≺_{lex} [_{1} [_{2} ]_{2} ]_{2} ≺_{lex} [_{1} [_{1} ]_{1} ]_{1} ≺_{lex} [_{1} [_{1} ]_{1} ]_{2} ≺_{lex} [_{1} [_{1} ]_{2} ]_{1} ≺_{lex} [_{1} [_{1} ]_{2} ]_{2} ≺_{lex} [_{1} ]_{1} [_{2} ]_{2} ≺_{lex} [_{1} ]_{1} [_{1} ]_{1} ≺_{lex} [_{1} ]_{1} [_{1} ]_{2} ≺_{lex} [_{1} ]_{2} [_{2} ]_{2} ≺_{lex} [_{1} ]_{2} [_{1} ]_{1} ≺_{lex} [_{1} ]_{2} [_{1} ]_{2}

Figure 1: All Dyck words of Example 1 arranged according to the lexicographical order ≺_{lex}.

In the introduction we mentioned that it is often possible to create a list of lexicographically ordered words from a list of longer words by deleting words and performing some operation on the remaining words. We will now explain, how to modify the lexicographically ordered list of all Dyck words in D_{2n}^{R} to obtain all words in D_{2n−2}^{R} arranged according to the lexicographical order (for n ≥ 1). In the first step, we delete all Dyck words that do not end with a pair of brackets. Then, we discard the rightmost pair of brackets from the remaining words. In the final step, all duplicates have to be cancelled. If any duplicates exist, then they are consecutive words in the list, thus it is simple to find duplicates. Applying these three steps to the list in Figure 1, we obtain all Dyck words in D_{2}^{R} with R := {([_{1},]_{1}), ([_{1},]_{2}), ([_{2},]_{2})}: [_{2} ]_{2} ≺_{lex} [_{1} ]_{1} ≺_{lex} [_{1} ]_{2} .

2 Ranking and Unranking Algorithm

In this section we will present a ranking algorithm for the generalized Dyck language D_{2n}^{R} as well as an unranking algorithm that creates the Dyck word by reversing the steps carried out by the ranking algorithm. Since a Dyck word’s rank is equal to the number of lexicographically smaller Dyck words, the ranking algorithm needs to determine that number. It follows the familiar practice and reads the Dyck word from left to right. As shown in the general approach to ranking and unranking [Li97], the algorithm has to go on reading until there is exactly one continuation to a word of the language. In that case the symbols not read so far are uniquely determined by the symbols read. Given a Dyck word w = w_{0} … w_{2n−1}, we compute the number of lexicographically smaller words by

rank(w) := ∑_{i=0}^{2n−1} A_{i} ,

where A_{i} := |{w̃_{0} … w̃_{2n−1} ∈ D_{2n}^{R} | w̃_{0} … w̃_{i−1} = w_{0} … w_{i−1} ∧ w̃_{i} <_{lex} w_{i}}|. Note that A_{i} is the number of Dyck words with the same prefix of length i as w and a smaller symbol at the right of that common prefix than in w. Furthermore, each A_{i}, 0 ≤ i ≤ 2n − 1, can be computed by reading the first i symbols of w, so that the algorithm can compute the rank by reading the Dyck word from left to right. If the shortest prefix with a unique continuation is read, the algorithm presented here does not read another symbol. So, it is optimal with respect to the number of symbols to be read from left to right. Let j be the length of that shortest prefix with a unique continuation. We immediately find 0 ≤ j ≤ 2n. Obviously, our algorithm is not able to compute A_{i}, j ≤ i ≤ 2n − 1, because it does not read the suffix w_{j} … w_{2n−1} of w. The computation of A_{i}, j ≤ i ≤ 2n − 1, is not needed, because that suffix w_{j} … w_{2n−1} is a unique continuation of the prefix read to a Dyck word in D_{2n}^{R}, thus we get A_{i} = 0, j ≤ i ≤ 2n − 1, by the definition of A_{i}. Now, we have the fundamentals for the computation of the rank of a Dyck word w. The algorithm proceeds as follows: It reads w from left to right. For each position i, 0 ≤ i ≤ 2n − 1, is checked, whether exactly one continuation to a Dyck word of length 2n exists. That is the case, iff either all n opening brackets have been read and each of these corresponds to one closing bracket only or (n − 1) opening and (n − 1) closing brackets have been read and the relation contains only one pair of brackets. If such a unique continuation exists, then no more symbols have to be read, as we have seen before. If not, then the algorithm has to compute A_{i}, whereby it is necessary to distinguish between opening and closing brackets:

(i) For an opening bracket, the number of Dyck words with the same prefix as w and a smaller opening bracket at the current position than in w have to be added to the rank.

(ii) For a closing bracket, the number of Dyck words with the same prefix as w and an opening bracket at the current position have to be added to the rank as well as the number of Dyck words with a smaller closing bracket than in w – in consideration of the corresponding opening bracket.

Thus, it is necessary to know the opening bracket corresponding to each closing bracket. For that purpose the algorithms make use of a stack with the operations push and pop. Furthermore, the algorithms need to compute the number of continuations of a Dyck word’s prefix to a Dyck word of length 2n. Therefore, let us recall the well-known one-to-one correspondence between Dyck words and paths in the lattice given in Figure 2. Thereby, an up-segment ↗ (resp. down-segment ↘) corresponds to an opening (resp. closing) bracket. Since we have a correspondence between opening and closing brackets (see Remark 1), there must be a correspondence between up-segments and down-segments of a path in the lattice. To each up-segment of any path there is a corresponding down-segment and vice versa: The down-segment (resp. up-segment) corresponding to an up-segment (resp. down-segment) is the next segment on the right (resp. left) side in the same row. Thus, each Dyck word of length 2n corresponds to a path from (0, 0) to (2n, 0). The segments are labelled by the symbols of the alphabet; the labels of up-segments (resp. down-segments) are opening (resp. closing) brackets. Obviously, an upsegment and its corresponding down-segment must be labelled by some [_{a} and ]_{b} with ([_{a},]_{b}) ∈ R.

[figure: .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .]_{0 1 2 3 4 5 6 7 8 9 10 2n-2 2n-1 2n  i}^{0}^{1}^{2}^{3}^{4}^{5}^{n-1}^{n}^{j}  ^{(n,n)}  ^{(i,j)}  ^{(i+1,j+1)}^{(i+1,j−1)} [_{a} ]_{b}

Figure 2: One-to-one correspondence between Dyck words of length 2n and the paths from (0, 0) to (2n, 0).

Note that the number of paths from (0, 0) to (i, j) in the lattice is given by the ballot number [CRS71]

p(i, j) = \frac{j + 1}{i + 1}\binom{i + 1}{\frac{1}{2}(i + j) + 1} = \binom{i}{\frac{1}{2}(i − j)} − \binom{i}{\frac{1}{2}(i − j) − 1} .  (1)

Now, the number of continuations can be computed by p and two other factors, one for the number of possibilities for the closing brackets not read so far and one for the pairs of brackets not read so far. The number of paths from (i, j) to (2n, 0) multiplied by those factors described above is given by:

q(i, j) := p(2n − i, j) close |R|^{\frac{2n−i−j}{2}} ,

where close is a variable in the algorithms. The variables used in the ranking algorithm will be explained now.

• up : Number of opening brackets (and up-segments).

• down : Number of closing brackets (and down-segments).

• close := ∏_{j=0}^{k−1} |close^{R}(w̃_{j})|, if w_{0} … w_{i} ≡ w̃_{0} … w̃_{k−1} mod δ ∧ w_{0} … w_{i} is read

in the algorithm ∧ w̃_{0} … w̃_{k−1} ∈ (T_{[})^{k}.

Note that close is the product of the numbers of closing brackets in R corresponding to each opening bracket read without its corresponding closing bracket read so far, i. e. the number of possibilities to complete the prefix read to a Dyck word in D^{R} by appending closing brackets only. This variable is needed for the function q and will be recomputed for each symbol being read in both algorithms.

• corr cl br[a − 1] := |close^{R}([_{a})|, 1 ≤ a ≤ |T_{[}|.

• corr cl br sm br[a − 1] := ∑_{l=1}^{a−1} |close^{R}([_{l})|, 1 ≤ a ≤ |T_{[}|.

• sm corr cl br[a − 1][b − 1] := |{x | x ∈ close^{R}([_{a}) ∧ x <_{lex} ]_{b}}|, 1 ≤ a ≤ |T_{[}|, 1 ≤ b ≤ |T_{]}|.

Note that the arrays corr cl br and corr cl br sm br and the matrix sm corr cl br can be precomputed in O(|T_{[}| |T_{]}|). This amount of time is constant with respect to the length of the words 2n, because the variables depend on the relation R only. We code the brackets in integers in the ranking and unranking algorithms; the opening bracket of type a (resp. closing bracket of type b) is coded in the integer −a (resp. b). Note that w = w[0] … w[2n−1] is an array of integers in the algorithm. The formal ranking algorithm is given as follows.

function rank (w : dyck word)

begin rank := 0 up := 0 down := 0 close := 1 i := 0 while i < 2n do

begin /⋆ check if a unique continuation exists ⋆/ if (up = n and close = 1) or

(|R| = 1 and up = n − 1 and down = n − 1) then /⋆ do not continue reading the Dyck word ⋆/ i := 2n

else

begin

if w[i] < 0 then

begin /⋆ w[i] is an opening bracket ⋆/ rank := rank + corr cl br sm br[−w[i] − 1] ·

q(i + 1, i + 1 − (2 · down))

push(−w[i]) close := close · corr cl br[−w[i] − 1] up := up + 1

end else

begin /⋆ w[i] is a closing bracket ⋆/ rank := rank + |R| · q(i + 1, i + 1 − (2 · down)) j := pop() close := \frac{close}{corr cl br[j−1]} rank := rank + sm corr cl br[j − 1][w[i] − 1] ·

q(i + 1, i − 1 − (2 · down))

down := down + 1 end

i := i + 1 end

end end;

Algorithm 1: Ranking algorithm for the generalized Dyck language D_{2n}^{R}.

The unranking algorithm reverses the steps made by the ranking algorithm. It creates the word successively from left to right. The algorithm has to determine for each position, whether the current symbol is either an opening or a closing bracket.

For that purpose, we compute the number of Dyck words with the actual prefix and an opening bracket as the current symbol (= |R| · k, where k = q(i + 1, i + 1 − (2 · down))). If the current value of rank of the Dyck word in question is smaller than this number (rank < |R| · k), then the actual symbol is an opening bracket, otherwise it is a closing bracket. Afterwards, the type of that bracket has to be computed. Further, a recomputation of the rank is necessary; this corresponds to the stepwise computation of the rank (A_{i}, 0 ≤ i ≤ 2n − 1) in the ranking algorithm. To compute the type of the opening or closing bracket, two more variables are needed by the unranking algorithm:

• op br[l − 1] : opening bracket of the l-th pair of brackets of the relation R according to the lexicographical order on the pairs of brackets, 1 ≤ l ≤ |R|.

• cl br[a−1][l −1] : l-th closing bracket that corresponds to [_{a} in the relation R according to the ordering on the alphabet, 1 ≤ a ≤ |T_{[}|, 1 ≤ l ≤ |close^{R}([_{a})|.

Again, the array op br and the matrix cl br can be precomputed in O(|T_{[}| |T_{]}|). Now, let us have a look at the formal unranking algorithm.

function unrank (rank : integer)

begin down := 0 close := 1 i := 0 while i < 2n do

begin /⋆ |R| · k = number of Dyck words with the actual prefix ⋆/ /⋆ and an opening bracket as the current symbol ⋆/ k := q(i + 1, i + 1 − (2 · down)) if rank < |R| · k then

begin /⋆ unrank[i] is an opening bracket ⋆/ unrank[i] := op br[⌊\frac{rank}{k} ⌋] rank := rank − corr cl br sm br[−unrank[i] − 1] · k push(−unrank[i]) close := close · corr cl br[−unrank[i] − 1]

end else

begin /⋆ unrank[i] is a closing bracket ⋆/ rank := rank − |R| · k j := pop() close := \frac{close}{corr cl br[j−1]} k := q(i + 1, i − 1 − (2 · down)) unrank[i] := cl br[j − 1][⌊\frac{rank}{k} ⌋] rank := rank − sm corr cl br[j − 1][unrank[i] − 1] · k down := down + 1

end i := i + 1

end end;

Algorithm 2: Unranking algorithm for the generalized Dyck language D_{2n}^{R}.

Let us have a look at the costs per symbol in the algorithms now. The critical part in both algorithms is the computation of the values q(i, j) for 0 ≤ i ≤ 2n and 0 ≤ j ≤ min(i, 2n−i). In order to compute the costs for q(i, j), we need to compute the costs for the computation of the binomial coefficient in p(2n−i, j) and the costs for the computation of the power of |R|. There are two possibilities to obtain a constant amount of time for each symbol read or created, respectively:

(i) The binomial coefficients can be precomputed in O(n^{2}) by computing Pascal’s triangle and the numbers |R|^{i}, 0 ≤ i ≤ n, can be precomputed in O(n) by successive multiplications of |R|. Having precomputed these values once (in O(n^{2})), q can be computed in O(1). This is the method preferred for a frequent use of the ranking and unranking algorithms.

(ii) If one pass of the loop requires the computation of q(i, j), then the next pass requires the computation of one or two values of q(i + 1, j + 1), q(i + 1, j − 1) and q(i + 1, j − 3). With the formulae

q(i + 1, j + 1) = q(i, j) \frac{1}{2|R|} \frac{j + 2}{j + 1} \frac{2n − i − j}{2n − i} ,
q(i + 1, j − 1) = q(i, j) \frac{1}{2} \frac{j}{j + 1} \frac{2n − i + j + 2}{2n − i} ,
q(i + 1, j − 3) = q(i, j) \frac{|R|}{2} \frac{j − 2}{j + 1} \frac{2n − i + j}{2n − i} \frac{2n − i + j + 2}{2n − i − j + 2} ,

we are able to compute q in O(1), too. This method is preferred in the case of few executions of the algorithms. The implementation of this method requires some modifications of the algorithms. These modifications are omitted here for the sake of a clear presentation.

Thus, the use of one of the strategies mentioned above leads to a constant amount of time per symbol read or created, respectively.

3 Analysis of the Algorithms

In this section we analyze the average number of symbols to be read by our ranking algorithm and the average number of symbols to be created by the unranking algorithm. The analysis of the unranking algorithm does not require any computation, because the algorithm always has to create the whole Dyck word, so the number of symbols to create is equal to 2n for every w ∈ D_{2n}^{R}. Thus, the mean value is equal to 2n and the variance is equal to 0. Since the ranking algorithm reads the shortest prefix, that is long enough to compute the rank of the Dyck word, we can analyze the number of symbols to be read using the general approach to ranking and unranking [Li97]. Let X_{pref}(D_{2n}^{R}) be the random variable describing the length of the shortest prefix to be read in order to rank a Dyck word. The mean value μ_{pref}(D_{2n}^{R}) and the variance σ_{pref}^{2}(D_{2n}^{R}) of X_{pref}(D_{2n}^{R}) are given by:

μ_{pref}(D_{2n}^{R}) = 𝔼[X_{pref}^{1}(D_{2n}^{R})] and
σ_{pref}^{2}(D_{2n}^{R}) = 𝔼[X_{pref}^{2}(D_{2n}^{R})] − 𝔼[X_{pref}^{1}(D_{2n}^{R})]^{2} .

We obtain the s-th moments, s ≥ 1, of X_{pref}(D_{2n}^{R}) by [Li97]:

𝔼[X_{pref}^{s}(D_{2n}^{R})]
:= (2n)^{s} − |D_{2n}^{R}|^{−1} ( ∑_{k=1}^{2n−1} ((k + 1)^{s} − k^{s}) |INIT_{k}^{1}(D_{2n}^{R})| + δ_{|D_{2n}^{R}|,1}) , (2)

where

INIT_{k}^{1}(D_{2n}^{R}) := {u | u v ∈ D_{2n}^{R} ∧ u ∈ T^{k} ∧ |{u ṽ ∈ D_{2n}^{R} | ṽ ∈ T^{2n−k}}| = 1}

is the set of prefixes of length k with a unique continuation to a word belonging to D_{2n}^{R} and δ is Kronecker’s delta. Again, we need a criterion for a unique continuation of a Dyck word’s prefix. Let us formalize the condition for a unique continuation that has been given in Section 2. Regarding the lattice in Figure 2, we see that a unique continuation to (2n, 0) exists from all points of {(n + l, n − l) | 0 ≤ l ≤ n}, if the labels of all down-segments are known; in other words, all opening brackets are read and the types of the closing brackets not read so far can be determined with knowledge of the prefix read. Moreover, a unique continuation exists from (2n − 2, 0), if the labels of the last two segments are known, i. e. if only one pair of brackets is not read so far and |R| = 1. We can compute the cardinality of INIT_{k}^{1}(D_{2n}^{R}), 1 ≤ k < 2n, now:

|INIT_{k}^{1}(D_{2n}^{R})|

= \{ \begin{matrix}0 & if & 1 ≤ k ≤ n − 1 \\ p(k, 2n − k) |T_{[}^{1}|^{2n−k} |R|^{k−n} & if & n ≤ k ≤ 2n − 3 \\ p(2n − 2, 2) + p(2n − 2, 0) & if & k = 2n − 2 ∧ |R| = 1 \\ p(2n − 2, 2) |T_{[}^{1}|^{2} |R|^{n−2} & if & k = 2n − 2 ∧ |R| ≥ 2 \\ p(2n − 1, 1) |T_{[}^{1}| |R|^{n−1} & if & k = 2n − 1 \end{matrix} . (3)

Here, T_{[}^{1} := {x | x ∈ T_{[} ∧ |close^{R}(x)| = 1} is the set of opening brackets with only one corresponding closing bracket according to R and p is given in (1). Before computing the s-th moments of X_{pref}(D_{2n}^{R}), we prove the following technical lemma which gives us the asymptotic behaviour for two types of sums. Lemma 1: The asymptotics for both sums are valid for n → ∞.

(i) The following asymptotic holds for s ∈ ℕ_{0} and α > \frac{1}{2}:

∑_{k=0}^{n−1}(n + k + 1)^{s} α^{k} [\binom{n + k}{n} − \binom{n + k}{n + 1}]

= (4α)^{n} n^{− \frac{3}{2}} π^{− \frac{1}{2}} (2n)^{s} \frac{4α − 1}{(2α − 1)^{2}} (1 + O(n^{−1})) .  (4)

(ii) The following asymptotic holds for α > \frac{1}{2}:

∑_{k=0}^{n−1}(n − k) α^{k} [\binom{n + k}{n} − \binom{n + k}{n + 1}]  (5)

= (4α)^{n} n^{− \frac{3}{2}} π^{− \frac{1}{2}} \frac{8α^{2}}{(2α − 1)^{3}} (1 + O(n^{−1})) .  (6)

Proof: The asymptotic for the first sum was computed in [Ke96a]. To compute the asymptotic equivalent for the second sum we first consider the following generating function for c ∈ ℕ_{0}

G(z, c, α) := ∑_{n≥0} z^{n} ∑_{k=0}^{n}(n − k) α^{k}\binom{n + k}{n + c} = ∑_{n≥0} z^{n} ∑_{k=0}^{n} k α^{n−k}\binom{2n − k}{n + c} .

After rearranging the sums and shifting the index of summation, we get:

G(z, c, α) = ∑_{λ≥0} λ z^{λ} ∑_{μ≥0}(αz)^{μ+c}\binom{2μ + λ + 2c}{μ} .  (7)

With the identities ∑_{λ≥0} λ x^{λ} = \frac{x}{(1−x)^{2}} , e. g. [GKP94, p. 335], and

∑_{l≥0} \binom{2l + β}{l}(αz)^{l} = \frac{1}{\sqrt{1 − 4αz}} (\frac{1 − \sqrt{1 − 4αz}}{2αz} )^{β} , β ∈ ℕ_{0} ,

e. g. [GKP94, p. 203], we can rewrite (7):

G(z, c, α) = \frac{1}{\sqrt{1 − 4αz}} (αz)^{c} (\frac{1 − \sqrt{1 − 4αz}}{2αz} )^{2c} ∑_{λ≥0} λ (\frac{1 − \sqrt{1 − 4αz}}{2α} )^{λ}

= \frac{1}{\sqrt{1 − 4αz}} \frac{1}{α} (\frac{1}{αz} )^{c} (\frac{1 − \sqrt{1 − 4αz}}{2} )^{2c+1} \frac{1}{(1 − \frac{1−\sqrt{1−4αz}}{2α} )^{2}} . (8)

Now, with (8) for c = 0 and c = 1 we find the generating function of the sum (5). Note that the term for k = n in the sum with index of summation k is equal to 0. We obtain the following simple closed-form expression of the generating function H(z, α) of the sum (5) by a straight-forward computation.

H(z, α) := G(z, 0, α) − G(z, 1, α) = \frac{2 (1 − 2αz − \sqrt{1 − 4αz})}{z (1 − 2α − \sqrt{1 − 4αz})^{2}} .

Now, we are looking for the singularity of smallest modulus that is not equal to 0. We find possible singularities at z = \frac{1}{4α} and z = 1 − α. Obviously, z = 1 − α is no singularity for α > \frac{1}{2}, because

H(1 − α, α) = \frac{2 (1 − 2α(1 − α) − \sqrt{1 − 4α(1 − α)})}{(1 − α) (1 − 2α − \sqrt{1 − 4α(1 − α)})^{2}} = \frac{1 − α}{(2α − 1)^{2}} , α > \frac{1}{2} .

Thus, the dominant singularity is at z = \frac{1}{4α}. Now, applying Darboux’s method, e. g. [Ke84], we get the asymptotic behaviour of the sum stated in the lemma. _{■} Remark 2: The following computation will show that it is not possible to deduce the asymptotical behaviour of (5) from (4).

∑_{k=0}^{n−1}(n − k) α^{k} [\binom{n + k}{n} − \binom{n + k}{n + 1}]

= ∑_{k=0}^{n−1}[(2n + 1) − (n + k + 1)] α^{k} [\binom{n + k}{n} − \binom{n + k}{n + 1}]

= \frac{(4α)^{n}}{n^{\frac{3}{2}} π^{\frac{1}{2}}} O(1) .

With the asymptotics for the two sums we are able to analyze the random variable X_{pref}(D_{2n}^{R}). Theorem 1: Assuming that all words in D_{2n}^{R} are equally likely, the s-th moments, s ≥ 1, of the random variable X_{pref}(D_{2n}^{R}) are given by:

𝔼[X_{pref}^{s}(D_{2n}^{R})] = (2n)^{s} + O(n^{s−1}) .

Proof: With the abbreviation α := \frac{|R|}{|T_{[}^{1}|} ≥ 1 we get by (2) using (3) and (1) and by shifting

the index of summation

𝔼[X_{pref}^{s}(D_{2n}^{R})] =

(2n)^{s} − |D_{2n}^{R}|^{−1} |T_{[}^{1}|^{n} × \{ ∑_{k=0}^{n−1}(n + k + 1)^{s} α^{k} [\binom{n + k}{n} − \binom{n + k}{n + 1}]

− \underbrace{∑_{k=0}^{n−1}(n + k)^{s} α^{k} [\binom{n + k}{n} − \binom{n + k}{n + 1}]}_{=:f(n,α)} \} .

The asymptotic behaviour of the first sum is given by (4). To gain an asymptotic equivalent for the second sum f(n, α), we first apply the addition formula for binomial coefficients \binom{a}{b} = \binom{a−1}{b} + \binom{a−1}{b−1}. We find

f(n, α) = g(n, α) + h(n, α) ,  (9)

where

g(n, α) := ∑_{k=0}^{n−1}(n + k)^{s} α^{k} [\binom{n + k − 1}{n} − \binom{n + k − 1}{n + 1}] ,

h(n, α) := ∑_{k=0}^{n−1}(n + k)^{s} α^{k} [\binom{n + k − 1}{n − 1} − \binom{n + k − 1}{n}] .

By shifting the index of summation and applying \binom{2n−1}{n} − \binom{2n−1}{n+1} = \frac{1}{n+1} \binom{2n}{n}, we obtain

g(n, α) = ∑_{k=0}^{n−1}(n + k + 1)^{s} α^{k+1} [\binom{n + k}{n} − \binom{n + k}{n + 1}] − (2n)^{s} α^{n} \frac{1}{n + 1}\binom{2n}{n} .

By (4) and the asymptotic behaviour of the Catalan numbers computed by Stirling’s formula [GKP94]

\frac{1}{n + 1}\binom{2n}{n} = 4^{n} n^{− \frac{3}{2}} π^{− \frac{1}{2}} (1 + O(n^{−1}))  (10)

we immediately get:

g(n, α) = (4α)^{n} n^{− \frac{3}{2}} π^{− \frac{1}{2}} (2n)^{s} \frac{3α − 1}{(2α − 1)^{2}} (1 + O(n^{−1})) .

A similar computation yields

h(n + 1, α)

= ∑_{k=0}^{n−1}(n + k + 1)^{s} α^{k} [\binom{n + k}{n} − \binom{n + k}{n + 1}] + (2n + 1)^{s} α^{n} \frac{1}{n + 1}\binom{2n}{n}

= (4α)^{n} n^{− \frac{3}{2}} π^{− \frac{1}{2}} [(2n)^{s} \frac{4α − 1}{(2α − 1)^{2}} + (2n + 1)^{s}] (1 + O(n^{−1})) .

Now, using the asymptotics for g(n, α) and h(n, α) in (9) and applying the formula for the number of Dyck words |D_{2n}^{R}| = \frac{1}{n+1} \binom{2n}{n}|R|^{n}, cf. [Li98], a simple computation leads to the equation 𝔼[X_{pref}^{s}(D_{2n}^{R})] = (2n)^{s} (1 + O(n^{−1})). _{■}

With 𝔼[X_{pref}^{s}(D_{2n}^{R})] we are not able to compute μ_{pref}(D_{2n}^{R}) and σ_{pref}^{2}(D_{2n}^{R}) with precision O(n^{−1}). This will be done in Theorem 2 and Theorem 3. Obviously, (3) implies that we must distinguish between the cases |R| = 1 and |R| ≥ 2. The case |R| = 1 has been investigated in [Li97]. There we find the following theorem. Theorem 2: Assuming that all words in D_{2n}^{R} are equally likely, the mean value and the variance of the random variable X_{pref}(D_{2n}^{R}) for |R| = 1 and n ≥ 2 are given by:

(i) μ_{pref}(D_{2n}^{R}) = 2n − \frac{13}{4} + O(n^{−1}) ,

(ii) σ_{pref}^{2}(D_{2n}^{R}) = \frac{51}{16} + O(n^{−1}) .

■

For the case |R| ≥ 2 we get the mean value and the variance of the number of symbols to be read in the following theorem. Theorem 3: Let α := \frac{|R|}{|T_{[}^{1}|} ≥ 1. Assuming that all words in D_{2n}^{R} are equally likely, the mean

value and the variance of the random variable X_{pref}(D_{2n}^{R}) for |R| ≥ 2 are given by:

\underline{Case 1:} |T_{[}^{1}| = 0, n ≥ 1 .

(i) μ_{pref}(D_{2n}^{R}) = 2n ,

(ii) σ_{pref}^{2}(D_{2n}^{R}) = 0 .

\underline{Case 2:} |T_{[}^{1}| ≥ 1, n → ∞ .

(i) μ_{pref}(D_{2n}^{R}) = 2n − \frac{4α − 1}{(2α − 1)^{2}} + O(n^{−1}) ,

(ii) σ_{pref}^{2}(D_{2n}^{R}) = \frac{4α^{2} (4α − 3)}{(2α − 1)^{4}} + O(n^{−1}) .

Proof: The proof of Case 1 is trivial. We insert (3) in (2) and obtain 𝔼[X_{pref}^{1}(D_{2n}^{R})] = 2n and 𝔼[X_{pref}^{2}(D_{2n}^{R})] = (2n)^{2}. For the mean value in Case 2 we get:

μ_{pref}(D_{2n}^{R}) = 𝔼[X_{pref}^{1}(D_{2n}^{R})] = 2n − |D_{2n}^{R}|^{−1} ∑_{k=n}^{2n−1} p(k, 2n − k) |T_{[}^{1}|^{2n−k} |R|^{k−n}

= 2n − \frac{|T_{[}^{1}|^{n}}{|D_{2n}^{R}|} ∑_{k=0}^{n−1} α^{k}p(n + k, n − k) .

With (1) and |D_{2n}^{R}| = \frac{1}{n+1} \binom{2n}{n}|R|^{n}, cf. [Li98], we obtain

μ_{pref}(D_{2n}^{R}) = 2n − \frac{n + 1}{\binom{2n}{n}}α^{−n} ∑_{k=0}^{n−1} α^{k} [\binom{n + k}{n} − \binom{n + k}{n + 1}] .

By (4) and (10) we immediately get the asymptotics for μ_{pref}(D_{2n}^{R}).

For the variance, we obtain with (2), (3) and (1)

σ_{pref}^{2}(D_{2n}^{R}) = 𝔼[X_{pref}^{2}(D_{2n}^{R})] − 𝔼[X_{pref}^{1}(D_{2n}^{R})]^{2}
= ((2n)^{2} − \frac{|T_{[}^{1}|^{n}}{|D_{2n}^{R}|} ∑_{k=0}^{n−1}(2n + 2k + 1) α^{k} [\binom{n + k}{n} − \binom{n + k}{n + 1}] )

− (2n − \frac{|T_{[}^{1}|^{n}}{|D_{2n}^{R}|} ∑_{k=0}^{n−1} α^{k} [\binom{n + k}{n} − \binom{n + k}{n + 1}] )^{2} .

Simplifying this expression yields

σ_{pref}^{2}(D_{2n}^{R}) = \frac{|T_{[}^{1}|^{n}}{|D_{2n}^{R}|} 2 ∑_{k=0}^{n−1}(n − k) α^{k} [\binom{n + k}{n} − \binom{n + k}{n + 1}]

− \frac{|T_{[}^{1}|^{n}}{|D_{2n}^{R}|} ∑_{k=0}^{n−1} α^{k} [\binom{n + k}{n} − \binom{n + k}{n + 1}]

− (\frac{|T_{[}^{1}|^{n}}{|D_{2n}^{R}|} ∑_{k=0}^{n−1} α^{k} [\binom{n + k}{n} − \binom{n + k}{n + 1}] )^{2} .

By applying (4), (6) and (10) and performing simplifications, we directly get the variance stated in the theorem. _{■} Remark 3: We have analyzed the number of symbols to be read in the ranking algorithm and have pointed out the number of symbols to be created by the unranking algorithm. So far, we did not talk about the running-time of the algorithms. In the last section we have seen that the amount of time per symbol is constant in both algorithms, so the running-time is proportional to the number of symbols to be read or created, respectively. Remark 4: In [Li97] the ranking and unranking of the Dyck language with t types of brackets D^{t} [Ha78, p. 313] was analyzed. Following our definitions, D^{t} = D^{R} with the relation R = {([_{1},]_{1}), ([_{2},]_{2}), …, ([_{t},]_{t})}. Further, D_{2n}^{t} = D_{2n}^{R}. The mean value and the variance of the random variable X_{pref}(D_{2n}^{t}) describing the number of symbols to be read for computing the rank for t ≥ 2 ∧ n ≥ 1 was found to be:

(i) μ_{pref}(D_{2n}^{t}) = 2n − 3 + O(n^{−1}) ,

(ii) σ_{pref}^{2}(D_{2n}^{t}) = 4 + O(n^{−1}) .

With R = {([_{1},]_{1}), …, ([_{t},]_{t})}, t ≥ 2, we find |R| = |T_{[}^{1}| = t. This implies α = \frac{|R|}{|T_{[}^{1}|} = 1. Thus, we obtain by Theorem 3, Case 2, the results stated in [Li97].

4 Generation of Random Trees

An interesting application for the unranking algorithm will be presented now: The generation of random labelled trees. Studying a class of combinatorial objects, it turns out to be an advantage to the researcher to have a procedure at hand, that gives an idea of the behaviour of the parameter in question. This procedure performs an exhaustive search for small objects and a random sampling for large objects [NW78, p. 3].

Another application for random labelled trees is in the area of testing computer programs, in particular the implementation of tree-based algorithms and data structures. For a small size of the trees, one can generate all trees [Li98] and compute the parameter in question. Unfortunately, this is not possible for trees with a larger number of nodes, since the number of trees is exponential in the number of nodes. Although the parameter can be computed exactly for small trees, an conclusion to the asymptotical behaviour of the parameter (for large trees) cannot be made. So, it is necessary to find another method to get an idea of the parameter’s behaviour. A practicable method is the generation of a sufficiently large set of random trees. Two methods to generate random objects were presented in [Wi77]; these methods were also applied in [NW78]. One method is to generate a random number and compute the corresponding object (or its linear coding) with an unranking algorithm. In this paper, we generate a random tree by applying the unranking algorithm for the generalized Dyck language to a random number. The other method constructs the object step by step. In each single step, the next symbol must be chosen from all possible symbols according to their probabilities depending on the actual position; these probabilities result from the number of continuations to an object of the desired size. This method requires the application of the random number generator for each symbol to be generated. It is used in [BLP99], for instance. It is well-known that there are several one-to-one correspondences between the normal Dyck language and other combinatorial objects. For example, the normal Dyck language is a linear coding for the shape of an ordered tree (arbitrary degree of the nodes) or an extended ordered binary tree (two types of nodes: internal nodes with two sons and leaves), cf. [AS95, p. 32] and [Za80], but the labels of the nodes or of the edges cannot be coded in the normal Dyck language. In [FS96, p. 266] a coding of ordered trees with labelled nodes by another generalization of the normal Dyck language was mentioned. With the generalization discussed here, we can also code the labels of the edges. Additionally, connections between certain labels can be considered, for example connections between the labels of the root of a subtree and the edge to its father (in an ordered tree) and connections between the labels of the brothers and/or the edges to their father (in an extended ordered binary tree). So, several classes of labelled trees can be coded by the generalized Dyck language. We point out three of them:

(a) Ordered trees with labelled nodes and labelled edges: In this class the relation R implies a connection between the labels of the nodes and the labels of the edges. The label of the node (resp. the label of the edge to its father) is coded in the type of the opening (resp. closing) bracket.

(b) Extended ordered binary trees with labelled nodes: Considering an internal node in an extended ordered binary tree, the label of the left (resp. right) son is coded in the type of the opening (resp. closing) bracket. So, a connection between the labels of the brothers is established.

(c) Extended ordered binary trees with labelled nodes and labelled edges: Here, the labels of the left (resp. right) son and the edge to its father are coded in the type of the opening (resp. closing) bracket. In that case we have a relation between the labels of the brothers and the labels of the edges to their father.

Remark 5: Note that in each case the label of the root of the tree is not coded in the Dyck word. It can be coded – if needed – in a further symbol to the left or right of the Dyck word. Remark 6: Consider a class of trees without any connection between the labels of the nodes and/or edges, coded in T_{[} and T_{]}; then each combination of opening and closing brackets is possible, i. e. the relation is given by: R := T_{[} × T_{]}. The one-to-one correspondences between the trees and the Dyck words are defined recursively. All trees in Figure 3 correspond to the Dyck word [_{a} X ]_{b} Y, where [_{a} and ]_{b} are corresponding brackets (following Remark 1) and X, Y ∈ D^{R}. Note that [_{a} X ]_{b} Y is a unique factorization of a Dyck word in D^{R} \ {ε}. The left picture shows an ordered tree (see (a)), whereas the other pictures represent extended ordered binary trees. In the middle, we find a tree with labelled nodes, corresponding to (b), and in the right picture, a tree with labels of the nodes and the edges is given (see (c)). In the latter case, the label of the left son (a_{2}) and the label of the edge to its father (a_{1}) must be coded in the type of the opening bracket (a). The same holds for b_{2}, b_{1} and b.

................................................................................................................  ................................................................................................................  ................................................................................................................  ................................................................................................................ ................................................................................................................  ................................................................................................................  ................................................................................................................ ................................................................................................................ ................................................................................................. ........................................................................................................  ........................................................................................................  ...............................................................................................................................................................................................................  .................................................................................... .................................................................................... ........................................................................................................  ........................................................................................................  ........................................................................................................  ........................................................................................................  .................................................................................... .................................................................................... ........................................................................................................  ........................................................................................................  ........................................................................................................  ........................................................................................................ X  Y a b  X  Y a  b  X  Y a_{1} a_{2}  b_{1}b_{2}

Figure 3: Labelled trees, corresponding to the Dyck word [_{a} X ]_{b} Y.

In these three cases, we find local connections between the labels only, i. e. connections between two or four labels at a time. These local connections are implied by the fact, that there is a unique corresponding closing to each opening bracket in every Dyck word and vice versa (see Remark 1). With the generalized Dyck language we cannot code trees with global connections, such as connections between a label and a property of the tree (or a subtree). The reason is obvious: In the generalized Dyck language, the labels of one pair of brackets are independent of the labels of the other pairs of brackets; they are independent of the structure of the Dyck word as well. For example, trees with labelled nodes, where the label describes the number of nodes in the subtree or its height, cannot be coded in the generalized Dyck language D_{2n}^{R}. Regarding Figure 3, we see that the shape of the tree and the labels can be determined in a very simple way from its coding. Obviously, the reason is the existence of the unique factorization of Dyck words mentioned above. Again, consider the Dyck word [_{a} X ]_{b} Y, where [_{a} and ]_{b} are corresponding brackets. If this Dyck word is a coding for an ordered tree, a and b are the labels of the node and the edge to its father and X is the coding of the subtree with the node, that is labelled by a, as its root. Y is the coding of all further subtrees on the right of the node with label a. In the case of an extended ordered binary tree, a (resp. b) codes the label of the left (resp. right) son and/or the edge to its father. The left and right subtrees can be determined from X and Y in the same manner. So, the recursive structure of the Dyck words reflects the recursive structure of the corresponding tree. Note that no recomputation of Dyck words X and Y has to be performed to find the shape and the labels of the subtrees.

Now, we will present two examples. In the first one, we find all words of a generalized Dyck language with their corresponding labelled ordered and extended ordered binary trees. One can see that only local connections between the labels exist, because we obtain a correct Dyck word, if we substitute one pair of corresponding brackets in a Dyck word by another one without further changes of the Dyck word. Considering the corresponding tree, this means to change some label(s) without changing the shape of the tree or its other labels. Example 2: Consider the generalized Dyck language D_{2n}^{R} with R := {([_{1},]_{1}), ([_{1},]_{2})}. In Figure 4 we find all Dyck words w ∈ D_{4}^{R} arranged according to their lexicographical order with the corresponding ordered trees (class (a)). From the relation follows immediately that the trees have two different types of edges, namely type 1 and type 2. Further, all nodes (except the root) are labelled by 1, thus this class of trees has only one type of nodes. Therefore, the labels of the nodes are suppressed in the picture.

................................................................................................................ ................................................................................................................  ................................................................................................................  ................................................................................................................ ................................................................................................................  ................................................................................................................  ................................................................................................................ ................................................................................................................  ................................................................................................................  ................................................................................................................ ................................................................................................................  ................................................................................................................ .................................................................  .................................................................  .................................................................  .................................................................  .................................................................  .................................................................  .................................................................  ................................................................. ................................................................................................................................................................................................................................................................................................................................................  ................................................................................................................................................................................................................................................................................................................................................  ................................................................................................................................................................................................................................................................................................................................................  ................................................................................................................................................................................................................................................................................................................................................ [_{1} [_{1} ]_{1} ]_{1} ≺_{lex} [_{1} [_{1} ]_{1} ]_{2} ≺_{lex} [_{1} [_{1} ]_{2} ]_{1} ≺_{lex} [_{1} [_{1} ]_{2} ]_{2} ≺_{lex} 1 1  2 1  1 2  2 2 [_{1} ]_{1} [_{1} ]_{1} ≺_{lex} [_{1} ]_{1} [_{1} ]_{2} ≺_{lex} [_{1} ]_{2} [_{1} ]_{1} ≺_{lex} [_{1} ]_{2} [_{1} ]_{2} 1  1  1  2  2  1  2  2

Figure 4: All Dyck words in D_{4}^{R} and their corresponding ordered trees.

In Figure 5 we present all extended ordered binary trees (class (b)) corresponding to the Dyck words w ∈ D_{4}^{R}. Again, they are arranged according to their lexicographical order. In this case, the relation implies that there is one type of nodes that are left sons of its father and two types of nodes that are right sons. With the unranking algorithm for the generalized Dyck language we have a procedure at hand that generates the coding of a random tree. We use a random number generator and compute the Dyck word and the corresponding labelled tree, whose rank is equal to the random number. Note the following fact: If the random number generator produces “good” random numbers, then the resulting Dyck words are codings of “good” random trees. Example 3: Let us have a look at two random trees according to the classes (a) and (b). First (class (a)), we consider a class of ordered trees with labelled edges and unlabelled nodes. As in the previous example, there are two different types of edges, say type 1 and type 2. Thus, the relation is given by R := {([_{1},]_{1}), ([_{1},]_{2})} again. Now, we want to generate an ordered tree with nine nodes, so n := 16. The random number generator computes 220609 ∈ [0 : D_{16}^{R}−1]. In the left picture in Figure 6 we

................................................................................................................................................................................................................................ ................................................................................................................  ................................................................................................................ ................................................................................................................ ................................................................. .................................................................  ................................................................. ................................................................. ................................................................................................................................................................................................................................ ................................................................................................................  ................................................................................................................ ................................................................................................................ ................................................................. .................................................................  ................................................................. ................................................................. ................................................................................................................................................................................................................................ ................................................................................................................  ................................................................................................................ ................................................................................................................ ................................................................. .................................................................  ................................................................. ................................................................. ................................................................................................................................................................................................................................ ................................................................................................................  ................................................................................................................ ................................................................................................................ ................................................................. .................................................................  ................................................................. ................................................................. ................................................................................................................................................................................................................................  ................................................................................................................ ................................................................................................................  ................................................................................................................ .................................................................  ................................................................. .................................................................  .................................................................  ................................................................................................................................................................................................................................  ................................................................................................................ ................................................................................................................  ................................................................................................................ .................................................................  ................................................................. .................................................................  .................................................................  ................................................................................................................................................................................................................................  ................................................................................................................ ................................................................................................................  ................................................................................................................ .................................................................  ................................................................. .................................................................  .................................................................  ................................................................................................................................................................................................................................  ................................................................................................................ ................................................................................................................  ................................................................................................................ .................................................................  ................................................................. .................................................................  ................................................................. [_{1} [_{1} ]_{1} ]_{1} ≺_{lex} [_{1} [_{1} ]_{1} ]_{2} ≺_{lex} [_{1} [_{1} ]_{2} ]_{1} ≺_{lex} [_{1} [_{1} ]_{2} ]_{2} ≺_{lex} 1  1  1  2  1  1  1  2 1  1  1  1  1  2  1  2 [_{1} ]_{1} [_{1} ]_{1} ≺_{lex} [_{1} ]_{1} [_{1} ]_{2} ≺_{lex} [_{1} ]_{2} [_{1} ]_{1} ≺_{lex} [_{1} ]_{2} [_{1} ]_{2} 1  1  1  1  1  2  1  2 1  1  1  2  1  1  1  2

Figure 5: All Dyck words in D_{4}^{R} and their corresponding extended ordered binary trees.

find the tree that corresponds to the Dyck word [_{1} [_{1} ]_{2} [_{1} [_{1} ]_{2} ]_{1} [_{1} ]_{2} ]_{1} [_{1} [_{1} ]_{2} [_{1} ]_{1} ]_{2} with rank 220609. As all nodes (except the root) are labelled by 1, the labels are suppressed in the picture. Second (class (b)), we want to generate an extended ordered binary tree with labelled nodes; there are three different types of nodes (1, 2 and 3) and the label of the left son of any node must not be smaller than the label of the right son. Obviously, we obtain R := {([_{1},]_{1}), ([_{2},]_{1}), ([_{2},]_{2}), ([_{3},]_{1}), ([_{3},]_{2}), ([_{3},]_{3})}. The root is unlabelled, because it does not have a brother (see Remark 5). Let n := 4 and let 12657 ∈ [0 : D_{8}^{R}] be the random number. The Dyck word with rank 12657 is given by [_{2} [_{1} ]_{1} [_{3} ]_{1} ]_{2} [_{2} ]_{1} and the resulting tree can be found in the right picture of Figure 6.

................................................................................................................  ................................................................................................................ ................................................................................................................................................................................................................................  ................................................................................................................ ................................................................................................................  ................................................................................................................ ................................................................................................................  ................................................................................................................  ................................................................................................................ ................................................................................................................  ................................................................................................................  ................................................................................................................  ................................................................................................................ ................................................................................................................ ................................................................................................................ ................................................................................................................  ................................................................................................................  ................................................................................................. .................................................................................................  .................................................................................... .................................................................................... .................................................................  ................................................................. .................................................................  ................................................................. ....................................................................................  ....................................................................................  .................................................................  .................................................................  .................................................................  ................................................................. 1  2 2 1  2 2  2  1 2  2  2 1  1  2  1 3  1

Figure 6: Two random trees (ordered and extended ordered binary).

5 Concluding Remarks

In this paper we have presented a ranking and an unranking algorithm for the generalized Dyck language. It is defined by a relation R which describes the pairs of brackets that can be used. The ranking (resp. unranking) algorithm reads (resp. creates) the Dyck word from left to right. Following a general approach to ranking and unranking [Li97], we computed the s-th moments of the random variable describing the length of the prefix to be read in order to determine the rank of a Dyck word. Especially, we pointed out the mean value and the variance of the length of that prefix with precision O(n^{−1}) for the generalized Dyck language D_{2n}^{R}. We showed that the number of symbols to be read is linear in the length of the words with a constant variance. The unranking algorithm always has to create the whole word, so the mean value of the number of symbols to be created is equal to the length of the words and the variance is equal to 0. Both algorithms presented here are optimal with respect to the number of symbols to be read (resp. created) from left to right. As the amount of time for each symbol is O(1), the running-time is proportional to the number of symbols to be read or created. Further, we mentioned one-to-one correspondences between the generalized Dyck language and ordered as well as extended ordered binary trees. With the generalization of the normal Dyck language we are able to code not only the shape of a tree but also the information of the nodes and/or the edges. Thus, with the algorithms presented here, we have ranking and unranking algorithms for a linear coding of various kinds of labelled trees at hand. An application for the unranking algorithm is the generation of random trees, which is useful in many areas. The unranking algorithm computes the Dyck word and the corresponding labelled tree, whose rank is equal to a random number.

Acknowledgement

The author takes the opportunity to thank the two anonymous referees for their detailed remarks and their suggestions that have helped to improve the paper.

References

[AS95] L. Alonso and R. Schott, Random Generation of Trees, Kluwer Academic Publishers, 1995.

[BLP99] E. Barcucci, A. Del Lungo, E. Pergola, Random Generation of Trees and Other Combinatorial Objects, Theoretical Computer Science 218, 1999, 219-232.

[CRS71] L. Carlitz, D. P. Roselle and R. A. Scoville, Some Remarks on Ballot-Type Sequences of Positive Integers, Journal of Combinatorial Theory 11, 1971, 258-271.

[FS96] P. Flajolet and R. Sedgewick, An Introduction to the Analysis of Algorithms, Addison-Wesley, 1996.

[GKP94] R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics, 2nd ed., Addison-Wesley, 1994.

[Ha78] M. A. Harrison, Introduction to Formal Language Theory, Addison-Wesley, 1978.

[Ke84] R. Kemp, Fundamentals of the Average Case Analysis of Particular Algorithms, Wiley-Teubner, 1984.

[Ke96a] R. Kemp, On Prefixes of Formal Languages and their Relation to the Average-Case Complexity of the Membership Problem, Journal of Automata, Languages and Combinatorics 1, 1997, 4, 259-303.

[Ke96b] R. Kemp, On the Average Minimal Prefix-Length of the Generalized Semi-Dycklanguage, RAIRO Theoretical Informatics and Applications 30, 1996, 6, 545-561.

[Ke98] R. Kemp, Generating Words Lexicographically: An Average-Case Analysis, Acta Informatica 35, 1998, 17-89.

[Li97] J. Liebehenschel, Ranking and Unranking of Lexicographically Ordered Words: An Average-Case Analysis, Journal of Automata, Languages and Combinatorics 2, 1998, 4, 227-268.

[Li98] J. Liebehenschel, Lexicographical Generation of a Generalized Dyck Language, Technical Report: Interner Bericht 5/98, Fachbereich Informatik, Johann Wolfgang Goethe-Universität, Frankfurt am Main, Germany, submitted.

[NW78] A. Nijenhuis, H. S. Wilf, Combinatorial Algorithms for computers and calculators, 2nd ed., Academic Press, 1978.

[Wi77] H. S. Wilf, A Unified Setting for Sequencing, Ranking and Selection Algorithms for Combinatorial Objects, Advances in Mathematics 24, 1977, 281-291.

[Za80] S. Zaks, Lexicographic Generation of Ordered Trees, Theoretical Computer Science 10, 1980, 63-82.