Generating Trees and Other Combinatorial Objects Lexicographically

Abstract

We show a one-to-one correspondence between all the ordered trees that have $n_0 + 1$ leaves and $n_i $ internal nodes with $k_i $ sons each, for $i = 1, \cdots ,t$, (hence $n_0 = \sum_1^t (k_i - 1) n_i $) and all the lattice paths in the $(t + 1)$-dimensional space, from the point $(n_0 ,n_1 , \cdots , n_t )$ to the origin, which do not go below the hyperplane $x_0 = \sum_1^t (k_i - 1) x_i $. Procedures for generating these paths (and thus the ordered trees) are presented and the ranking and unranking procedures are derived.