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.     

Signatures of Strings

The parity of a permutation π can be defined as the parity of the number of inversions in π. The signature ε(π) of π is an encoding of the parity in a multiplicative group of order 2: ε(π) = (?1)^inv(π). It is also well known that half of the permutations of a finite set are even and half are odd. In this paper, we explore the natural notion of parity for larger moduli; that is, we define the m-signature of a permutation π to be the number of inversions of π, reduced modulo m. Unlike with the 2-signatures of permutations of sets, the m-signatures of the permutations of a multiset are not typically equi-distributed among the modulo m residue classes, though the distribution is close to uniform. We present a recursive method of calculating the distribution of m-signatures of permutations of a multiset, develop properties of this distribution, and present sufficient conditions for the distribution to be uniform.     

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.     

The Möbius function of separable and decomposable permutations

We give a recursive formula for the Möbius function of an interval [σ,π] in the poset of permutations ordered by pattern containment in the case where π is a decomposable permutation, that is, consists of two blocks where the first one contains all the letters 1,2,…,k for some k. This leads to many special cases of more explicit formulas. It also gives rise to a computationally efficient formula for the Möbius function in the case where σ and π are separable permutations. A permutation is separable if it can be generated from the permutation 1 by successive sums and skew sums or, equivalently, if it avoids the patterns 2413 and 3142.We also show that the Möbius function in the poset of separable permutations admits a combinatorial interpretation in terms of normal embeddings among permutations. A consequence of this interpretation is that the Möbius function of an interval [σ,π] of separable permutations is bounded by the number of occurrences of σ as a pattern in π. Another consequence is that for any separable permutation π the Möbius function of (1,π) is either 0, 1 or −1.     

Block decomposition of permutations and Schur-positivity

The block number of a permutation is the maximum number of components in its expression as a direct sum. We show that, for 321-avoiding permutations, the set of left-to-right maxima has the same distribution when the block number is assumed to be k, as when the last descent of the inverse is assumed to be at position \(n - k\). This result is analogous to the Foata–Schützenberger equidistribution theorem, and implies that the quasi-symmetric generating function of the descent set over 321-avoiding permutations with a prescribed number of blocks is Schur-positive.     

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.     

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.     

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.     

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 ?? +???.     

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.     

Generating indecomposable permutations

An indecomposable permutation π on [n] is one such that π([m])=[m] for no m<n. We consider indecomposable permutations and give a new, inclusive enumerative recurrence for them. This recurrence allows us to generate all indecomposable permutations of length n in transposition Gray code order, in constant amortized time (CAT). We also present a CAT generation algorithm for indecomposable permutations which is based on the Johnson-Trotter algorithm for generating all permutations of length n. The question of whether or not there exists an adjacent transposition Gray code for indecomposable permutations remains open.     

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.     

Reconstruction of permutations distorted by reversal errors

The problem of reconstructing permutations on n elements from their erroneous patterns which are distorted by reversal errors is considered in this paper. Reversals are the operations reversing the order of a substring of a permutation. To solve this problem, it is essential to investigate structural and combinatorial properties of a corresponding Cayley graph on the symmetric group Sym_n generated by reversals. It is shown that for any n?3 an arbitrary permutation π is uniquely reconstructible from four distinct permutations at reversal distance at most one from π where the reversal distance is defined as the least number of reversals needed to transform one permutation into the other. It is also proved that an arbitrary permutation is reconstructible from three permutations with a probability p₃→1 and from two permutations with a probability as n→∞. A reconstruction algorithm is presented. In the case of at most two reversal errors it is shown that at least erroneous patterns are required in order to reconstruct an arbitrary permutation.     

On the complexity of crossings in permutations

