Restricted Simsun Permutations

A permutation is simsun if for all k, the subword of the one-line notation consisting of the k smallest entries does not have three consecutive decreasing elements. Simsun permutations were introduced by Simion and Sundaram, who showed that they are counted by the Euler numbers. In this paper we enumerate simsun permutations avoiding a pattern or a set of patterns of length 3. The results involve Motkzin, Fibonacci, and secondary structure numbers. The techniques in the proofs include generating functions, bijections into lattice paths and generating trees.     

Descent pattern avoidance

We extend the notion of consecutive pattern avoidance to considering sums over all permutations where each term is a product of weights depending on each consecutive pattern of a fixed length. We study the problem of finding the asymptotics of these sums. Our technique is to extend the spectral method of Ehrenborg, Kitaev and Perry. When the weight depends on the descent pattern we show how to find the equation determining the spectrum. We give two length 4 applications. First, we find the asymptotics of the number of permutations with no triple ascents and no triple descents. Second, we give the asymptotics of the number of permutations with no isolated ascents or descents. Our next result is a weighted pattern of length 3 where the associated operator only has one non-zero eigenvalue. Using generating functions we show that the error term in the asymptotic expression is the smallest possible.     

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.     

Restricted 123-avoiding Baxter permutations and the Padovan numbers

Baxter studied a particular class of permutations by considering fixed points of the composite of commuting functions. This class is called Baxter permutations. In this paper we investigate the number of 123-avoiding Baxter permutations of length n that also avoid (or contain a prescribed number of occurrences of) another certain pattern of length k. In several interesting cases the generating function depends only on k and is expressed via the generating function for the Padovan numbers.     

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.     

Cyclic Descents and <Emphasis Type="Italic">P</Emphasis>-Partitions

Louis Solomon showed that the group algebra of the symmetric group _n has a subalgebra called the descent algebra, generated by sums of permutations with a given descent set. In fact, he showed that every Coxeter group has something that can be called a descent algebra. There is also a commutative, semisimple subalgebra of Solomon's descent algebra generated by sums of permutations with the same number of descents: an “Eulerian” descent algebra. For any Coxeter group that is also a Weyl group, Paola Cellini proved the existence of a different Eulerian subalgebra based on a modified definition of descent. We derive the existence of Cellini's subalgebra for the case of the symmetric group and of the hyperoctahedral group using a variation on Richard Stanley's theory of P-partitions.     

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.     

Generating Functions for Alternating Descents and Alternating Major Index

In 2008, Chebikin introduced the alternating descent set, AltDes(??), of a permutation ?? =??? ₁ ··· ?? _n in the symmetric group S _n as the set of all i such that either i is odd and ?? _i >??? _i+1 or i is even and ?? _i <??? _i+1. We can then define altdes(??) =?|AltDes(??)| and ${{\rm altmaj}(\sigma) = \sum_{i \in AltDes(\sigma)}i}$ . In this paper, we compute a generating function for the joint distribution of altdes(??) and altmaj(??) over S _n . Our formula is similar to the formula for the joint distribution of des and maj over the symmetric group that was first proved by Gessel. We also compute similar generating functions for the groups B _n and D _n and for r-tuples of permutations in S _n . Finally we prove a general extension of these formulas in cases where we keep track of descents only at positions r, 2r, . . ..     

Enumerating set partitions according to the number of descents of size d or more

Let P(n, k) denote the set of partitions of {1, 2, ..., n} having exactly k blocks. In this paper, we find the generating function which counts the members of P(n, k) according to the number of descents of size d or more, where d????1 is fixed. An explicit expression in terms of Stirling numbers of the second kind may be given for the total number of such descents in all the members of P(n, k). We also compute the generating function for the statistics recording the number of ascents of size d or more and show that it has the same distribution on P(n, k) as the prior statistics for descents when d????2, by both algebraic and combinatorial arguments.     

Asymptotics of the moments of the number of cycles of a random A-permutation

We consider random permutations uniformly distributed on the set of all permutations of degree n whose cycle lengths belong to a fixed set A (the so-called A-permutations). In the present paper, we establish an asymptotics of the moments of the total number of cycles and of the number of cycles of given length of this random permutation as n → ∞.