On q-functional equations and excursion moments

DOI10.1016/J.DISC.2007.12.072MaRDI QIDQ998510zbMATHOpenAlexFDO

Authors Christoph Richard

Publication date 28 January 2009

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0503198

zbMATH Keywords

limit distribution\(q\)-difference equationsimply generated treesBrownian excursion

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) (q)-calculus and related topics (05A30) Difference equations, scaling ((q)-differences) (39A13) Basic hypergeometric functions in one variable, ({}_rphi_s) (33D15)

Abstract: We analyse q-functional equations arising from tree-like combinatorial structures, which are counted by size, internal path length, and certain generalisations thereof. The corresponding counting parameters are labelled by a positive integer k. We show the existence of a joint limit distribution for these parameters in the limit of infinite size, if the size generating function has a square root as dominant singularity. The limit distribution coincides with that of integrals of k-th powers of the standard Brownian excursion. Our approach yields a recursion for the moments of the limit distribution. It can be used to analyse asymptotic expansions of the moments, and it admits an extension to other types of singularity.

Recommendations

• Linear functional equations with a catalytic variable and area limit laws for lattice paths and polygons
• Analysis of generating functions and probabilities on trees
• Infinite systems of functional equations and Gaussian limiting distributions
• A functional equation often arising in the analysis of algorithms (extended abstract)
• Limiting distributions for additive functionals on Catalan trees

Cites work

• scientific article; zbMATH DE number 981443 (Why is no real title available?)
• scientific article; zbMATH DE number 986989 (Why is no real title available?)
• scientific article; zbMATH DE number 19286 (Why is no real title available?)
• scientific article; zbMATH DE number 1268810 (Why is no real title available?)
• scientific article; zbMATH DE number 2046018 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 2102911 (Why is no real title available?)
• scientific article; zbMATH DE number 765034 (Why is no real title available?)
• scientific article; zbMATH DE number 863491 (Why is no real title available?)
• scientific article; zbMATH DE number 5279360 (Why is no real title available?)
• scientific article; zbMATH DE number 3256930 (Why is no real title available?)
• scientific article; zbMATH DE number 3274494 (Why is no real title available?)
• scientific article; zbMATH DE number 3390782 (Why is no real title available?)
• A Multivariate Faa di Bruno Formula with Applications
• A bernoulli excursion and its various applications
• A method for the enumeration of various classes of column-convex polygons
• An invariance principle for conditioned recurrent random walk attracted to a stable law
• Analytic combinatorics
• Analytic variations on the Airy distribution
• Area and Inertial Moment of Dyck Paths
• Basic analytic combinatorics of directed lattice paths
• Brownian excursion area, wright's constants in graph enumeration, and other Brownian areas
• Critical exponents from nonlinear functional equations for partially directed cluster models
• Geodesic distance in planar graphs
• Kac's formula, levy's local time and brownian excursion
• Left and right length of paths in binary trees
• Left and right pathlengths in random binary trees
• Limit laws for embedded trees: Applications to the integrated superBrownian excursion
• On the Altitude of Nodes in Random Trees
• On the Joint Path Length Distribution in Random Binary Trees
• On the analysis of linear probing hashing
• Probability theory. Translated from the German by Robert B. Burckel
• Scaling behaviour of two-dimensional polygon models
• Singularity Analysis of Generating Functions
• Singularity analysis, Hadamard products, and tree recurrences
• Stacking models of vesicles and compact clusters
• Stochastic analysis of tree–like data structures
• The Brownian excursion area: A numerical analysis
• The Wiener Index of simply generated random trees
• The continuum random tree. I
• The continuum random tree. III
• The density of the ISE and local limit laws for embedded trees
• The depth first processes of Galton-Watson trees converge to the same Brownian excursion
• The first-passage area for drifted Brownian motion and the moments of the Airy distribution
• The statistical mechanics of interacting walks, polygons, animals and vesicles
• Uniform q-series asymptotics for staircase polygons
• \(Q\)-grammars and wall polyominoes

Cited in

(8)

• On the joint distribution of the area and the number of peaks for Bernoulli excursions
• The density of the ISE and local limit laws for embedded trees
• Patterns in random permutations avoiding the pattern 132
• Trees with power-like height dependent weight
• Cost functionals for large (uniform and simply generated) random trees
• Tightness results for infinite-slit limits of the chordal Loewner equation
• Linear functional equations with a catalytic variable and area limit laws for lattice paths and polygons
• Area limit laws for symmetry classes of staircase polygons

This page was built for publication: On \(q\)-functional equations and excursion moments

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