A coding algorithm for Rényi trees (Q1207762)

The author considers \(k\)-trees with \(n\) labelled nodes \(1,2,\dots,n\) constructed as follows: start with a complete \(k\)-graph with nodes \(n- k+1,\dots,n\) and successively join a new node to \(k\) nodes already joined to each other. He shows that there is a bijection between these \(k\)-trees with \(n\) nodes and certain doubly labelled rooted trees with \(n-k+1\) nodes and one between these latter trees and certain doubly labelled forests of trees of height one. This ultimately gives rise to a bijection between \(k\)-trees with \(n\) labelled nodes and sequences of length \(n-k+1\) over an alphabet of \(k(n-k)+1\) elements. Some applications of these bijections are discussed.