Permutation tableaux and permutation patterns

In this paper we introduce and study a class of tableaux which we call permutation tableaux; these tableaux are naturally in bijection with permutations, and they are a distinguished subset of the -diagrams of Alex Postnikov [A. Postnikov, Webs in totally positive Grassmann cells, in preparation; L. Williams, Enumeration of totally positive Grassmann cells, Adv. Math. 190 (2005) 319-342]. The structure of these tableaux is in some ways more transparent than the structure of permutations; therefore we believe that permutation tableaux will be useful in furthering the understanding of permutations. We give two bijections from permutation tableaux to permutations. The first bijection carries tableaux statistics to permutation statistics based on relative sizes of pairs of letters in a permutation and their places. We call these statistics weak excedance statistics because of their close relation to weak excedances. The second bijection carries tableaux statistics (via the weak excedance statistics) to statistics based on generalized permutation patterns. We then give enumerative applications of these bijections. One nice consequence of these results is that the polynomial enumerating permutation tableaux according to their content generalizes both Carlitz' q-analog of the Eulerian numbers [L. Carlitz, q-Bernoulli and Eulerian numbers, Trans. Amer. Math. Soc. 76 (1954) 332-350] and the more recent q-analog of the Eulerian numbers found in [L. Williams, Enumeration of totally positive Grassmann cells, Adv. Math. 190 (2005) 319-342]. We conclude our paper with a list of open problems, as well as remarks on progress on these problems which has been made by A. Burstein, S. Corteel, N. Eriksen, A. Reifegerste, and X. Viennot.     

The Abelian sandpile model on Ferrers graphs — A classification of recurrent configurations

We classify all recurrent configurations of the Abelian sandpile model (ASM) on Ferrers graphs. The classification is in terms of decorations of EW-tableaux, which undecorated are in bijection with the minimal recurrent configurations. We introduce decorated permutations, extending to decorated EW-tableaux a bijection between such tableaux and permutations, giving a direct bijection between the decorated permutations and all recurrent configurations of the ASM. We also describe a bijection between the decorated permutations and the intransitive trees of Postnikov, the breadth-first search of which corresponds to a canonical toppling of the corresponding configurations.     

Bijections between pattern-avoiding fillings of Young diagrams

The pattern-avoiding fillings of Young diagrams we study arose from Postnikov's work on positive Grassmann cells. They are called -diagrams, and are in bijection with decorated permutations. Other closely-related fillings are interpreted as acyclic orientations of some bipartite graphs. The definition of the diagrams is the same but the avoided patterns are different. We give here bijections proving that the number of pattern-avoiding filling of a Young diagram is the same, for these two different sets of patterns. The result was obtained by Postnikov via a recurrence relation. This relation was extended by Spiridonov to obtain more general results about other patterns and other polyominoes than Young diagrams, and we show that our bijections also extend to more general polyominoes.     

Pattern avoidance for alternating permutations and Young tableaux

We define a class Ln,k of permutations that generalizes alternating (up-down) permutations and give bijective proofs of certain pattern-avoidance results for this class. As a special case of our results, we give bijections between the set A2n(1234) of alternating permutations of length 2n with no four-term increasing subsequence and standard Young tableaux of shape 〈n³〉, and between the set A2n+1(1234) and standard Young tableaux of shape 〈³n−1,2,1〉. This represents the first enumeration of alternating permutations avoiding a pattern of length four. We also extend previous work on doubly-alternating permutations (alternating permutations whose inverses are alternating) to our more general context.The set Ln,k may be viewed as the set of reading words of the standard Young tableaux of a certain skew shape. In the last section of the paper, we expand our study to consider pattern avoidance in the reading words of standard Young tableaux of any skew shape. We show bijectively that the number of standard Young tableaux of shape λ/μ whose reading words avoid 213 is a natural μ-analogue of the Catalan numbers (and in particular does not depend on λ, up to a simple technical condition), and that there are similar results for the patterns 132, 231 and 312.     

Evacuation and a geometric construction for Fibonacci tableaux

Tableaux have long been used to study combinatorial properties of permutations and multiset permutations. Discovered independently by Robinson and Schensted and generalized by Knuth, the Robinson–Schensted correspondence has provided a fundamental tool for relating permutations to tableaux. In 1963, Schützenberger defined a process called evacuation on standard tableaux which gives a relationship between the pairs of tableaux (P,Q) resulting from the Schensted correspondence for a permutation and both the reverse and the complement of that permutation. Viennot gave a geometric construction for the Schensted correspondence and Fomin described a generalization of the correspondence which provides a bijection between permutations and pairs of chains in Young's lattice.In 1975, Stanley defined a Fibonacci lattice and in 1988 he introduced the idea of a differential poset. Roby gave an insertion algorithm, analogous to the Schensted correspondence, for mapping a permutation to a pair of Fibonacci tableaux. The main results of this paper are to give an evacuation algorithm for the Fibonacci tableaux that is analogous to the evacuation algorithm on Young tableaux and to describe a geometric construction for the Fibonacci tableaux that is similar to Viennot's geometric construction for Young tableaux.     

