Generalized Stirling permutations, families of increasing trees and urn models

DOI10.1016/J.JCTA.2009.11.006zbMATH Open1230.05100arXiv0805.4084OpenAlexW2160220344MaRDI QIDQ616442FDOQ616442

Authors: Svante Janson, Markus Kuba, Alois Panholzer 

Publication date: 7 January 2011

Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Abstract: Bona [2007+] studied the distribution of ascents, plateaux and descents in the class of Stirling permutations, introduced by Gessel and Stanley [1978]. Recently, Janson [2008+] showed the connection between Stirling permutations and plane recursive trees and proved a joint normal law for the parameters considered by Bona. Here we will consider generalized Stirling permutations extending the earlier results of Bona and Janson, and relate them with certain families of generalized plane recursive trees, and also $(k+1)$-ary increasing trees. We also give two different bijections between certain families of increasing trees, which both give as a special case a bijection between ternary increasing trees and plane recursive trees. In order to describe the (asymptotic) behaviour of the parameters of interests, we study three (generalized) Polya urn models using various methods.

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

Recommendations

• Plane recursive trees, Stirling permutations and an urn model
• Analysis of statistics for generalized Stirling permutations
• Block patterns in Stirling permutations
• Descents on quasi-Stirling permutations
• Some statistics on Stirling permutations and Stirling derangements

zbMATH Keywords

descentsStirling permutationslimiting distributionurn modelsincreasing treesplateausascentsblocks in permutationsplane recursive trees

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Limit theorems in probability theory (60F99) Distribution theory (60E99) Combinatorial probability (60C99)

Cites Work

• Analytic combinatorics
• The two-parameter Poisson-Dirichlet distribution derived from a stable subordinator
• Size-biased sampling of Poisson point processes and excursions
• On some generalized farlie-gumbel-morgenstern distributions-II regression, correlation and further generalizations
• Stirling polynomials
• Random Fragmentation and Coagulation Processes
• Logarithmic combinatorial structures: A probabilistic approach
• The diameter of a scale-free random graph
• Some exactly solvable models of urn process theory
• Functional limit theorems for multitype branching processes and generalized Pólya urns.
• Unimodal, log-concave and Pólya frequency sequences in combinatorics
• Real zeros and normal distribution for statistics on Stirling permutations defined by Gessel and Stanley
• Level of nodes in increasing trees revisited
• The \(r\)-multipermutations
• Asymptotic degree distribution in random recursive trees
• \(P\)-partitions and \(q\)-Stirling numbers
• Inverse descents of \(r\)-multipermutations
• Hilbert polynomials in combinatorics
• Plane recursive trees, Stirling permutations and an urn model
• Title not available (Why is that?)
• Limit theorems for triangular urn schemes
• On the degree distribution of the nodes in increasing trees
• Brownian bridge asymptotics for random mappings
• Arcsine Laws and Interval Partitions Derived from a Stable Subordinator
• Title not available (Why is that?)
• Poisson approximations for functionals of random trees

Cited In (46)

• Jacobi-Stirling polynomials and \(P\)-partitions
• Statistics on multipermutations and partial \(\gamma\)-positivity
• Plane recursive trees, Stirling permutations and an urn model
• A bijection of plane increasing trees with relaxed binary trees of right height at most one
• Occupancy problems related to the generalized Stirling numbers
• Statistics on trapezoidal words and \(k\)-inversion sequences
• Bijection between increasing binary trees and rook placements on double staircases
• Bivariate generating functions for a class of linear recurrences: general structure
• A context-free grammar for the \(e\)-positivity of the trivariate second-order Eulerian polynomials
• The ascent-plateau statistics on Stirling permutations
• Pattern restricted Stirling \(k\)-ary words, the plateau statistic and the kernel method
• Hopf algebras of \(m\)-permutations, \((m + 1)\)-ary trees, and \(m\)-parking functions
• An asymptotic distribution theory for Eulerian recurrences with applications
• The Haglund-Remmel-Wilson identity for \(k\)-Stirling permutations
• A unified approach to multivariate polynomial sequences with real stability
• On the free Lie algebra with multiple brackets
• Stable multivariate Eulerian polynomials and generalized Stirling permutations
• Lattice paths and branched continued fractions. II: Multivariate Lah polynomials and Lah symmetric functions
• Descents on nonnesting multipermutations
• Stirling permutations, cycle structure of permutations and perfect matchings
• Enumerating descents on quasi-Stirling permutations and plane trees
• Gibbs partitions, Riemann-Liouville fractional operators, Mittag-Leffler functions, and fragmentations derived from stable subordinators
• On bucket increasing trees, clustered increasing trees and increasing diamonds
• On moment sequences and mixed Poisson distributions
• Enumeration formulæ for pattern restricted Stirling permutations
• MacMahon's equidistribution theorem for \(k\)-Stirling permutations
• Phase transitions of composition schemes: Mittag-Leffler and mixed Poisson distributions
• Lattice Paths and Branched Continued Fractions: An Infinite Sequence of Generalizations of the Stieltjes–Rogers and Thron–Rogers Polynomials, with Coefficientwise Hankel-Total Positivity
• Overview on Heisenberg-Weyl algebra and subsets of Riordan subgroups
• Descents on quasi-Stirling permutations
• Weakly increasing trees on a multiset
• Some statistics on Stirling permutations and Stirling derangements
• Stirling permutation codes
• Context-Free Grammars and Stable Multivariate Polynomials over Stirling Permutations
• The combinatorics of a tree-like functional equation for connected chord diagrams
• The \(1 / k\)-Eulerian polynomials and \(k\)-Stirling permutations
• Pattern restricted quasi-Stirling permutations
• Eulerian polynomials, Stirling permutations of the second kind and perfect matchings
• The Gessel correspondence and the partial \(\gamma \)-positivity of the Eulerian polynomials on multiset Stirling permutations
• Analysis of statistics for generalized Stirling permutations
• Generalized Stirling permutations and forests: higher-order Eulerian and Ward numbers
• Enumeration of a dual set of Stirling permutations by their alternating runs
• Combinatorial families of multilabelled increasing trees and hook-length formulas
• Pseudo-involutions in the Riordan group
• Title not available (Why is that?)
• Large deviations for the leaves in some random trees

This page was built for publication: Generalized Stirling permutations, families of increasing trees and urn models

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