Permutations and words counted by consecutive patterns

Generating functions which count occurrences of consecutive sequences in a permutation or a word which matches a given pattern are studied by exploiting the combinatorics associated with symmetric functions. Our theorems take the generating function for the number of permutations which do not contain a certain pattern and give generating functions refining permutations by the both the total number of pattern matches and the number of non-overlapping pattern matches. Our methods allow us to give new proofs of several previously recorded results on this topic as well as to prove new extensions and new q-analogues of such results.     

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 Enumeration of Maximally Clustered Permutations

The maximally clustered permutations are characterized by avoiding the classical permutation patterns {3421, 4312, 4321}. This class contains the freely braided permutations and the fully commutative permutations. In this work, we show that the generating functions for certain fully commutative pattern classes can be transformed to give generating functions for the corresponding freely braided and maximally clustered pattern classes. Moreover, this transformation of generating functions is rational. As a result, we obtain enumerative formulas for the pattern classes mentioned above as well as the corresponding hexagon-avoiding pattern classes where the hexagon-avoiding permutations are characterized by avoiding {46718235, 46781235, 56718234, 56781234}.     

Restricted colored permutations and Chebyshev polynomials

Several authors have examined connections between restricted permutations and Chebyshev polynomials of the second kind. In this paper we prove analogues of these results for colored permutations. First we define a distinguished set of length two and length three patterns, which contains only 312 when just one color is used. Then we give a recursive procedure for computing the generating function for the colored permutations which avoid this distinguished set and any set of additional patterns, which we use to find a new set of signed permutations counted by the Catalan numbers and a new set of signed permutations counted by the large Schröder numbers. We go on to use this result to compute the generating functions for colored permutations which avoid our distinguished set and any layered permutation with three or fewer layers. We express these generating functions in terms of Chebyshev polynomials of the second kind and we show that they are special cases of generating functions for involutions which avoid 3412 and a layered permutation.     

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 X-Class and Almost-Increasing Permutations

In this paper we give a bijection between the class of permutations that can be drawn on an X-shape and a certain set of permutations that appears in Knuth [4] in connection to sorting algorithms. A natural generalization of this set leads us to the definition of almost-increasing permutations, which is a one-parameter family of permutations that can be characterized in terms of forbidden patterns. We find generating functions for almost-increasing permutations by using their cycle structure to map them to colored Motzkin paths. We also give refined enumerations with respect to the number of cycles, fixed points, excedances, and inversions.     

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.     

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.     

Generating Functions for Permutations Avoiding a Consecutive Pattern

Given a permutation τ of length j, we say that a permutation σ has a τ-match starting at position i, if the elements in positions i, i+1, . . . , i+j−1 in σ have the same relative order as the elements of τ. We have been able to take advantage of the results of Mendes and Remmel [1] to obtain a generating function for the number of permutations with no τ-matches for several new classes of permutations. These new classes include a large class of permutations which are shuffles of an increasing sequence 1 2 · · · n with an arbitrary permutation σ of the integers {n + 1, . . . , n + m}. Finally we give a formula for the generating function for the number of permutations which have no 1 3 2 4-matches.     

Simple permutations and pattern restricted permutations

A simple permutation is one that does not map any non-trivial interval onto an interval. It is shown that, if the number of simple permutations in a pattern restricted class of permutations is finite, the class has an algebraic generating function and is defined by a finite set of restrictions. Some partial results on classes with an infinite number of simple permutations are given. Examples of results obtainable by the same techniques are given; in particular it is shown that every pattern restricted class properly contained in the 132-avoiding permutations has a rational generating function.     

On the generating function for consecutively weighted permutations

We show that the analytic continuation of the exponential generating function associated to consecutive weighted pattern enumeration of permutations only has poles and no essential singularities. The proof uses the connection between permutation enumeration and functional analysis, and as well as the Laurent expansion of the associated resolvent. As a consequence, we give a partial answer to a question of Elizalde and Noy: when is the multiplicative inverse of the exponential generating function for the number permutations avoiding a single pattern an entire function? Our work implies that it is enough to verify that this function has no zeros to conclude that the inverse function is entire.     

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.     

