An algorithm for uniform generation of unlabeled trees (Pólya trees), with an extension of Cayley's formula

Laurent Bartholdi, Persi Diaconis

Pólya trees are rooted, unlabeled trees on $n$ vertices. This paper gives an efficient, new way to generate Pólya trees. This allows comparing typical unlabeled and labeled tree…