We investigate crossing minimization problems for a set of permutations, where a crossing expresses a disarrangement between elements. The goal is a common permutation π^∗ which minimizes the number of crossings. In voting and social science theory this is known as the Kemeny optimal aggregation problem minimizing the Kendall-τ distance. This rank aggregation problem can be phrased as a one-sided two-layer crossing minimization problem for a series of bipartite graphs or for an edge coloured bipartite graph, where crossings are counted only for monochromatic edges. We contribute the max version of the crossing minimization problem, which attempts to minimize the discrimination against any permutation. As our results, we correct the construction from [C. Dwork, R. Kumar, M. Noar, D. Sivakumar, Rank aggregation methods for the Web, Proc. WWW10 (2001) 613-622] and prove the NP-hardness of the common crossing minimization problem for k=4 permutations. Then we establish a 2−2/k-approximation, improving the previous factor of 2. The max version is shown NP-hard for every k≥4, and there is a 2-approximation. Both approximations are optimal, if the common permutation is selected from the given ones. For two permutations crossing minimization is solved by inspecting the drawings, whereas it remains open for three permutations.     

On the Lipschitz constant of the RSK correspondence

We view the RSK correspondence as associating to each permutation π∈Sn a Young diagram λ=λ(π), i.e. a partition of n. Suppose now that π is left-multiplied by t transpositions, what is the largest number of cells in λ that can change as a result? It is natural refer to this question as the search for the Lipschitz constant of the RSK correspondence.We show upper bounds on this Lipschitz constant as a function of t. For t=1, we give a construction of permutations that achieve this bound exactly. For larger t we construct permutations which come close to matching the upper bound that we prove.     

Combinatorial Hopf algebras, noncommutative Hall-Littlewood functions, and permutation tableaux

We introduce a new family of noncommutative analogues of the Hall-Littlewood symmetric functions. Our construction relies upon Tevlin's bases and simple q-deformations of the classical combinatorial Hopf algebras. We connect our new Hall-Littlewood functions to permutation tableaux, and also give an exact formula for the q-enumeration of permutation tableaux of a fixed shape. This gives an explicit formula for: the steady state probability of each state in the partially asymmetric exclusion process (PASEP); the polynomial enumerating permutations with a fixed set of weak excedances according to crossings; the polynomial enumerating permutations with a fixed set of descent bottoms according to occurrences of the generalized pattern 2-31.     

The bireflections of a permutation

A bireflection of a permutation θ is an ordered pair (φ, ψ) of permutations satisfying φ² = ψ² = 1, θ = φψ. The family of bireflections of a permutation is studied. As a corollary an expression for the number of dihedral groups over θ in S_A is obtained.     

Permutations and β-shifts

Given a real number β>1, a permutation π of length n is realized by the β-shift if there is some x∈[0,1] such that the relative order of the sequence x,f(x),…,fn−1(x), where f(x) is the fractional part of βx, is the same as that of the entries of π. Widely studied from such diverse fields as number theory and automata theory, β-shifts are prototypical examples of one-dimensional chaotic dynamical systems. When β is an integer, permutations realized by shifts were studied in Elizalde (2009) [5]. In this paper we generalize some of the results to arbitrary β-shifts. We describe a method to compute, for any given permutation π, the smallest β such that π is realized by the β-shift. We also give a way to determine the length of the shortest forbidden (i.e., not realized) pattern of an arbitrary β-shift.     

Counting permutations by successions and other figures

Let π=(π(1), π(2),…, π(n)) be a permutation of the arbitrary n-set S of positive integers. A p-succession (alternately, p-rise) in π is any pair π(i), π(i+1) with π(i+1)=π(i)+1p, i=1,2,…, n-1 (alternately, π(i+1)?π(i)+p). A succession (alternately, rise) is just a p-succession (alternately, p-rise) with p=1. A p-run in π is a subsequence i, i+1,…,i+p-1 of the permutation π. We show that the number of permutations of S which have precisely α rises and β successions depends only on n=¦S¦, α, β, and l, where l is the number of maximal subsets {i,i+1,…,i+j)} of S, and determine an explicit recursion and generating function for these numbers. The same methodology is applied to count permutations of S by number of rises and figures of a more general type, where a specific criterion characterizes such figures. As a special case, we obtain the generating function when the figure is a p-run. Finally, we enumerate permutations of S by number of p-successions. Additional results are provided relating this particular enumeration problem to the special case of ordinary successions (p=1).