Stable multivariate Eulerian polynomials and generalized Stirling permutations

We study Eulerian polynomials as the generating polynomials of the descent statistic over Stirling permutations—a class of restricted multiset permutations. We develop their multivariate refinements by indexing variables by the values at the descent tops, rather than the position where they appear. We prove that the obtained multivariate polynomials are stable, in the sense that they do not vanish whenever all the variables lie in the open upper half-plane. Our multivariate construction generalizes the multivariate Eulerian polynomial for permutations, and extends naturally to r-Stirling and generalized Stirling permutations.The benefit of this refinement is manifold. First of all, the stability of the multivariate generating functions implies that their univariate counterparts, obtained by diagonalization, have only real roots. Second, we obtain simpler recurrences of a general pattern, which allows for essentially a single proof of stability for all the cases, and further proofs of equidistributions among different statistics. Our approach provides a unifying framework of some recent results of Bóna, Brändén, Brenti, Janson, Kuba, and Panholzer. We conclude by posing several interesting open problems.     

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.     

Partially Ordered Generalized Patterns and <Emphasis Type="Italic">k</Emphasis>-ary Words

Recently, Kitaev [9] introduced partially ordered generalized patterns (POGPs) in the symmetric group, which further generalize the generalized permutation patterns introduced by Babson and Steingrímsson [1]. A POGP p is a GP some of whose letters are incomparable. In this paper, we study the generating functions (g.f.) for the number of k-ary words avoiding some POGPs. We give analogues, extend and generalize several known results, as well as get some new results. In particular, we give the g.f. for the entire distribution of the maximum number of non-overlapping occurrences of a pattern p with no dashes (which is allowed to have repetition of letters), provided we know the g.f. for the number of k-ary words that avoid p.AMS Subject Classification: 05A05, 05A15.     

Restricted 1-3-2 Permutations and Generalized Patterns

Recently, Babson and Steingrimsson (see [2]) introduced generalized permutations patterns that allow the requirement that two adjacent letters in a pattern must be adjacent in the permutation. We study generating functions for the number of permutations on n letters avoiding 1-3-2 (or containing 1-3-2 exactly once) and an arbitrary generalized pattern t \tau on k letters, or containing t \tau exactly once. In several cases, the generating function depends only on k and can be expressed via Chebyshev polynomials of the second kind, and the generating function of Motzkin numbers.     

Partially Well-Ordered Closed Sets of Permutations

It is known that the pattern containment order on permutations is not a partial well-order. Nevertheless, many naturally defined subsets of permutations are partially well-ordered, in which case they have a strong finite basis property. Several classes are proved to be partially well-ordered under pattern containment. Conversely, a number of new antichains are exhibited that give some insight as to where the boundary between partially well-ordered and not partially well-ordered classes lies.     

Asymptotics of multivariate sequences, part III: Quadratic points

We consider a number of combinatorial problems in which rational generating functions may be obtained, whose denominators have factors with certain singularities. Specifically, there exist points near which one of the factors is asymptotic to a nondegenerate quadratic. We compute the asymptotics of the coefficients of such a generating function. The computation requires some topological deformations as well as Fourier–Laplace transforms of generalized functions. We apply the results of the theory to specific combinatorial problems, such as Aztec diamond tilings, cube groves, and multi-set permutations.     

Gray code for permutations with a fixed number of cycles

We give the first Gray code for the set of n-length permutations with a given number of cycles. In this code, each permutation is transformed into its successor by a product with a cycle of length three, which is optimal. If we represent each permutation by its transposition array then the obtained list still remains a Gray code and this allows us to construct a constant amortized time (CAT) algorithm for generating these codes. Also, Gray code and generating algorithm for n-length permutations with fixed number of left-to-right minima are discussed.     

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.