Analyzing Generalized Stirling Permutations via Relations to Families of Increasing Trees and Urn Models

Abstract

Stirling permutations are a class of restricted permutations of multisets introduced by Gessel and Stanley. We consider Stirling permutations and generalizations and establish bijective links between these combinatorial objects and certain families of increasing trees. Our main interest is the distributional analysis of several “permutation statistics” for these objects, i.e., describing the exact and asymptotic behaviour of various parameters in generalized Stirling permutations. In our analysis we show results for the number of ascents, descents and plateux, the number of blocks, the sizes of the blocks, the number of left-to-right minima and left-to-right maxima, the distance between occurrences of elements, and the number of inversions. To get the results we first use the before mentioned bijections, which also link the parameters under consideration with certain quantities in increasing trees. Then we use several techniques ranging from generating functions, connections to P\'olya urn models, martingales, and Stein's method for analyzing them. The talk is based on a joint work with Svante Janson (Uppsala University) and Markus Kuba (TU Wien). ?