Plane recursive trees, Stirling permutations and an urn model

Svante Janson

doi:10.46298/dmtcs.3590

Svante Janson - Plane recursive trees, Stirling permutations and an urn model

dmtcs:3590 - Discrete Mathematics & Theoretical Computer Science, January 1, 2008, DMTCS Proceedings vol. AI, Fifth Colloquium on Mathematics and Computer Science - https://doi.org/10.46298/dmtcs.3590

Plane recursive trees, Stirling permutations and an urn modelConference paper

Authors: Svante Janson ¹

1 Department of Mathematics [Uppsala]

We exploit a bijection between plane recursive trees and Stirling permutations; this yields the equivalence of some results previously proven separately by different methods for the two types of objects as well as some new results. We also prove results on the joint distribution of the numbers of ascents, descents and plateaux in a random Stirling permutation. The proof uses an interesting generalized Pólya urn.

https://doi.org/10.46298/dmtcs.3590

Source: HAL:hal-01194667v1

Volume: DMTCS Proceedings vol. AI, Fifth Colloquium on Mathematics and Computer Science

Section: Proceedings

Published on: January 1, 2008

Imported on: May 10, 2017

Keywords: [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], [MATH.MATH-DS]Mathematics [math]/Dynamical Systems [math.DS], [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], [en] Plane recursive trees, Stirling permutations, number of ascents, number of descents, urn model, generalized Pólya urn

Bibliographic References

11 Documents citing this article

Richard A. Brualdi;Geir Dahl, 2024, Multipermutations and Stirling Multipermutations, Graphs and Combinatorics, 40, 2, 10.1007/s00373-024-02751-2, https://doi.org/10.1007/s00373-024-02751-2.

Elena Jaramillo Rodriguez, 2023, Combinatorial methods for barcode analysis, Journal of Applied and Computational Topology, 8, 2, pp. 239-270, 10.1007/s41468-023-00143-8.

Olivier Bodini;Antoine Genitrini;Mehdi Naima, 2022, A Combinatorial Link Between Labelled Graphs and Increasingly Labelled Schröder Trees, pp. 493-509, 10.1007/978-3-031-20624-5_30, https://hal.sorbonne-universite.fr/hal-03680342.

Diego Arcis;Sebastián Márquez, 2021, Hopf algebras on planar trees and permutations, arXiv (Cornell University), 21, 11, 10.1142/s0219498822502243, http://arxiv.org/abs/2002.00246.

Michael Wallner, 2018, A bijection of plane increasing trees with relaxed binary trees of right height at most one, arXiv (Cornell University), 755, pp. 1-12, 10.1016/j.tcs.2018.06.053, http://arxiv.org/abs/1706.07163.

David Callan;Shi-Mei Ma;Toufik Mansour, 2016, Restricted Stirling Permutations, Taiwanese Journal of Mathematics, 20, 5, 10.11650/tjm.20.2016.6717, https://doi.org/10.11650/tjm.20.2016.6717.

Markus Kuba;Alois Panholzer, 2016, On moment sequences and mixed Poisson distributions, Probability Surveys, 13, none, 10.1214/14-ps244, https://doi.org/10.1214/14-ps244.

Basile Morcrette, 2012, Fully Analyzing an Algebraic Pólya Urn Model, arXiv (Cornell University), pp. 568-581, 10.1007/978-3-642-29344-3_48, http://arxiv.org/abs/1203.4917.

J. Haglund;Mirkó Visontai, 2012, Stable multivariate Eulerian polynomials and generalized Stirling permutations, European Journal of Combinatorics, 33, 4, pp. 477-487, 10.1016/j.ejc.2011.10.007.

Markus Kuba;Alois Panholzer, 2012, Enumeration formulæ for pattern restricted Stirling permutations, Discrete Mathematics, 312, 21, pp. 3179-3194, 10.1016/j.disc.2012.07.011.

MARKUS KUBA;ALOIS PANHOLZER, 2011, Analysis of Statistics for Generalized Stirling Permutations, Combinatorics Probability Computing, 20, 6, pp. 875-910, 10.1017/s0963548311000381.

Sources : OpenCitations, OpenAlex & Crossref

Share and export

Consultation statistics

This page has been seen 337 times.

This article's PDF has been downloaded 497 times.