Recursive Generation of k-ary Trees
K. Manes, A. Sapounakis, I. Tasoulas, and P. Tsikouras
Department of Informatics
University of Piraeus
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.
Full version: pdf,
(Concerned with sequence
Received July 14 2009;
revised version received November 3 2009.
Published in Journal of Integer Sequences, November 4 2009.
Journal of Integer Sequences home page