##
Cool-lex Order and *k*-ary Catalan Structures

*Stephane Durocher*,
Department of Computer Science,
University of Manitoba, Canada.

*Pak Ching Li*,
Department of Computer Science,
University of Manitoba, Canada.

*Debajyoti Mondal*,
Department of Computer Science,
University of Manitoba, Canada.

*Frank Ruskey*,
Department of Computer Science,
University of Victoria, Canada.

*Aaron Williams*,
Department of Mathematics and Statistics, McGill University.

### Abstract:

For any given *k*, the sequence of *k*-ary Catalan numbers,
C_{t,k} = \frac{1}{kt+1}\binom{kt}{t}, enumerates a number of combinatorial objects,
including *k*-ary Dyck words of length *n*=*kt* and *k*-ary
trees with *t* internal nodes.
We show that these objects can be efficiently ordered using the same variation of
lexicographic order known as cool-lex order.
In particular, we provide loopless algorithms that generate each successive object in O(1) time.
The algorithms are also efficient in terms of memory, with the *k*-ary Dyck word algorithm using
O(1) additional index variables, and the *k*-ary tree algorithm using O(*t*) additional
pointers and index variables.
We also show how to efficiently rank and unrank *k*-ary Dyck words in cool-lex order using O(*kt*)
arithmetic operations, subject to an initial precomputation.
Our results are based on the cool-lex successor rule for sets of binary strings that are bubble languages.
However, we must complement and reverse 1/*k*-ary Dyck words to obtain the stated efficiency.

Back to list of publications.