Stable multivariate W-Eulerian polynomials

We prove a multivariate strengthening of Brenti?s result that every root of the Eulerian polynomial of type B is real. Our proof combines a refinement of the descent statistic for signed permutations with the notion of real stability—a generalization of real-rootedness to polynomials in multiple variables. The key is that our refined multivariate Eulerian polynomials satisfy a recurrence given by a stability-preserving linear operator.Our results extend naturally to colored permutations, and we also give stable generalizations of recent real-rootedness results due to Dilks, Petersen, and Stembridge on affine Eulerian polynomials of types A and C. Finally, although we are not able to settle Brenti?s real-rootedness conjecture for Eulerian polynomials of type D, nor prove a companion conjecture of Dilks, Petersen, and Stembridge for affine Eulerian polynomials of types B and D, we indicate some methods of attack and pose some related open problems.     

Eulerian pairs and Eulerian recurrence systems

In this paper, we introduce the definitions of Eulerian pair and Hermite-Biehler pair. We also characterize a duality relation between Eulerian recurrences and Eulerian recurrence systems. This generalizes and unifies Hermite-Biehler decompositions of several enumerative polynomials, including up-down run polynomials for symmetric groups, alternating run polynomials for hyperoctahedral groups, flag descent polynomials for hyperoctahedral groups and flag ascent-plateau polynomials for Stirling permutations. We derive some properties of associated polynomials. In particular, we prove the alternatingly increasing property and the interlacing property of the ascent-plateau and left ascent-plateau polynomials for Stirling permutations.     

A context-free grammar for the e-positivity of the trivariate second-order Eulerian polynomials

Ma-Ma-Yeh made a beautiful observation that a transformation of the grammar of Dumont instantly leads to the γ-positivity of the Eulerian polynomials. We notice that the transformed grammar bears a striking resemblance to the grammar for 0-1-2 increasing trees also due to Dumont. The appearance of the factor of two fits perfectly in a grammatical labeling of 0-1-2 increasing plane trees. Furthermore, the grammatical calculus is instrumental to the computation of the generating functions. This approach can be adapted to study the e-positivity of the trivariate second-order Eulerian polynomials first introduced by Dumont in the contexts of ternary trees and Stirling permutations, and independently defined by Janson, in connection with the joint distribution of the numbers of ascents, descents and plateaux over Stirling permutations.     

Eulerian quasisymmetric functions

We introduce a family of quasisymmetric functions called Eulerian quasisymmetric functions, which specialize to enumerators for the joint distribution of the permutation statistics, major index and excedance number on permutations of fixed cycle type. This family is analogous to a family of quasisymmetric functions that Gessel and Reutenauer used to study the joint distribution of major index and descent number on permutations of fixed cycle type. Our central result is a formula for the generating function for the Eulerian quasisymmetric functions, which specializes to a new and surprising q-analog of a classical formula of Euler for the exponential generating function of the Eulerian polynomials. This q-analog computes the joint distribution of excedance number and major index, the only of the four important Euler-Mahonian distributions that had not yet been computed. Our study of the Eulerian quasisymmetric functions also yields results that include the descent statistic and refine results of Gessel and Reutenauer. We also obtain q-analogs, (q,p)-analogs and quasisymmetric function analogs of classical results on the symmetry and unimodality of the Eulerian polynomials. Our Eulerian quasisymmetric functions refine symmetric functions that have occurred in various representation theoretic and enumerative contexts including MacMahon's study of multiset derangements, work of Procesi and Stanley on toric varieties of Coxeter complexes, Stanley's work on chromatic symmetric functions, and the work of the authors on the homology of a certain poset introduced by Björner and Welker.     

Multivariate stable Eulerian polynomials on segmented permutations

Recently, Nunge studied Eulerian polynomials on segmented permutations, namely generalized Eulerian polynomials, and further asked whether their coefficients form unimodal sequences. In this paper, we prove the stability of the generalized Eulerian polynomials and hence confirm Nunge’s conjecture. Our proof is based on Brändén’s stable multivariate Eulerian polynomials. By acting on Brändén’s polynomials with a stability-preserving linear operator, we get a multivariate refinement of the generalized Eulerian polynomials. To prove Nunge’s conjecture, we also develop a general approach to obtain generalized Sturm sequences from bivariate stable polynomials.     