A Bijection from Staircase Tableaux to Inversion Tables,Giving Some Eulerian and Mahonian Statistics

We give a simple bijection between staircase tableaux and inversion tables. Some nice properties of the bijection allow us to easily compute the generating polynomials of subsets of the staircase tableaux. We also give a combinatorial interpretation of some statistics of these tableaux in terms of permutations.     

Generalized Stirling permutations, families of increasing trees and urn models

Bóna (2007) [6] studied the distribution of ascents, plateaux and descents in the class of Stirling permutations, introduced by Gessel and Stanley (1978) [13]. Recently, Janson (2008) [17] showed the connection between Stirling permutations and plane recursive trees and proved a joint normal law for the parameters considered by Bóna. Here we will consider generalized Stirling permutations extending the earlier results of Bóna (2007) [6] and Janson (2008) [17], and relate them with certain families of generalized plane recursive trees, and also (k+1)-ary increasing trees. We also give two different bijections between certain families of increasing trees, which both give as a special case a bijection between ternary increasing trees and plane recursive trees. In order to describe the (asymptotic) behaviour of the parameters of interests, we study three (generalized) Pólya urn models using various methods.     

A Matrix-analog for Viennot's construction of the Robinson correspondence

The notion of Viennot matrix which is here introduced provides a convenient combinatorial set-up to describe the Robinson correspondence between permutations and pairs of Young tableaux. By means of that set-up a Simon-Newcomb property is reproved in a simple manner.     

Alternating permutations and binary increasing trees

In [3], Foata and Schützenberger prove that the binary increasing trees are equinumerous with half of the alternating permutations considered by André [1].In this paper we present a direct recursive proof of this fact, and then exhibit a natural bijection between the two families. In the process a second class of permutations, which forms a main concern of Foata and Schützenberger's paper, is encountered in a natural setting.     

Ribbon tableaux, ribbon rigged configurations and Hall-Littlewood functions at roots of unity

Hall-Littlewood functions indexed by rectangular partitions, specialized at primitive roots of unity, can be expressed as plethysms. We propose a combinatorial proof of this formula using Schilling's bijection between ribbon tableaux and ribbon rigged configurations.     

Restricted Dumont permutations, Dyck paths, and noncrossing partitions

We complete the enumeration of Dumont permutations of the second kind avoiding a pattern of length 4 which is itself a Dumont permutation of the second kind. We also consider some combinatorial statistics on Dumont permutations avoiding certain patterns of length 3 and 4 and give a natural bijection between 3142-avoiding Dumont permutations of the second kind and noncrossing partitions that uses cycle decomposition, as well as bijections between 132-, 231- and 321-avoiding Dumont permutations and Dyck paths. Finally, we enumerate Dumont permutations of the first kind simultaneously avoiding certain pairs of 4-letter patterns and another pattern of arbitrary length.     

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.     

On the Orthogonal Tableaux of Koike and Terada

Many different definitions have been given for semistandard odd and even orthogonal tableaux which enumerate the corresponding irreducible orthogonal characters. Weightpreserving bijections have been provided between some of these sets of tableaux (see [3], [8]). We give bijections between the (semistandard) odd orthogonal Koike-Terada tableaux and the odd orthogonal Sundaram-tableaux and between the even orthogonal Koike-Terada tableaux and the even orthogonal King-Welsh tableaux. As well, we define an even version of orthogonal Sundaram tableaux which enumerate the irreducible characters of O(2n).     

Stack words, standard Young tableaux, permutations with forbidden subsequences and planar maps

Stack words stem from studies on stack-sortable permutations and represent classical combinatorial objects such as standard Young tableaux, permutations with forbidden sequences and planar maps. We extend existing enumerative results on stack words and we also obtain new results. In particular, we make a correspondence between nonseparable 3×n rectangular standard Young tableaux (or stack words where elements satisfy a ‘Towers of Hanoi’ condition) and nonseparable cubic rooted planar maps with 2n vertices enumerated by 2ⁿ(3n)!/((2n+1)!(n+1)!). Moreover, these tableaux without two consecutive integers in the same row are in bijection with nonseparable rooted planar maps with n+1 edges enumerated by 2(3n)!/((2n+1)!(n+1)!).     

Baxter permutations and plane bipolar orientations

