Rooted quasi-Stirling permutations of general multisets

Abstract

Given a general multiset $\mathcal{M}=\{1^{m_1},2^{m_2},\dots ,n^{m_n}\}$, where $i$ appears $m_i$ times, a multipermutation $\pi$ of $\mathcal{M}$ is called {\em quasi-Stirling}, if it contains no subword of the form $abab$ with $a\ne b$. We designate exactly one entry of $\pi$, say $k\in \mathcal{M}$, which is not the leftmost entry among all entries with the same value, by underlining it in $\pi$, and we refer to the pair $(\pi ,k)$ as a quasi-Stirling multipermutation of $\mathcal{M}$ rooted at $k$. By introducing certain vertex and edge labeled trees, we give a new bijective proof of an identity due to Yan, Yang, Huang and Zhu, which links the enumerator of rooted quasi-Stirling multipermutations by the numbers of ascents, descents, and plateaus, with the exponential generating function of the {\em bivariate Eulerian polynomials}. This identity can be viewed as a natural extension of Elizalde's result on $k$-quasi-Stirling permutations, and our bijective approach to proving it enables us to: (1) prove bijectively a Carlitz type identity involving quasi-Stirling polynomials on multisets that was first obtained by Yan and Zhu; (2) confirm a recent partial $\gamma$-positivity conjecture due to Lin, Ma and Zhang, and find a combinatorial interpretation of the $\gamma$-coefficients in terms of two new statistics defined on quasi-Stirling multipermutations called sibling descents and double sibling descents.

17 pages, comments are welcome

References in corpus (6)

• Gamma-positivity in combinatorics and geometry
• The symmetric and unimodal expansion of Eulerian polynomials via continued fractions
• Plane recursive trees, Stirling permutations and an urn model
• Pattern restricted quasi-Stirling permutations
• Quasi-Stirling Permutations on Multisets
• Partial $\gamma$-Positivity for Quasi-Stirling Permutations of Multisets