Benedikt Stufler - Probabilistic enumeration and equivalence of nonisomorphic trees

dmtcs:14790 - Discrete Mathematics & Theoretical Computer Science, January 12, 2026, vol. 27:3 - https://doi.org/10.46298/dmtcs.14790
Probabilistic enumeration and equivalence of nonisomorphic treesArticle

Authors: Benedikt Stufler

    We present a new probabilistic proof of Otter's asymptotic formula for the number of unlabelled trees with a given number of vertices. We additionally prove a new approximation result, showing that the total variation distance between random Pólya trees and random unlabelled trees tends to zero when the number of vertices tends to infinity. In order to demonstrate that our approach is not restricted to trees we extend our results to tree-like classes of graphs.


    Volume: vol. 27:3
    Section: Combinatorics
    Published on: January 12, 2026
    Accepted on: October 16, 2025
    Submitted on: November 18, 2024
    Keywords: Combinatorics, Probability