Permutation Tableaux and Permutation Patterns

Details Permutation Tableaux and Permutation Patterns Permutation Tableaux and Permutation Patterns

2005-07-07

arxiv.org/abs/math/0507149v2

Mathematics

Combinatorics

Clarification of proofs (thanks to referees); report on progress on our open problems by Burstein, Corteel, Eriksen, Reifegers

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Permutation Tableaux and Permutation Patterns does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Permutation Tableaux and Permutation Patterns, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Permutation Tableaux and Permutation Patterns will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-480739