Enumerating \(k\)-way trees (Q1313764)

A matrix representation of a \(k\)-way tree is described and used to prove a theorem on the number of \(k\)-way trees with a prescribed number of edges in each direction. The theorem is then used to give a simple proof of Cayley's theorem on the number of free labelled trees on \(n\) nodes. In addition, efficient algorithm to generate arbitrary \(k\)-way trees uniformly at random is outlined.