Research On The Combinatorial Properties Of Permutation Tableaux,Link Partitions And Lattice Paths

Both permutation tableau and link partition are fire-new combinatorial structures that were introduced in 2007.Recent years,more and more researchers in combinatorics pay close attention to these two structures,and there were lots of papers about them have been published.Besides,as one of the most classical combinatorial structures,lattice path has been studying all the time.In this paper,we mainly study the enumerative properties of permutation tableau,and the connection between(2,2)-Motzkin path and underdiagonal lattice path.We utilize the bijection between permutation tableau and link partition,transferring the problem of enumerating permutation tableaux to link partitions.By constructing an involution on link partitions,we confirmed that the number of link partitions in a fixed shape is odd,and so is the number of permutation tableau in a fixed shape.Because the number of the set of(2,2)-Motzkin paths of length n is equal to the number of the set of underdiagonal lattice paths of length n,we constructed a bijection between them.In chapter 1,we introduce the background of the research subject,including some research outputs of permutation tableau,link partition and lattice path,also the structure of the whole paper.In chapter 2,we present some necessary theoretical knowledge.In chapter 3,we mainly discuss the parity of the number of permutation tableaux in a fixed shape.To be specific,we first introduce the structures of rainbow linked partitions and non-rainbow linked partitions,and then we establish an involution on the set of linked partitions of [n] according to these two special structures,and obtained the enumerative property of link partitions.This involution is not only the key tool to solve our problem,but also one of the innovations of this paper.In chapter 4,we introduce the map from underdiagonal lattice paths to(2,2)-Motzkin paths and the map from(2,2)-Motzkin paths to underdiagonal lattice paths respectively,to explain our bijection,which is new and can make supplement for the research on these two lattice paths.