置换杨图的组合性质及其应用

置换杨图本质上是A.Postnikov在研究完全非负Grassnann元胞及其元胞分解时所定义的]-图(]-diagram)的一个子集.它的发现引起许多组合学者的关注和研究,其中L.K.Williams和E.Steingrí-sson是最先关注这类组合结构的,他们在研究它的组合性质时发现了它与置换群之间存在着一一对应关系Ψ.从置换杨图本身的结构出发按照行递归的方式给出了Ψ是一一映射的一个新方法,利用这种方法可简单地将任意的一个排列π∈Sn分解成若干圈的乘积形式,并且每个圈中的元素都是按递减顺序排列.

Combinatorial Properties of Permutation Tableaux with Its Applications

Essentially,the permutation tableaux is a subset of the]-diagram defined by A.Postnikov in his work studying the combinatorics of the totally non-negative part of the Grassmannian and its cell decomposition.On the basis of investigating combinatorial properties of permutation tableau,L.K.Williams found that there is a natural bijectionΨ between the permutation tableaux and the permutations.In terms of its combinatorial structure,we give a new proof thatΨis a bijection in this thesis with a new way which leads to an unexpected result:any permutationπ∈Sncan be decomposed into the multiplications of cycles each of which is ordered decreasingly.