Explicit formulas and recurrence relations for higher order Eulerian polynomials

In the paper, the authors present explicit formulas, nonlinear ordinary differential equations, and recurrence relations for Eulerian polynomials, higher order Eulerian polynomials, and their generating functions in terms of the Stirling numbers of the second kind.     

The pure descent statistic on permutations

We introduce a new statistic based on permutation descents which has a distribution given by the Stirling numbers of the first kind, i.e., with the same distribution as for the number of cycles in permutations. We study this statistic on the sets of permutations avoiding one pattern of length three by giving bivariate generating functions. As a consequence, new classes of permutations enumerated by the Motzkin numbers are obtained. Finally, we deduce results about the popularity of the pure descents in all these restricted sets.     

The symmetric and unimodal expansion of Eulerian polynomials via continued fractions

This paper was motivated by a conjecture of Brändén [P. Brändén, Actions on permutations and unimodality of descent polynomials, European J. Combin. 29 (2) (2008) 514-531] about the divisibility of the coefficients in an expansion of generalized Eulerian polynomials, which implies the symmetric and unimodal property of the Eulerian numbers. We show that such a formula with the conjectured property can be derived from the combinatorial theory of continued fractions. We also discuss an analogous expansion for the corresponding formula for derangements and prove a (p,q)-analogue of the fact that the (-1)-evaluation of the enumerator polynomials of permutations (resp. derangements) by the number of excedances gives rise to tangent numbers (resp. secant numbers). The (p,q)-analogue unifies and generalizes our recent results [H. Shin, J. Zeng, The q-tangent and q-secant numbers via continued fractions, European J. Combin. 31 (7) (2010) 1689-1705] and that of Josuat-Vergès [M. Josuat-Vergés, A q-enumeration of alternating permutations, European J. Combin. 31 (7) (2010) 1892-1906].     

Partial γ-positivity for quasi-Stirling permutations of multisets

We prove that the enumerative polynomials of quasi-Stirling permutations of multisets with respect to the statistics of plateaux, descents and ascents are partial γ-positive, thereby confirming a recent conjecture posed by Lin, Ma and Zhang. This is accomplished by proving the partial γ-positivity of the enumerative polynomials of certain ordered labeled trees, which are in bijection with quasi-Stirling permutations of multisets. As an application, we provide an alternative proof of the partial γ-positivity of the enumerative polynomials on Stirling permutations of multisets.     

On Touchard polynomials

