Generating functions for individual leaf depths

DOI10.1016/J.DAM.2024.04.017MaRDI QIDQ6426055zbMATH OpenFDO

Authors Sergi Elizalde

Publication date 10 February 2023

Full work available at URL https://doi.org/10.1016/J.DAM.2024.04.017

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Trees (05C05)

Abstract: We explore a generating function trick which allows us to keep track of infinitely many statistics using finitely many variables, by recording their individual distributions rather than their joint distributions. Building on previous work of Panholzer and Prodinger, we apply this method to study the depth distributions of individual nodes in binary trees, plane trees, noncrossing trees, and increasing trees; the height distributions of individual vertices and individual steps in Dyck paths; and the number of diagonals separating two fixed sides of a convex polygon in a triangulation or dissection. We obtain both exact and asymptotic results, which sometimes refine known formulas or provide combinatorial proofs of results from the probability literature.

Recommendations

• Analysis of generating functions and probabilities on trees
• The height distribution of leaves in rooted trees
• On the distribution of depths in increasing trees
• scientific article; zbMATH DE number 4023312
• Moments of level numbers of leaves in binary trees

This page was built for publication: Generating functions for individual leaf depths

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6426055)