Combinatorial Properties Of Permutation Tableaux With Its Applications

Young diagram is one of the most important and extensively influential combinatorialobjects in the field of combinatorics. In this thesis, based on the structure of Youngdiagram, we introduce and study a class of fairly new combinatorial objects which iscalled permutation tableau. Essentially, the permutation tableaux is a subset of the ]-diagram defined by A. Postnikov in his work studying the combinatorics of the totallynon-negative part of the Grassmannian and its cell decomposition. L.K. Williams foundthat there is a natural bijection between the permutation tableaux and the permutations.Then she carried out further studies on the permutation tableaux which is no-longerdependent on ]-diagram.In this thesis, we explore the combinatorial structures and properties of the permu-tation tableaux, and study the applications of the permutation tableaux in the field ofenumerative combinatorics, by establishing bijections between the permutation tableauxand the permutations. As will be seen, the permutation tableaux has intuitionistic andvisual structures.The contributions of this thesis are as follows: First, we simplify the bijectionΨwhichwas established by L.K. Williams and E. Steingr′(?)msson. Second, we find a new method toshow thatΨis a bijection. This method leads to an unexpected result: any permutationπ∈Sn can be decomposed into the multiplications of cycles each of which is ordered de-creasingly. Finally, in studying related applications, we explore the connections betweenthe permutation tableaux corresponding to derangements and alternating permutation-s, and find a bijection from derangements on [n] to alternating permutations on [2n] byre?ecting them on the permutation tableaux. As a consequence of this bijection, we gavea new proof to the following conjecture proposed by R.P. Stanley: A_「n/2」(n) = D_「n/2」,A*_「(n+1)/2」(n) = D_「(n+1)/2」, where A_k(n) is the number of alternating permutations on set[n] with k fixed points, D_n is the number of derangement on set [n], and A*_k(n) is thenumber of anti-alternating permutations with k fixed points on [n].