-positivity and partial -positivity of descent-type polynomials

DOI10.1016/J.JCTA.2019.05.002MaRDI QIDQ2318485zbMATH OpenOpenAlexFDO

Authors Shi-Mei Ma, Jun Ma, Yeong-Nan Yeh

Publication date 15 August 2019

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

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

zbMATH Keywords

derangement polynomialsEulerian polynomialsJacobi-Stirling permutationsLegendre-Stirling permutationsNarayana polynomialsStirling permutations

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15) Symmetric functions and generalizations (05E05) Bernoulli and Euler numbers and polynomials (11B68) Bell and Stirling numbers (11B73) Special sequences and polynomials (11B83) Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10)

Abstract: In this paper, we study gamma-positivity of descent-type polynomials by introducing the change of context-free grammars method. We first present grammatical proofs of the gamma-positivity of the Eulerian polynomials, type B Eulerian polynomials, derangement polynomials, Narayana polynomials and type B Narayana polynomials. We then provide partial gamma-positive expansions for several multivariate polynomials associated to Stirling permutations, Legendre-Stirling permutations, Jacobi-Stirling permutations and type B derangements, and the recurrences for the partial gamma-coefficients of these expansions are also obtained. Moreover, we define variants of the Foata-Strehl group action which are used to give combinatorial interpretations for the coefficients of most of these partial gamma-positive expansions.

Review text

A polynomial with symmetric coefficients, or a homogenous symmetric polynomial in two variables, can be written \(\sum_{k=0}^{\left\lfloor n/2 \right\rfloor} \gamma_k x^k (1+x)^{n-2k}\) or \(\sum_{k=0}^{\left\lfloor n/2 \right\rfloor} \gamma_k (xy)^k(x+y)^{n-2k}\); it is \(\gamma\)-positive if all \(\gamma_k\ge 0\). A polynomial in three variables is partial \(\gamma\)-positive if it can be written \(\sum s_i(x,y) z^i\) and all \(s_i\) are \(\gamma\)-positive. \textit{W. Y. C. Chen}'s grammar [Theor. Comput. Sci. 117, No. 1--2, 113--129 (1993; Zbl 0788.68082)] is a context-free grammar, which is extended to a derivation \(D\). We can change grammars by substituting variables in the derivation. Descent-type polynomials enumerate generalized permutations by descents; examples include Eulerian polynomials (classical and type \(B\)), derangement polynomials, and Narayama polynomials (classical and type \(B\)). For all of these polynomials, the authors use the change of grammars method to prove \(\gamma\)-positivity. For multivariate descent-type polynomials associated to Stirling permutations, Legendre-Stirling permutations, Jacobi-Stirling permutations, and type \(B\) derangements, the method proves partial \(\gamma\)-positivity, and gives recurrence relations for the partial \(\gamma\)-coefficients. Variants of the Foata-Strehl group action [\textit{D. Foata} and \textit{V. Strehl}, Math. Z. 137, 257--264 (1974; Zbl 0274.05007)] give combinatorial interpretations of many of the partial \(\gamma\)-coefficients.

Recommendations

• Statistics on multipermutations and partial \(\gamma\)-positivity
• A context-free grammar for the \(e\)-positivity of the trivariate second-order Eulerian polynomials
• Symmetric unimodal expansions of excedances in colored permutations
• The Gessel correspondence and the partial -positivity of the Eulerian polynomials on multiset Stirling permutations
• Enumeration of permutations by the parity of descent positions
• On the \(\gamma\)-positivity of multiset Eulerian polynomials
• The -positivity of basic Eulerian polynomials via group actions
• On two unimodal descent polynomials
• The Dumont ansatz for the Eulerian polynomials, peak polynomials and derivative polynomials
• Partial \(\gamma \)-positivity for quasi-Stirling permutations of multisets

Cites work

