An algorithm for uniform generation of unlabeled (Pólya) trees

Pólya trees are unlabeled rooted trees on n vertices. This paper gives a new way to generate Pólya trees, that conjecturally is very efficient. This allows comparing typical unlabeled and labeled tree statistics and comparing asymptotic theorems with “reality.” Our method is an application of the Burnside process, alternating two steps: from a labeled rooted tree, produce a uniform permutation fixing it; and from a permutation, produce a uniform labeled rooted tree fixed by it. This last step is linked to a product formula, refining Cayley’s, for the number of rooted labeled trees preserved by a given permutation.