Permutation tableaux and permutation patterns
From MaRDI portal
Abstract: 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 Le-diagrams of Alex Postnikov. 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 and the more recent q-analog of the Eulerian numbers of the second author. We conclude our paper with a list of open problems, some of which have now been solved by Burstein, Corteel, Eriksen, Reifegerste, and Viennot.
From the authors' abstract: 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 Postnikov's lE-diagrams. 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. The second bijection carries tableaux 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 generalize both Carlitz' \(q\)-analog of the Eulerian numbers and the more recent \(q\)-analog of the Eulerian numbers found by the second author [Adv. Math. 190, No. 2, 319--342 (2005; Zbl 1064.05150)]. We conclude the paper with a list of open problems, as well as remarks on progress on these problems.
Recommendations
Cites work
- Crossings and alignments of permutations
- Denert's Permutation Statistic Is Indeed Euler‐Mahonian
- Enumeration of totally positive Grassmann cells
- Generalized pattern avoidance
- Generalized permutation patterns and a classification of the Mahonian statistics
- scientific article; zbMATH DE number 3821741 (Why is no real title available?)
- New Euler-Mahonian statistics on permutations and words
- Permutations depending on the exceedance type and the number of inversions and combinatorial interpretation of a continued fraction of Heine
- Permutations selon leurs pics, creux, doubles montees et double descentes, nombres d'Euler et nombres de Genocchi
- q-Bernoulli and Eulerian Numbers
- Shelling totally nonnegative flag varieties
- Specializations of Generalized Laguerre Polynomials
Cited in
(73)- Permutations with extremal number of fixed points
- An automaton-theoretic approach to the representation theory of quantum algebras
- Permutation statistics and weak Bruhat order in permutation tableaux of type B
- EW-tableaux, Le-tableaux, tree-like tableaux and the abelian sandpile model
- The parity of the number of permutation tableaux in a fixed shape
- 2-species exclusion processes and combinatorial algebras
- A combinatorial proof of a symmetry of \((t,q)\)-Eulerian numbers of type \(B\) and type \(D\)
- An equivalence of multistatistics on permutations
- The pinnacle set of a permutation
- Tower tableaux
- Bijections between pattern-avoiding fillings of Young diagrams
- Non-ambiguous trees: new results and generalisation
- Combinatorics of faithfully balanced modules
- Patterns in Shi tableaux and Dyck paths
- Lonesum and \(\Gamma\)-free \(0-1\) fillings of Ferrers shapes
- Block decomposition and statistics arising from permutation tableaux
- Enumerations of permutations by circular descent sets
- The \(\nu \)-Tamari lattice via \(\nu \)-trees, \( \nu \)-bracket vectors, and subword complexes
- Permutation patterns and cell decompositions
- Profiles of permutations
- On some properties of permutation tableaux
- Combinatorics on permutation tableaux of type A and type B
- New interpretations for noncrossing partitions of classical types
- Tableaux combinatorics for the asymmetric exclusion process
- Actions on permutations and unimodality of descent polynomials
- Bijections for permutation tableaux
- Simple permutations and pattern restricted permutations
- Chess tableaux
- On positroids induced by rational Dyck paths
- Crossings and alignments of permutations
- Permutation tableaux, restricted set partitions and labeled Dyck paths.
- Formulae for Askey-Wilson moments and enumeration of staircase tableaux
- Permutation q-enumeration with the Schur row adder
- Weighted random staircase tableaux
- Statistics on staircase tableaux, Eulerian and Mahonian statistics
- Applying the cluster method to count occurrences of generalized permutation patterns
- Staircase tableaux, the asymmetric exclusion process, and Askey-Wilson polynomials
- Combinatorial properties of permutation tableaux
- Asymptotic normality of the number of corners in tableaux associated with the partially asymmetric simple exclusion process
- Expected values of statistics on permutation tableaux
- Dyck tableaux
- Linked partitions and permutation tableaux
- Tree-like tableaux
- scientific article; zbMATH DE number 59348 (Why is no real title available?)
- Combinatorics of non-ambiguous trees
- scientific article; zbMATH DE number 490786 (Why is no real title available?)
- Expected patterns in permutation classes
- Bijections for permutation tableaux
- scientific article; zbMATH DE number 6928814 (Why is no real title available?)
- Combinatorics of diagrams of permutations
- KP solitons and total positivity for the Grassmannian
- Distribution of the number of corners in tree-like and permutation tableaux
- Permutations, moments, measures
- A bijection from staircase tableaux to inversion tables, giving some Eulerian and Mahonian statistics
- Pattern avoidance and Young tableaux
- Non-ambiguous trees: new results and generalization
- On the sign-imbalance of permutation tableaux
- The structure of alternative tableaux
- The Matrix Ansatz, orthogonal polynomials, and permutations
- Permutation tableaux and the dashed permutation pattern 32-1
- Shelling totally nonnegative flag varieties
- Rook placements in Young diagrams and permutation enumeration
- An Ising model having permutation spin motivated by a permutation complexity measure
- The history of the Gothenburg--Reykjavík--Strathclyde combinatorics group
- Permutations sortable by \(n - 4\) passes through a stack
- The q-tangent and q-secant numbers via continued fractions
- A q-enumeration of alternating permutations
- Corners in tree-like tableaux
- Tableau sequences, open diagrams, and Baxter families
- Combinatorics of the 2-species exclusion processes, marked Laguerre histories, and partially signed permutations
- Restricted Dumont permutations, Dyck paths, and noncrossing partitions
- Combinatorics of diagrams of permutations
- Combinatorial Hopf algebras, noncommutative Hall-Littlewood functions, and permutation tableaux
This page was built for publication: Permutation tableaux and permutation patterns
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q868877)
