Combinatorics On Permutation Tableaux

The main results of this thesis are statistics on permutation tableaux. We set upcorrespondences of permutation tableaux, permutations and linked partitions and weintroduce the inversion number on permutation tableaux. We generalize the idea offorbidden permutation pattern to permutation tableaux avoiding certain pattern. Thuswe obtain the correspondence between some subclass of permutation tableaux andSchr(o|¨)der paths, permutation tableaux and Dyck paths, permutation tableaux and setpartitions. We proved that some statistics on permutation tableaux are enumerated bysecond kind of Stirling numbers and Eulerian numbers.The first chapter is devoted to the background knowledge of the permutationtableaux. We show the derivation of permutation tableaux from the study of total-ly nonnegative Grassmannian cells, the connection between permutation tableaux andpartially asymmetric exclusion process (or PASEP for short).In Chapter2, we first present a new recurrence enumeration result of permutationtableaux. Through this recurrence relation, we could get some information about thestatistics on permutation tableau. Then we summarize various types diagrams of per-mutation tableaux, namely all one’s diagram, restricted zero-one diagram, alternativediagram and staircase diagram and show the different roles of each diagram that playsin the study of permutation tableaux.In Chapter3, we set up a bijection between permutation tableaux of length n andlinked partitions of [n]={1,2,..., n} and a bijection between linked partitions of [n]and permutations on [n]. By Combining these two bijections, we get a new bijectionbetween permutation tableaux of length n and permutations on [n]. This leads us tostudy several combinatorial properties of permutation tableaux.In Chapter4, we introduce inversion number on permutation tableau. By usingthe bijection of Corteel and Nadeau, we show that the inversion number of permutationtableaux has the same distribution as the dashed pattern32-1in permutations. Thisgives a solution of the problem proposed by Corteel and Nadeau concerning permuta- tion tableaux of length n and the number of occurrences of the dashed pattern32–1inpermutations on [n]. As a special case, permutation tableaux without inversions coin-cide with L-Bell tableaux introduced by Corteel and Nadeau.In Chapter5, we study some subclasses of permutation tableaux. Each of theseclasses is counted by Bell number and connected with permutations avoiding some pat-terns of length3. Furthermore, by restricting the bijection between linked partitionsand permutation tableaux in Chapter3to the noncrossing linked partitions, we are ledto a subclass of permutation tableaux avoiding certain pattern which we called crossingpattern. We show the recurrence relation of permutation tableaux avoiding crossingpattern. Moreover, we set up a bijection between permutation tableaux avoiding cross-ing pattern of length n+1and Schr(o|¨)der paths of length2n by using the decompositionof permutation tableaux. Likewise, we introduce the nesting pattern of permutationtableaux. We construct a bijection between permutation tableaux avoiding nesting pat-tern and permutation tableaux avoiding crossing pattern.