Plane recursive trees, Stirling permutations and an urn model
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 as...
Main Author: | |
---|---|
Format: | Article |
Language: | English |
Published: |
Discrete Mathematics & Theoretical Computer Science
2008-01-01
|
Series: | Discrete Mathematics & Theoretical Computer Science |
Subjects: | |
Online Access: | https://dmtcs.episciences.org/3590/pdf |
_version_ | 1797270450049384448 |
---|---|
author | Svante Janson |
author_facet | Svante Janson |
author_sort | Svante Janson |
collection | DOAJ |
description | 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. |
first_indexed | 2024-04-25T02:04:27Z |
format | Article |
id | doaj.art-d3ddb6db1d7741e4b28b8ac20648f577 |
institution | Directory Open Access Journal |
issn | 1365-8050 |
language | English |
last_indexed | 2024-04-25T02:04:27Z |
publishDate | 2008-01-01 |
publisher | Discrete Mathematics & Theoretical Computer Science |
record_format | Article |
series | Discrete Mathematics & Theoretical Computer Science |
spelling | doaj.art-d3ddb6db1d7741e4b28b8ac20648f5772024-03-07T14:36:56ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502008-01-01DMTCS Proceedings vol. AI,...Proceedings10.46298/dmtcs.35903590Plane recursive trees, Stirling permutations and an urn modelSvante Janson0Department 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://dmtcs.episciences.org/3590/pdfplane recursive treesstirling permutationsnumber of ascentsnumber of descentsurn modelgeneralized pólya urn[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] |
spellingShingle | Svante Janson Plane recursive trees, Stirling permutations and an urn model Discrete Mathematics & Theoretical Computer Science plane recursive trees stirling permutations number of ascents number of descents urn model generalized pólya urn [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] |
title | Plane recursive trees, Stirling permutations and an urn model |
title_full | Plane recursive trees, Stirling permutations and an urn model |
title_fullStr | Plane recursive trees, Stirling permutations and an urn model |
title_full_unstemmed | Plane recursive trees, Stirling permutations and an urn model |
title_short | Plane recursive trees, Stirling permutations and an urn model |
title_sort | plane recursive trees stirling permutations and an urn model |
topic | plane recursive trees stirling permutations number of ascents number of descents urn model generalized pólya urn [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] |
url | https://dmtcs.episciences.org/3590/pdf |
work_keys_str_mv | AT svantejanson planerecursivetreesstirlingpermutationsandanurnmodel |