J. Touchard in his work on the cycles of permutations generalized the Bell polynomials in order to study some problems of enumeration of the permutations when the cycles possess certain properties.In the present paper (considering Touchards's generalization) we introduce and study a class of related polynomials. An exponential generating function, recurrence relations and connections with other well-known polynomials are obtained. In special cases, relations with Stirling number of the first and second kind, as well as with other numbers recently studied are derived. Finally, a combinatorial interpretation is discussed.     

Enumeration of labelled threshold graphs and a theorem of frobenius involving eulerian polynomials

We enumerate labelled threshold graphs by the number of vertices, the number of isolated vertices, and the number of distinct vertex-degrees and we give the exact asymptotics for the number of labelled threshold graphs withn vertices. We obtain the appropriate generating function and point out a combinatorial interpretation relating its coefficients to the Stirling numbers of the second kind. We use these results to derive a new proof of a theorem of Frobenius expressing the Eulerian polynomials in terms of the Stirling numbers.     

Permutations with extremal number of fixed points

We extend Stanley's work on alternating permutations with extremal number of fixed points in two directions: first, alternating permutations are replaced by permutations with a prescribed descent set; second, instead of simply counting permutations we study their generating polynomials by number of excedances. Several techniques are used: Désarménien's desarrangement combinatorics, Gessel's hook-factorization and the analytical properties of two new permutation statistics “DEZ” and “lec.” Explicit formulas for the maximal case are derived by using symmetric function tools.     

Counting Simsun Permutations by Descents

We count in the present work simsun permutations of length n by their number of descents. Properties studied include the recurrence relation and real-rootedness of the generating function of the number of n-simsun permutations with k descents. By means of generating function arguments, we show that the descent number is equidistributed over n-simsun permutations and n-André permutations. We also compute the mean and variance of the random variable X _n taking values the descent number of random n-simsun permutations, and deduce that the distribution of descents over random simsun permutations of length n satisfies a central and a local limit theorem as n ?? +???.     

On two unimodal descent polynomials

The descent polynomials of separable permutations and derangements are both demonstrated to be unimodal. Moreover, we prove that the $\gamma$-coefficients of the first are positive with an interpretation parallel to the classical Eulerian polynomial, while the second is spiral, a property stronger than unimodality. Furthermore, we conjecture that they are both real-rooted.     

Signed Permutation Statistics and Cycle Type

We derive a multivariate generating function which counts signed permutations by their cycle type and to other descent statistics, analogous to a result of Gessel and Reutenauer [4.5] for (unsigned) permutations. The derivation uses a bijection which is the hyperoctahedral analogue of Gessel's necklace bijection.     

Descents, inversions, and major indices in permutation groups

A multivariate generating function involving the descent, major index, and inversion statistic first given by Ira Gessel is generalized to other permutation groups. We provide generating functions for variants of these three statistics for the Weyl groups of type B and D, wreath product groups, and multiples of permutations. All of our ideas are combinatorial in nature and exploit fundamental relationships between the elementary and homogeneous symmetric functions.     

Some results related to Hurwitz stability of combinatorial polynomials

Many important problems are closely related to the zeros of certain polynomials derived from combinatorial objects. The aim of this paper is to observe some results and applications for the Hurwitz stability of polynomials in combinatorics and study other related problems.We first present a criterion for the Hurwitz stability of the Turán expressions of recursive polynomials. In particular, it implies the q-log-convexity or q-log-concavity of the original polynomials. We also give a criterion for the Hurwitz stability of recursive polynomials and prove that the Hurwitz stability of any palindromic polynomial implies its semi-γ-positivity, which illustrates that the original polynomial with odd degree is unimodal. In particular, we get that the semi-γ-positivity of polynomials implies their parity-unimodality and the Hurwitz stability of polynomials implies their parity-log-concavity. Those results generalize the connections between real-rootedness, γ-positivity, log-concavity and unimodality to Hurwitz stability, semi-γ-positivity, parity-log-concavity and parity-unimodality (unimodality). As applications of these criteria, we derive some Hurwitz stability results occurred in the literature in a unified manner. In addition, we obtain the Hurwitz stability of Turán expressions for alternating run polynomials of types A and B and the Hurwitz stability for alternating run polynomials defined on a dual set of Stirling permutations.Finally, we study a class of recursive palindromic polynomials and derive many nice properties including Hurwitz stability, semi-γ-positivity, non-γ-positivity, unimodality, strong q-log-convexity, the Jacobi continued fraction expansion and the relation with derivative polynomials. In particular, these properties of the alternating descents polynomials of types A and B can be implied in a unified approach.     

Alternating Eulerian polynomials and left peak polynomials

We first present grammatical interpretations for the alternating Eulerian polynomials of types A and B. As applications, we then derive several properties of the type B alternating Eulerian polynomials, including recurrence relations, generating function and unimodality. And then, we establish an interesting connection between alternating Eulerian polynomials of type B and left peak polynomials, which implies that the type B alternating Eulerian polynomials have gamma-vectors that alternate in sign.     

Cyclotomic factors of the descent set polynomial

We introduce the notion of the descent set polynomial as an alternative way of encoding the sizes of descent classes of permutations. Descent set polynomials exhibit interesting factorization patterns. We explore the question of when particular cyclotomic factors divide these polynomials. As an instance we deduce that the proportion of odd entries in the descent set statistics in the symmetric group Sn only depends on the number on 1's in the binary expansion of n. We observe similar properties for the signed descent set statistics.     

Horse paths, restricted 132-avoiding permutations, continued fractions, and Chebyshev polynomials

Several authors have examined connections among 132-avoiding permutations, continued fractions, and Chebyshev polynomials of the second kind. In this paper we find analogues for some of these results for permutations π avoiding 132 and 1□23 (there is no occurrence π_i<π_j<π_j+1 such that 1?i?j-2) and provide a combinatorial interpretation for such permutations in terms of lattice paths. Using tools developed to prove these analogues, we give enumerations and generating functions for permutations which avoid both 132 and 1□23, and certain additional patterns. We also give generating functions for permutations avoiding 132 and 1□23 and containing certain additional patterns exactly once. In all cases we express these generating functions in terms of Chebyshev polynomials of the second kind.