# 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  [“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
Full Text:
##### References:
  Aldous, D.J.; Pitman, J., Brownian bridge asymptotics for random mappings, Random structures algorithms, 5, 4, 487-512, (1994) · Zbl 0811.60057  Arratia, R.; Barbour, A.D.; Tavaré, S., Logarithmic combinatorial structures: A probabilistic approach, (2003), European Math. Soc. Zürich · Zbl 1040.60001  Bergeron, F.; Flajolet, P.; Salvy, B., Varieties of increasing trees, (), 24-48  Bertoin, J., Random fragmentation and coagulation processes, (2006), Cambridge Univ. Press Cambridge · Zbl 1107.60002  Bollobas, B.; Riordan, O.M., Mathematical results on scale-free random graphs, (), 1-34 · Zbl 1047.05038  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  Brenti, F., Unimodal, log-concave, and Pólya frequency sequences in combinatorics, Mem. amer. math. soc., 81, 413, (1989) · Zbl 0697.05011  Brenti, F., Hilbert polynomials in combinatorics, J. algebraic combin., 7, 127-156, (1998) · Zbl 0901.05093  Dobrow, R.; Smythe, R., Poisson approximations for functionals of random trees, Random structures algorithms, 9, 79-92, (1996) · Zbl 0855.60025  Eggenberger, F.; Pólya, G., Über die statistik verketteter vorgänge, Zeitschrift angew. math. mech., 3, 279-289, (1923) · JFM 49.0382.01  Flajolet, P.; Dumas, P.; Puyhaubert, V., Some exactly solvable models of urn process theory, (), 59-118 · Zbl 1193.60011  Flajolet, P.; Sedgewick, R., Analytic combinatorics, (2009), Cambridge Univ. Press Cambridge · Zbl 1165.05001  Gessel, I.; Stanley, R.P., Stirling polynomials, J. combin. theory ser. A, 24, 1, 24-33, (1978) · Zbl 0378.05006  Janson, S., Functional limit theorems for multitype branching processes and generalized Pólya urns, Stochastic process. appl., 110, 177-245, (2004) · Zbl 1075.60109  Janson, S., Asymptotic degree distribution in random recursive trees, Random structures algorithms, 26, 69-83, (2005) · Zbl 1059.05094  Janson, S., Limit theorems for triangular urn schemes, Probab. theory related fields, 134, 417-452, (2006) · Zbl 1112.60012  Janson, S., Plane recursive trees, Stirling permutations and an urn model, (), 541-547 · Zbl 1358.60015  Johnson, N.L.; Kotz, S., Urn models and their application, (1977), Wiley New York · Zbl 0382.62040  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  Panholzer, A.; Prodinger, H., The level of nodes in increasing trees revisited, Random structures algorithms, 31, 203-226, (2007) · Zbl 1131.05029  Park, S.K., The r-multipermutations, J. combin. theory ser. A, 67, 1, 44-71, (1994) · Zbl 0804.05001  Park, S.K., Inverse descents of r-multipermutations, Discrete math., 132, 1-3, 215-229, (1994) · Zbl 0809.05001  Park, S.K., P-partitions and q-Stirling numbers, J. combin. theory ser. A, 68, 1, 33-52, (1994) · Zbl 0809.05006  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  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  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  Pólya, G., Sur quelques points de la théorie des probabilités, Ann. inst. Poincaré, 1, 117-161, (1931) · JFM 57.0610.02  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  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.