Some polynomials associated with the $${\vavec{}}$$-Whitney numbes

In the present article, we study three families of polynomials associated with the r-Whitney numbers of the second kind. They are the r-Dowling polynomials, r-Whitney–Fubini polynomials and the r-Eulerian–Fubini polynomials. Then we derive several combinatorial results by using algebraic arguments (Rota’s method), combinatorial arguments (set partitions) and asymptotic methods.     

Generalizations of Eulerian partially ordered sets, flag numbers, and the Möbius function

A partially ordered set is r-thick if every nonempty open interval contains at least r elements. This paper studies the flag vectors of graded, r-thick posets and shows the smallest convex cone containing them is isomorphic to the cone of flag vectors of all graded posets. It also defines a k-analogue of the Möbius function and k-Eulerian posets, which are 2k-thick. Several characterizations of k-Eulerian posets are given. The generalized Dehn-Sommerville equations are proved for flag vectors of k-Eulerian posets. A new inequality is proved to be valid and sharp for rank 8 Eulerian posets.ResumeUn ensemble partiellement ordonné est r-épais si chacun de ses intervalles ouverts non-vides contient au moins r éléments. Dans cet article nous étudions les vecteurs drapeaux des ensembles partiellement ordonnés gradués r-épais. Nous démontrons que le cône le plus petit contenant ces vecteurs est isomorphe au cône des vecteurs drapeaux des ensembles partiellement ordonnés gradués quelconques. Nous définissons aussi un k-analogue de la fonction de Möbius et des ensembles partiellement ordonnés k-eulériens qui sont 2k-épais. Nous caractérisons les ensembles partiellement ordonnés k-eulériens de plusieurs manières, et généralisons les équations de Dehn-Sommerville pour le vecteur drapeaux d'un ensemble partiellement ordonné k-eulérien. Nous démontrons une nouvelle inégalité optimale pour les ensembles partiellement ordonnés eulériens de rang 8.     

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.     

A note on q-Eulerian numbers

The paper contains a combinatorial interpretation of the q-Eulerian numbers suggested by H. O. Foulkes' combinatorial interpretation of the ordinary Eulerian numbers. Some applications are also given.     

A Simple Recurrence for Covers of the Sphere With Branch Points of Arbitrary Ramification

The problem of counting ramified covers of a Riemann surface up to homeomorphism was proposed by Hurwitz in the late 1800’s. This problem translates combinatorially into factoring a permutation of specified cycle type, with certain conditions on the cycle types of the factors, such as minimality and transitivity. Goulden and Jackson have given a proof for the number of minimal, transitive factorizations of a permutation into transpositions. This proof involves a partial differential equation for the generating series, called the Join-Cut equation. Recently, Bousquet-Mélou and Schaeffer have found the number of minimal, transitive factorizations of a permutation into arbitrary unspecified factors. This was proved by a purely combinatorial argument, based on a direct bijection between factorizations and certain objects called m-Eulerian trees. In this paper, we give a simple partial differential equation for Bousquet-Mélou and Schaeffer’s generating series, and for Goulden and Jackson’s generating series, as well as a new proof of the result by Bousquet-Mélou and Schaeffer. We apply algebraic methods based on Lagrange’s theorem, and combinatorial methods based on a new use of Bousquet-Mélou and Schaeffer’s m-Eulerian trees. Supported by a Discovery Grant from NSERC. Research supported by a Postgraduate Scholarship from NSERC. Received October 8, 2005     

A characterization of permutations via skew-hooks

A characterization of permutations is given using skew-hooks, such that the r-descents of the permutation are reflected in the structure of the skew-hook. The characterization yields a combinatorial proof of Foulkes' skew-hook rule for computing Eulerian numbers.     

Two new triangles of q-integers via q-Eulerian polynomials of type A and B

The classical Eulerian polynomials can be expanded in the basis t ^k?1(1+t) ^n+1?2k (1≤k≤?(n+1)/2?) with positive integral coefficients. This formula implies both the symmetry and the unimodality of the Eulerian polynomials. In this paper, we prove a q-analogue of this expansion for Carlitz’s q-Eulerian polynomials as well as a similar formula for Chow–Gessel’s q-Eulerian polynomials of type B. We shall give some applications of these two formulas, which involve two new sequences of polynomials in the variable q with positive integral coefficients. It is an open problem to give a combinatorial interpretation for these polynomials.     

The peak and descent statistics over ballot permutations

A ballot permutation is a permutation π such that in any prefix of π the descent number is not more than the ascent number. By using a reversal-concatenation map, we (i) give a formula for the joint distribution (pk, des) of the peak and descent statistics over ballot permutations, (ii) connect this distribution and the joint distribution (pk, des) over ordinary permutations in terms of generating functions, and (iii) confirm Spiro's conjecture which finds the equidistribution of the descent statistic for ballot permutations and an analogue of the descent statistic for odd order permutations.     

A construction for equidistant permutation arrays of index one

