Permutation tableaux and permutation patterns (Q868877): Difference between revisions

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.