Generalized Stirling permutations, families of increasing trees and urn models (Q616442)

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.