An equidistant permutation array (EPA) which we denote by A(r, λ; ν) is a ν × r array such that every row is a permutation of the integers 1, 2,…, r and such that every pair of distinct rows has precisely λ columns in common. R(r, λ) is the maximum ν such that there exists an A(r, λ; ν). In this paper we show that R(n² + n + 2, 1) ? 2n² + n where n is a prime power.     

New permutation statistics: Variation and a variant

For each permutation π we introduce the variation statistic of π, as the total number of elements on the right between each two adjacent elements of π. We modify this new statistic to get a slightly different variant, which behaves more closely like Mahonian statistics such as maj. In this paper we find an explicit formula for the generating function for the number of permutations of length n according to the variation statistic, and for that according to the modified version.     

Major index for 01-fillings of moon polyominoes

We propose a major index statistic on 01-fillings of moon polyominoes which, when specialized to certain shapes, reduces to the major index for permutations and set partitions. We consider the set F(M,s;A) of all 01-fillings of a moon polyomino M with given column sum s whose empty rows are A, and prove that this major index has the same distribution as the number of north-east chains, which are the natural extension of inversions (resp. crossings) for permutations (resp. set partitions). Hence our result generalizes the classical equidistribution results for the permutation statistics inv and maj. Two proofs are presented. The first is an algebraic one using generating functions, and the second is a bijection on 01-fillings of moon polyominoes in the spirit of Foata's second fundamental transformation on words and permutations.     

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.     

Adjacent q-Cycles in Permutations

We introduce a new permutation statistic, namely, the number of cycles of length q consisting of consecutive integers, and consider the distribution of this statistic among the permutations of {1, 2, . . . , n}. We determine explicit formulas, recurrence relations, and ordinary and exponential generating functions. A generalization to more than one fixed length is also considered.     

Applications of conditional power function of two-sample permutation test

Permutation or randomization test is a nonparametric test in which the null distribution (distribution under the null hypothesis of no relationship or no effect) of the test statistic is attained by calculating the values of the test statistic overall permutations (or by considering a large number of random permutation) of the observed dataset. The power of permutation test evaluated based on the observed dataset is called conditional power. In this paper, the conditional power of permutation tests is reviewed. The use of the conditional power function for sample size estimation is investigated. Moreover, reproducibility and generalizability probabilities are defined. The use of these probabilities for sample size adjustment is shown. Finally, an illustration example is used.     

The maximal-inversion statistic and pattern-avoiding permutations

We define a new combinatorial statistic, maximal-inversion, on a permutation. We remark that the number M(n,k) of permutations in S_n with k maximal-inversions is the signless Stirling number c(n,n−k) of the first kind. A permutation π in S_n is uniquely determined by its maximal-inversion set . We prove it by making an algorithm for retrieving the permutation from its maximal-inversion set. Also, we remark on how the algorithm can be used directly to determine whether a given set is the maximal-inversion set of a permutation. As an application of the algorithm, we characterize the maximal-inversion set for pattern-avoiding permutations. Then we give some enumerative results concerning permutations with forbidden patterns.     

Minimal polynomials of Young permutation modules and idempotents

Applying an epimorphism of the Solomon descent algebra onto the subring of the Green ring spanned by the isomorphism classes of Young permutation modules, we determine a basis of primitive orthogonal idempotents which diagonalise the multiplication maps of Young permutation modules. We determine direct sum decompositions of tensor products of hook Young permutation modules, the minimal polynomials of all Young permutation modules, and of the Young module Y^(r?1,1).     

From Bruhat intervals to intersection lattices and a conjecture of Postnikov

We prove the conjecture of A. Postnikov that (A) the number of regions in the inversion hyperplane arrangement associated with a permutation w∈Sn is at most the number of elements below w in the Bruhat order, and (B) that equality holds if and only if w avoids the patterns 4231, 35142, 42513 and 351624. Furthermore, assertion (A) is extended to all finite reflection groups.A byproduct of this result and its proof is a set of inequalities relating Betti numbers of complexified inversion arrangements to Betti numbers of closed Schubert cells. Another consequence is a simple combinatorial interpretation of the chromatic polynomial of the inversion graph of a permutation which avoids the above patterns.     

On the reconstruction index of permutation groups: semiregular groups

Summary. The reconstruction index of all semiregular permutation groups is determined. We show that this index satisfies 3 ￡ r(G, W) ￡ 5 3 \leq \rho(G, \Omega) \leq 5 and we classify the groups in each case.     

The number of flags in finite vector spaces: asymptotic normality and Mahonian statistics

We study the generalized Galois numbers which count flags of length r in N-dimensional vector spaces over finite fields. We prove that the coefficients of those polynomials are asymptotically Gaussian normally distributed as N becomes large. Furthermore, we interpret the generalized Galois numbers as weighted inversion statistics on the descent classes of the symmetric group on N elements and identify their asymptotic limit as the Mahonian inversion statistic when r approaches ∞. Finally, we apply our statements to derive further statistical aspects of generalized Rogers–Szeg? polynomials, reinterpret the asymptotic behavior of linear q-ary codes and characters of the symmetric group acting on subspaces over finite fields, and discuss implications for affine Demazure modules and joint probability generating functions of descent-inversion statistics.     

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.