论文部分内容阅读
随着计算机科学技术的发展,组合数学的重要性日渐凸显,许多理论学科和应用学科向组合数学提出了大量的具有理论和实际意义的课题,促使组合数学产生了许多新理论,如组合优化,组合算法等.而组合计数理论是组合数学中一个最基本的研究方向,许多理论研究和实际模型的建立都是以此为基础,组合数学中有很多重要的组合数,例如Fibonacci数,Catalan数,Motzkin数和Schr(o)der数.人们对这些组合数的研究已经很成熟,其中研究最多的是Catalan数.Catalan数和一些重要的组合对象,如格路,有序树,Young表等密切相关,人们在研究Catalan数的时候主要基于Catalan数和格路的关系.计算机科学技术的发展丰富了算法的理论知识,而排序是算法的重要内容.排序和重要的组合对象有着紧密的联系,比如人们最初用有禁排列研究排序的一些性质。随着有禁排列研究的深入,人们发现3长的有禁排列的计数是Catalan数,后来人们用几种不同的方法研究Catalan数和有禁排列的关系。本文建立在Catalan数的基础上,研究一种新的组合数即Fine数.Fine数有很多重要的性质,本文的主要成果有:
1.在第二章,根据Fine数和Catalan数之间的关系,对Fine数的定义和性质给予归纳总结,同时研究了Fine数的一些重要的恒等式和Fine数的一些组合解释。并且对这些恒等式用发生函数的方法给予证明,对这些组合解释通过建立一一对应给予证明。
2.在第三章,对有禁排列和错排的定义及性质给予归纳总结,同时证明了错排的两个重要的恒等式.此外,本章给出两个算法,即标准约合分解法和标号法,并分别用这两个算法建立Fine格路和避免321模式的错排之间的双射,同时得到了避免321模式的错排的一些统计量的性质.