Fine Paths And Restricted Derangements

With the development of computer science and technology,the importance of combinatorial mathematics become more clearly.Many theory subjects and applied subjects proposed a large number of theoretical and practical problems,which promoted combinatorial mathematics produce many new theory,for example,combinatorial optimization,combinatorial algorithm and so on.However,combinatorial counting theory is the most basis aspect of combinatorial mathematics,many theory research and practical model based on it.Combinatorial mathematics includes many importance combinatorial numbers,such as the Fibonacci numbers,the Catalan numbers,the Motzkin numbers and the Schr(o｜¨)der numbers.The research on these numbers are mature and most people do research on the Catalan numbers.There are close links between the Catalan numbers and lattice paths,labeled trees,tableaux and so on.People do research on this aspect mainly base on the relation between the Catalan numbers and lattice paths.The development of computer science and technology enrich knowledge of algorithms theory,and sort is an important aspect of algorithms.There are close links between sort and combinatorial objects,for examnple,people first used restricted permutation study sort.With the development of research,people discovered the count of 321-avoiding permutation is the Catalan numbers.This paper base on the Catalan numbers and use two methods to establish the bijections between Fine paths and restricted derangement.1.In chapter 2,we base on the relation between the Fine numbers and the Catalan numbers, so we summary the definition and properties of the Fine numbers.Furthermore,we prove some identities and combinatorial explanation of the Fine numbers.We use generating function to prove the identities,and establish several bijections for the Fine numbers.2.In chapter 3,we summary the definition and properties of restricted permutations and derangements,at the same time,we prove two indentities of derangement.Furthermore,we introduce two algorithms of canonical reduced decomposition and labelling schemes,and we use these two algorithms establish the bijections between Fine paths and 321-avoiding derangements respectively,and we obtain some properties of 321-avoiding derangements.