Descents on quasi-Stirling permutations

DOI10.1016/J.JCTA.2021.105429zbMATH Open1459.05001arXiv2002.00985OpenAlexW3127145954MaRDI QIDQ2229196FDOQ2229196

Authors: Sergi Elizalde 

Publication date: 22 February 2021

Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Abstract: Stirling permutations were introduced by Gessel and Stanley, who used their enumeration by the number of descents to give a combinatorial interpretation of certain polynomials related to Stirling numbers. Quasi-Stirling permutations, which can be viewed as labeled noncrossing matchings, were introduced by Archer et al. as a natural extension of Stirling permutations. Janson's correspondence between Stirling permutations and labeled increasing plane trees extends to a bijection between quasi-Stirling permutations and the same set of trees without the increasing restriction. Archer et al. posed the problem of enumerating quasi-Stirling permutations by the number of descents, and conjectured that there are $(n+1{)}^{n-1}$ such permutations of size $n$ having the maximum number of descents. In this paper we prove their conjecture, and we give the generating function for quasi-Stirling permutations by the number of descents, expressed as a compositional inverse of the generating function of Eulerian polynomials. We also find the analogue for quasi-Stirling permutations of the main result from Gessel and Stanley's paper. We prove that the distribution of descents on these permutations is asymptotically normal, and that the roots of the corresponding quasi-Stirling polynomials are all real, in analogy to B'ona's results for Stirling permutations. Finally, we generalize our results to a one-parameter family of permutations that extends $k$-Stirling permutations, and we refine them by also keeping track of the number of ascents and the number of plateaus.

Full work available at URL: https://arxiv.org/abs/2002.00985

Recommendations

• Statistics on quasi-Stirling permutations of multisets
• Quasi-Stirling polynomials on multisets
• Pattern restricted quasi-Stirling permutations
• Rooted quasi-Stirling permutations of general multisets
• Real zeros and normal distribution for statistics on Stirling permutations defined by Gessel and Stanley

zbMATH Keywords

descentplane treeEulerian polynomialnoncrossing matchingquasi-Stirlingstirling permutation

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Trees (05C05) Planar graphs; geometric and topological aspects of graph theory (05C10) Bernoulli and Euler numbers and polynomials (11B68)

Cites Work

• The on-line encyclopedia of integer sequences
• Title not available (Why is that?)
• Analytic combinatorics
• Title not available (Why is that?)
• On convergence rates in the central limit theorems for combinatorial structures
• Title not available (Why is that?)
• Stirling polynomials
• Probabilistic bounds on the coefficients of polynomials with only real zeros
• Central and local limit theorems applied to asymptotic enumeration
• Combinatorics of permutations
• Title not available (Why is that?)
• Unimodal, log-concave and Pólya frequency sequences in combinatorics
• Real zeros and normal distribution for statistics on Stirling permutations defined by Gessel and Stanley
• Generalized Stirling permutations, families of increasing trees and urn models
• The \(r\)-multipermutations
• A family of symmetric functions associated with Stirling permutations
• Stable multivariate Eulerian polynomials and generalized Stirling permutations
• Théorie géométrique des polynômes eulériens
• Unimodality, log-concavity, real-rootedness and beyond
• Crossings and nestings of matchings and partitions
• \(P\)-partitions and \(q\)-Stirling numbers
• Inverse descents of \(r\)-multipermutations
• Plane recursive trees, Stirling permutations and an urn model
• Analysis of statistics for generalized Stirling permutations
• A universal bijection between Gessel-Stanley permutations and connection diagrams of corresponding ranks
• Generalized Stirling permutations and forests: higher-order Eulerian and Ward numbers
• On the Distribution of the Number of Successes in Independent Trials
• Central and local limit theorems for the coefficients of polynomials of binomial type
• Pattern restricted quasi-Stirling permutations

Cited In (20)

• Statistics on multipermutations and partial \(\gamma\)-positivity
• Plane recursive trees, Stirling permutations and an urn model
• A context-free grammar for the \(e\)-positivity of the trivariate second-order Eulerian polynomials
• Multipermutations and Stirling multipermutations
• Generalized Stirling permutations, families of increasing trees and urn models
• On the lucky and displacement statistics of Stirling permutations
• Descents on nonnesting multipermutations
• Enumerating descents on quasi-Stirling permutations and plane trees
• MacMahon's equidistribution theorem for \(k\)-Stirling permutations
• Rooted quasi-Stirling permutations of general multisets
• Descents in \(t\)-sorted permutations
• Real zeros and normal distribution for statistics on Stirling permutations defined by Gessel and Stanley
• Partial \(\gamma \)-positivity for quasi-Stirling permutations of multisets
• Statistics on quasi-Stirling permutations of multisets
• Stirling permutation codes
• Some results related to Hurwitz stability of combinatorial polynomials
• Chromatic symmetric functions of Dyck paths and \(q\)-rook theory
• Pattern restricted quasi-Stirling permutations
• The Gessel correspondence and the partial \(\gamma \)-positivity of the Eulerian polynomials on multiset Stirling permutations
• Quasi-Stirling polynomials on multisets

Uses Software

• OEIS

This page was built for publication: Descents on quasi-Stirling permutations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2229196)