We present a simple bijection between Baxter permutations of size n and plane bipolar orientations with n edges. This bijection translates several classical parameters of permutations into natural parameters of orientations, and has remarkable symmetry properties. By specialising it to Baxter permutations avoiding the pattern 3142, we obtain a bijection with non-separable planar maps, which had been described only in an implicit recursive manner so far (up to simple symmetries). A further specialization yields a bijection between permutations avoiding 3142 and 2413 and series-parallel maps.     

New interpretations for noncrossing partitions of classical types

We interpret noncrossing partitions of type B and type D in terms of noncrossing partitions of type A. As an application, we get type-preserving bijections between noncrossing and nonnesting partitions of type B, type C and type D which are different from those in the recent work of Fink and Giraldo. We also define Catalan tableaux of type B and type D, and find bijections between them and noncrossing partitions of type B and type D respectively.     

The admissible interval for the invariant factors of a product of matrices

It is well known that Littlewood-Richardson sequences give a combinatorial characterization for the invariant factors of a product of two matrices over a principal ideal domain. Given partitions a and c, let LR(a,c) be the set of partitions b for which at least one Littlewood - Richardson sequence of type (a,b,c) exists. I. Zaballa has shown in [20] that LR(a, c) has a minimal element w and a maximal element n, with respect to the order bf majorization, depending only on a and c;. In generalLR(a, c) is not the whole interval [w, n]. Here a combinatorial algorithm is provided for constructing all the elements of LR(a, c). This algorithm consists in starting with the minimal Littlewood-Richardson sequence of shape c/a and successively modifying it until the maximal Littlewood - Richardson sequence of shape c/a is achieved. Also explicit bijections between Littlewood - Richardson sequences of conjugate shape and weight and between Littlewood - Richardson sequences of dual shape and equal weight are presented. The bijections are denned by means of permutations of Littlewood - Richardson sequences.     

Four positive formulae for type A quiver polynomials

We give four positive formulae for the (equioriented type A) quiver polynomials of Buch and Fulton [BF99 ]. All four formulae are combinatorial, in the sense that they are expressed in terms of combinatorial objects of certain types: Zelevinsky permutations, lacing diagrams, Young tableaux, and pipe dreams (also known as rc-graphs). Three of our formulae are multiplicity-free and geometric, meaning that their summands have coefficient 1 and correspond bijectively to components of a torus-invariant scheme. The remaining (presently non-geometric) formula is a variant of the conjecture of Buch and Fulton in terms of factor sequences of Young tableaux [BF99 ]; our proof of it proceeds by way of a new characterization of the tableaux counted by quiver constants. All four formulae come naturally in “doubled” versions, two for double quiver polynomials, and the other two for their stable limits, the double quiver functions, where setting half the variables equal to the other half specializes to the ordinary case. Our method begins by identifying quiver polynomials as multidegrees [BB82 , Jos84 , BB85 , Ros89 ] via equivariant Chow groups [EG98 ]. Then we make use of Zelevinsky’s map from quiver loci to open subvarieties of Schubert varieties in partial flag manifolds [Zel85 ]. Interpreted in equivariant cohomology, this lets us write double quiver polynomials as ratios of double Schubert polynomials [LS82 ] associated to Zelevinsky permutations; this is our first formula. In the process, we provide a simple argument that Zelevinsky maps are scheme-theoretic isomorphisms (originally proved in [LM98 ]). Writing double Schubert polynomials in terms of pipe dreams [FK96 ] then provides another geometric formula for double quiver polynomials, via [KM05 ]. The combinatorics of pipe dreams for Zelevinsky permutations implies an expression for limits of double quiver polynomials in terms of products of Stanley symmetric functions [Sta84 ]. A degeneration of quiver loci (orbit closures of GL on quiver representations) to unions of products of matrix Schubert varieties [Ful92 , KM05 ] identifies the summands in our Stanley function formula combinatorially, as lacing diagrams that we construct based on the strands of Abeasis and Del Fra in the representation theory of quivers [AD80 ]. Finally, we apply the combinatorial theory of key polynomials to pass from our lacing diagram formula to a double Schur function formula in terms of peelable tableaux [RS95a , RS98 ], and from there to our formula of Buch–Fulton type.     

Arc permutations

Arc permutations and unimodal permutations were introduced in the study of triangulations and characters. This paper studies combinatorial properties and structures on these permutations. First, both sets are characterized by pattern avoidance. It is also shown that arc permutations carry a natural affine Weyl group action, and that the number of geodesics between a distinguished pair of antipodes in the associated Schreier graph, and the number of maximal chains in the weak order on unimodal permutations, are both equal to twice the number of standard Young tableaux of shifted staircase shape. Finally, a bijection from non-unimodal arc permutations to Young tableaux of certain shapes, which preserves the descent set, is described and applied to deduce a conjectured character formula of Regev.