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.
Recommendations
Cites work
- scientific article; zbMATH DE number 3821741 (Why is no real title available?)
- 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
- 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
- Shelling totally nonnegative flag varieties
- Specializations of Generalized Laguerre Polynomials
- q-Bernoulli and Eulerian Numbers
Cited in
(73)- Combinatorics of faithfully balanced modules
- Bijections for permutation tableaux
- Crossings and alignments of permutations
- Restricted Dumont permutations, Dyck paths, and noncrossing partitions
- Dyck tableaux
- Permutation patterns and cell decompositions
- Permutations sortable by \(n - 4\) passes through a stack
- Asymptotic normality of the number of corners in tableaux associated with the partially asymmetric simple exclusion process
- Bijections between pattern-avoiding fillings of Young diagrams
- Permutation statistics and weak Bruhat order in permutation tableaux of type \(B\)
- The structure of alternative tableaux
- The Matrix Ansatz, orthogonal polynomials, and permutations
- Combinatorics of diagrams of permutations
- Permutation tableaux and the dashed permutation pattern 32-1
- Permutations, moments, measures
- Combinatorics of diagrams of permutations
- Combinatorics of the 2-species exclusion processes, marked Laguerre histories, and partially signed permutations
- Permutation q-enumeration with the Schur row adder
- Formulae for Askey-Wilson moments and enumeration of staircase tableaux
- Expected values of statistics on permutation tableaux
- Linked partitions and permutation tableaux
- Bijections for permutation tableaux
- Tree-like tableaux
- Non-ambiguous trees: new results and generalisation
- Enumerations of permutations by circular descent sets
- Combinatorial properties of permutation tableaux
- Tableau sequences, open diagrams, and Baxter families
- Actions on permutations and unimodality of descent polynomials
- 2-species exclusion processes and combinatorial algebras
- An equivalence of multistatistics on permutations
- Rook placements in Young diagrams and permutation enumeration
- Profiles of permutations
- A \(q\)-enumeration of alternating permutations
- The \(\nu \)-Tamari lattice via \(\nu \)-trees, \( \nu \)-bracket vectors, and subword complexes
- The \(q\)-tangent and \(q\)-secant numbers via continued fractions
- An automaton-theoretic approach to the representation theory of quantum algebras
- Corners in tree-like tableaux
- On some properties of permutation tableaux
- Non-ambiguous trees: new results and generalization
- Combinatorics of non-ambiguous trees
- Block decomposition and statistics arising from permutation tableaux
- On the sign-imbalance of permutation tableaux
- A combinatorial proof of a symmetry of \((t,q)\)-Eulerian numbers of type \(B\) and type \(D\)
- Permutation tableaux, restricted set partitions and labeled Dyck paths.
- Statistics on staircase tableaux, Eulerian and Mahonian statistics
- New interpretations for noncrossing partitions of classical types
- The pinnacle set of a permutation
- Combinatorial Hopf algebras, noncommutative Hall-Littlewood functions, and permutation tableaux
- KP solitons and total positivity for the Grassmannian
- Combinatorics on permutation tableaux of type A and type B
- Staircase tableaux, the asymmetric exclusion process, and Askey-Wilson polynomials
- Simple permutations and pattern restricted permutations
- A bijection from staircase tableaux to inversion tables, giving some Eulerian and Mahonian statistics
- Pattern avoidance and Young tableaux
- scientific article; zbMATH DE number 6928814 (Why is no real title available?)
- The parity of the number of permutation tableaux in a fixed shape
- Expected patterns in permutation classes
- Shelling totally nonnegative flag varieties
- Permutations with extremal number of fixed points
- Tower tableaux
- Tableaux combinatorics for the asymmetric exclusion process
- EW-tableaux, Le-tableaux, tree-like tableaux and the abelian sandpile model
- Patterns in Shi tableaux and Dyck paths
- Distribution of the number of corners in tree-like and permutation tableaux
- Lonesum and \(\Gamma\)-free \(0-1\) fillings of Ferrers shapes
- An Ising model having permutation spin motivated by a permutation complexity measure
- On positroids induced by rational Dyck paths
- Chess tableaux
- Weighted random staircase tableaux
- Applying the cluster method to count occurrences of generalized permutation patterns
- scientific article; zbMATH DE number 59348 (Why is no real title available?)
- scientific article; zbMATH DE number 490786 (Why is no real title available?)
- The history of the Gothenburg--Reykjavík--Strathclyde combinatorics group
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)
