Journal of Integer Sequences, Vol. 12 (2009), Article 09.7.7

Recursive Generation of k-ary Trees

K. Manes, A. Sapounakis, I. Tasoulas, and P. Tsikouras
Department of Informatics
University of Piraeus
18534 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,    dvi,    ps,    latex    

(Concerned with sequence 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