On q-functional equations and excursion moments

DOI10.1016/J.DISC.2007.12.072zbMATH Open1227.39006arXivmath/0503198OpenAlexW2115836261MaRDI QIDQ998510FDOQ998510

Authors: Christoph Richard 

Publication date: 28 January 2009

Published in: Discrete Mathematics (Search for Journal in Brave)

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.

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

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

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)

Cites Work

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

Cited In (8)

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

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)