×

zbMATH — the first resource for mathematics

Generalized Stirling permutations, families of increasing trees and urn models. (English) Zbl 1230.05100
In this paper the authors discuss correspondences between certain types of permutations and certain types of trees. By exploiting these correspondences they obtain results on the distribution of ascents, descents, and plateaus in random permutations using the connection between (random) trees and specific Polya urn models.
Section 1 gives an overview of previous results and an outliner for the paper.
Section 2.1 introduces notations and definitions for generalized Stirling permutations. Furthermore some results from literature are recalled.
Section 2.2 discusses several types of generalized plane recursive trees.
Section 3.1 explores the relation between (\(k+1\))-ary increasing trees, k-plane recursive trees and k-Stirling permutations. Theorem 1 gives an explicit bijection between (\(k+1\))-ary increrasing trees and k-Stirling permutations. In Theorem 2 ascents, descents and plateaus in Stirling permutations are related to j-children and j-leaves in (\(k+1\))-increasing trees. Theorem 3 prepares the use of Polya urn models.
Section 3.2 is not entirely clear to me especially the definitions of \(B_A\) \(B_D\) and \(B_E\) remain rather vague for me.
Section 4 makes some other bijections more explicit. First the correspondence between ordinary plane recursive trees of order n+1 and ternary increasing trees of order n is discussed. Next the notion of \( F_{k,k+2}\) increasing trees is introduced and a bijection between those trees and k-bundled increasing trees is given.
Section 5 is on distributions of ascents, descents, plateaus and block sizes. Here the described correspondences are exploited in combination with some results that one of the authors published already in an erlier paper: The authors reference [14] [“Functional limit Theorems for multitype branching processes and generalize Polya urns”, Stochastic Processes Appl. 110, No. 2, 171–245 (2004; Zbl 1075.60109)].
In Section 6 the authors use another urn model for deriving expressions for the probability distributions of the number of blocks in random k-Stirling permutations, more specific for the probability mass function and binomial moments.
In Section 7 using a Polya urn model, some results on the distribution of block lengths are derived.

MSC:
05C05 Trees
05A05 Permutations, words, matrices
05C80 Random graphs (graph-theoretic aspects)
60C99 Combinatorial probability
60E99 Distribution theory
60F99 Limit theorems in probability theory
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Aldous, D.J.; Pitman, J., Brownian bridge asymptotics for random mappings, Random structures algorithms, 5, 4, 487-512, (1994) · Zbl 0811.60057
[2] Arratia, R.; Barbour, A.D.; Tavaré, S., Logarithmic combinatorial structures: A probabilistic approach, (2003), European Math. Soc. Zürich · Zbl 1040.60001
[3] Bergeron, F.; Flajolet, P.; Salvy, B., Varieties of increasing trees, (), 24-48
[4] Bertoin, J., Random fragmentation and coagulation processes, (2006), Cambridge Univ. Press Cambridge · Zbl 1107.60002
[5] Bollobas, B.; Riordan, O.M., Mathematical results on scale-free random graphs, (), 1-34 · Zbl 1047.05038
[6] Bóna, M., Real zeros and normal distribution for statistics on Stirling permutations defined by gessel and Stanley, SIAM J. discrete math., 23, 1, 401-406, (2008/09) · Zbl 1230.05005
[7] Brenti, F., Unimodal, log-concave, and Pólya frequency sequences in combinatorics, Mem. amer. math. soc., 81, 413, (1989) · Zbl 0697.05011
[8] Brenti, F., Hilbert polynomials in combinatorics, J. algebraic combin., 7, 127-156, (1998) · Zbl 0901.05093
[9] Dobrow, R.; Smythe, R., Poisson approximations for functionals of random trees, Random structures algorithms, 9, 79-92, (1996) · Zbl 0855.60025
[10] Eggenberger, F.; Pólya, G., Über die statistik verketteter vorgänge, Zeitschrift angew. math. mech., 3, 279-289, (1923) · JFM 49.0382.01
[11] Flajolet, P.; Dumas, P.; Puyhaubert, V., Some exactly solvable models of urn process theory, (), 59-118 · Zbl 1193.60011
[12] Flajolet, P.; Sedgewick, R., Analytic combinatorics, (2009), Cambridge Univ. Press Cambridge · Zbl 1165.05001
[13] Gessel, I.; Stanley, R.P., Stirling polynomials, J. combin. theory ser. A, 24, 1, 24-33, (1978) · Zbl 0378.05006
[14] Janson, S., Functional limit theorems for multitype branching processes and generalized Pólya urns, Stochastic process. appl., 110, 177-245, (2004) · Zbl 1075.60109
[15] Janson, S., Asymptotic degree distribution in random recursive trees, Random structures algorithms, 26, 69-83, (2005) · Zbl 1059.05094
[16] Janson, S., Limit theorems for triangular urn schemes, Probab. theory related fields, 134, 417-452, (2006) · Zbl 1112.60012
[17] Janson, S., Plane recursive trees, Stirling permutations and an urn model, (), 541-547 · Zbl 1358.60015
[18] Johnson, N.L.; Kotz, S., Urn models and their application, (1977), Wiley New York · Zbl 0382.62040
[19] Kuba, M.; Panholzer, A., On the degree distribution of the nodes in increasing trees, J. combin. theory ser. A, 114, 597-618, (2007) · Zbl 1116.05020
[20] Panholzer, A.; Prodinger, H., The level of nodes in increasing trees revisited, Random structures algorithms, 31, 203-226, (2007) · Zbl 1131.05029
[21] Park, S.K., The r-multipermutations, J. combin. theory ser. A, 67, 1, 44-71, (1994) · Zbl 0804.05001
[22] Park, S.K., Inverse descents of r-multipermutations, Discrete math., 132, 1-3, 215-229, (1994) · Zbl 0809.05001
[23] Park, S.K., P-partitions and q-Stirling numbers, J. combin. theory ser. A, 68, 1, 33-52, (1994) · Zbl 0809.05006
[24] Perman, M.; Pitman, J.; Yor, M., Size-biased sampling of Poisson point processes and excursions, Probab. theory related fields, 92, 1, 21-39, (1992) · Zbl 0741.60037
[25] Pitman, J.; Yor, M., Arcsine laws and interval partitions derived from a stable subordinator, Proc. lond. math. soc. (3), 65, 2, 326-356, (1992) · Zbl 0769.60014
[26] Pitman, J.; Yor, M., The two-parameter Poisson-Dirichlet distribution derived from a stable subordinator, Ann. probab., 25, 2, 855-900, (1997) · Zbl 0880.60076
[27] Pólya, G., Sur quelques points de la théorie des probabilités, Ann. inst. Poincaré, 1, 117-161, (1931) · JFM 57.0610.02
[28] Stepanov, V.E., Limit distributions of certain characteristics of random mappings, Teor. verojatnost. i primenen., Theory probab. appl., 14, 612-626, (1969), (in Russian); English transl.: · Zbl 0193.46401
[29] Vitter, J.; Flajolet, P., Average case analysis of algorithms and data structures, (), 431-524 · Zbl 0900.68251
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.