• \(q\)-Eulerian polynomials arising from Coxeter groups
• A combinatorial interpretation of the Legendre-Stirling numbers
• A context-free grammar for peaks and double descents of permutations
• Actions on permutations and unimodality of descent polynomials
• Combinatorial interpretations of the Jacobi-Stirling numbers
• Context-Free Grammars and Stable Multivariate Polynomials over Stirling Permutations
• Context-free grammars for permutations and increasing trees
• Context-free grammars for several polynomials associated with Eulerian polynomials
• Context-free grammars, differential operators and formal power series
• Counting permutations by runs
• Enriched \(P\)-partitions and peak algebras
• Enumerating a class of lattice paths
• Eulerian Numbers
• Eulerian polynomials, Stirling permutations of the second kind and perfect matchings
• Gamma-positivity in combinatorics and geometry
• scientific article; zbMATH DE number 3308309 (Why is no real title available?)
• Identities derived from noncrossing partitions of type \(B\)
• Identities from weighted Motzkin paths
• Jacobi-Stirling numbers, Jacobi polynomials, and the left-definite analysis of the classical Jacobi differential expression
• Jacobi-Stirling polynomials and \(P\)-partitions
• Legendre polynomials, Legendre--Stirling numbers, and the left-definite spectral analysis of the Legendre differential expression
• Legendre-Stirling permutations
• Non-crossing partitions for classical reflection groups
• On -positive polynomials arising in pattern avoidance
• On certain combinatorial expansions of the Eulerian polynomials
• On derangement polynomials of type B. II
• Real root conjecture fails for five- and higher-dimensional spheres
• Real zeros and normal distribution for statistics on Stirling permutations defined by Gessel and Stanley
• Rearrangements of the symmetric group and enumerative properties of the tangent and secant numbers
• Some \(q\)-analogues of the Schröder numbers arising from combinatorial statistics on lattice paths
• Some combinatorial arrays generated by context-free grammars
• Stable multivariate Eulerian polynomials and generalized Stirling permutations
• Stirling polynomials
• The -positivity of basic Eulerian polynomials via group actions
• The Eulerian distribution on involutions is indeed \(\gamma\)-positive
• The Eulerian distribution on involutions is indeed unimodal
• The Jacobi-Stirling numbers
• The Legendre-Stirling numbers
• The On-Line Encyclopedia of Integer Sequences
• The symmetric and unimodal expansion of Eulerian polynomials via continued fractions
• Three recurrences for parallelogram polyominoes
• Théorie géométrique des polynômes eulériens
• Total positivity of Narayana matrices
• William Chen grammars and derivations in trees and arborescences

Cited in

(42)

• Gamma-positivity in combinatorics and geometry
• MacMahon's equidistribution theorem for \(k\)-Stirling permutations
• Statistics on multipermutations and partial \(\gamma\)-positivity
• Weakly increasing trees on a multiset
• Jacobian elliptic functions and a family of bivariate peak polynomials
• Alternating Eulerian polynomials and left peak polynomials
• Partial \(\gamma \)-positivity for quasi-Stirling permutations of multisets
• The Gessel correspondence and the partial -positivity of the Eulerian polynomials on multiset Stirling permutations
• On the \(\gamma\)-positivity of multiset Eulerian polynomials
• Gamma-positivity for a refinement of median Genocchi numbers
• The \(\gamma\)-positivity of bivariate Eulerian polynomials via the Hetyei-Reiner action
• A context-free grammar for the \(e\)-positivity of the trivariate second-order Eulerian polynomials
• David-Barton type identities and alternating run polynomials
• On symmetric polynomials with only real zeros and nonnegative \(\gamma\)-vectors
• The \(\gamma \)-positive coefficients arising in segmented permutations
• Triangular recurrences, generalized Eulerian numbers, and related number triangles
• On -positive polynomials arising in pattern avoidance
• The -positivity of basic Eulerian polynomials via group actions
• scientific article; zbMATH DE number 7599682 (Why is no real title available?)
• A unified approach to multivariate polynomial sequences with real stability
• The Dumont ansatz for the Eulerian polynomials, peak polynomials and derivative polynomials
• Rooted quasi-Stirling permutations of general multisets
• Stirling permutation codes
• Positivity of Narayana polynomials and Eulerian polynomials
• Some \(\gamma \)-positive polynomials arising from enumerations of the pseudo Schröder paths
• Excedance-type polynomials, gamma-positivity and alternatingly increasing property
• The binomial-Stirling-Eulerian polynomials
• More bijective combinatorics of weakly increasing trees
• On the joint distributions of succession and Eulerian statistics
• The interlacing properties of generalized Narayana polynomials
• A group action on cyclic compositions and -positivity
• Eulerian-type polynomials over Stirling permutations and box sorting algorithm
• Stirling permutation codes. II
• Combinatorics on bi- -positivity of 1/k-Eulerian polynomials
• Sign-balance of excedances over mod-k-alternating permutations and gamma-positivity
• A symmetry on weakly increasing trees and multiset Schett polynomials
• Stable multivariate Narayana polynomials and labeled plane trees
• New refinements of Narayana polynomials and Motzkin polynomials
• Variants of the Euler operator and Eulerian polynomials
• A combinatorial method for log-concavity of rows of triangular arrays
• Gamma positivity of the descent based Eulerian polynomial in positive elements of classical Weyl groups
• The 1/k-Eulerian polynomials of type B

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: \(\gamma\)-positivity and partial \(\gamma\)-positivity of descent-type polynomials

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