Generalized Permutations And Young Tableaux

In 1968,D.Knuth introduced the concept of pattern avoidance of permutation in his first volume of”The Art of Computer Programming".By using RSK corre-spondence,he proved that for any ??S3,the number of permutations which avoid the pattern ? is the Catalan number.In 1985,R.Simion and F.W.Schmidt first systematically studied the pattern avoidance of permutation and gave a bijective proof of the result of Knuth.In the past 30 years,enumerative combinatorics has been rapidly and broadly developed in the area of pattern avoidance,along with hundreds of research papers and an annual conference”Permutation Patterns”since 2003.In this paper,we mainly study generalized permutations and Young tableaux.There are three parts of this paper.In the first part,we introduce and study the concept of pattern avoidance of generalized permutations.In the second part,we consider the refined RSK correspondence.In the last part,we pay our attention to the inversion statistics of 321-avoiding permutations.In chapter 3,by extending the concept of pattern avoidance on set and multi-set permutations,we introduce the pattern avoidance of generalized permutations and show that for any ??S3,the cardinality |S??(?)|=K(N,N)(?,?)is independent of the order of the entries of ? and ?,and is Schur concave for partitions ?and ?.Extending both Dyck path and Riordan path,we introduce the Catalan-Riordan paths and obtain that the(n,k)-th Catalan-Riordan number CR(n,k)is the number of semistandard Young tableaux of shape(n,n)and type(12k,2n-k).As applications,we interpret both Motzkin and Riordan numbers in two ways,via semistandard Young tableaux of two rows and generalized permutations avoiding??S3.In chapter 4,we study the refined RSK correspondence of Lewis.First-ly,we extend the bijection of Lewis and show that for any composition ?=(?1,?2,...,?n)? {k,k+1}n,there is a bijection between S?(1N)k and the set of standard Young tableaux of shape((k+1)n).Secondly,by extending Lewis's method to semistandard Young tableaux,we construct a bijection from general-ized permutations to rectangular semistandard Young tableaux.As a consequence,we reprove several Known results in the literature.Combining with the results obtained in Chapter three,we list some new identities on Catalan and Kostka numbers.In chapter 5,by introducing a new bijection from Sn(321)to Dyck paths of length 2n,we obtain a counting formulae for the number of 321-avoiding permu-tations on[n]with m inversions.In the final of this paper,we list three problems which are worthy of us to study later.