组合数学中常见的计数方法论文答辩

组合数学中常见的计数方法导师:段洪玲辩论人:杨树营专业:信息与计算科学研究背景和意义背景 现代数学可以分为两大类：一类是研究连续对象的，如分析、方程等，另一类就是研究离散对象的组合数学。组合数学不仅在根底数学研究中具有极其重要的地位，在其它的学科中也有重要的应用，如计算机科学、编码和密码学、物理、化学、生物等学科中均有重要应用。 4研究背景和意义意义 组合数学不仅在软件技术中有重要的应用价值，在企业管理，交通规划，战争指挥，金融分析等领域都有重要的应用。在美国有一家用组合数学命名的公司，他们用组合数学的方法来提高企业管理的效益，这家公司办得非常成功。此外，试验设计也是具有很大应用价值的学科，它的数学原理就是组合设计。用组合设计的方法解决工业界中的试验设计问题，在美国已有专门的公司开发这方面的软件。论文结构和主要内容第一局部:开篇介绍了组合数学的研究背景和意义,说明了组合数学在自然科学的许多领具有十分重要的应用价值。 第二局部:介绍了Catalan数的起源、定义、性质及其在生活中的应用。第三局部:介绍了Stirling数的起源、定义、性质,并结合概率论有关知识,重点介绍了Stirling数在定理和恒等式证明方面的应用。论文结构和主要内容第四局部:简单介绍了Fine数和Pólya计数。在Fine数一局部,引进格路的概念,以Dyck格路的形式给出了Fine数和Catalan数的定义,最后总结了Fine数和Catalan数的假设干性质并列举了Fine数的一些组合解释。在Pólya计数一局部,通过群的相关知识引出Pólya定理,最后举例说明Pólya定理在组合计算中的简单应用。第五局部:总结。Catalan数定义及求法 1.凸n+1边形的三角剖分数:将凸n+1边形用不相交的对角线对进行三角剖分,所有不同的三角剖分方案数即为Catalan数(所谓凸n边形,即n边形内任意两点的连线线段都在该n边形内)

。

2.路径模型及求法:从平面上(0,0)点出发到(n,n)点的除端点外不接触直线y=x,且在直线y=x下方的路径数即为Catalan数。

Catalan数应用 1.售票问题:一个售票亭前排着2n个人的队伍等候购票,假定他们都购置价值1元的同一种票,其中有n个人持1元币,n个人持2元币,而售票员开始售票时没有零钱,问有多少种排队方式,可使得售票员能依次顺利售票,而不出现找不出钱的局面? 2.唱票问题:2(n-1)张选票投给甲、乙两个候选人,每人均各得n-1张,要求唱票时任一时刻甲所得票数乙所得票数,问这样的唱票方式有多少种?Stirling数定义 1.第二类Stirling数:,

我们把系数 叫做第二类Stirling数。 2.第一类Stirling数:,我们把系数叫做第一类Stirling数。重要定理 1.第二类Stirling数 定理1.1:如果 ,那么 Stirling数定理1.2:第二类Stirling数,是将p个元素的集合划分成k个不可区分的非空盒的划分的个数。 2.第一类Stirling数 定理2.1:如果,那么 定理2.2:第一类Stirling数是将p个物体排成k个非空的循环排列的方法数。Stirling数应用 Stirling数与概率恒等式证明 定理1:如果随机变量V服从二项分布,那么 它的任意m阶原点矩为 这里是第二类Stirling数,为降阶乘。 定理2:假设 序列 并且 与独立,那么时,第二类Stirling数满 足 Fine数、

Catalan数与Dyck格路定义

Dyck格路:一条2n长的Dyck格路是指在中,从 原点(0,0)出发到(2n,0),由(1,1)方向的上升步和 (1,-1)方向的下降步组成的,始终在x轴上方的一 条路径.从(0,0)出发到(2n,0)的Dyck格路记做n- Dyck格路。 Catalan数:我们把长度为2n的 Dyck格路的集合记做。是由Catalan数来计数的,Catalan数的初值是1,1,2,5,14,24,132,429,1430,4862,…Fine数、

Catalan数与Dyck格路

Fine数:在中,一条2n长的Fine格路是一条不包含hill的2n长的Dyck格路。一个hill是由(1,1)方向的上升步和(1,-1)方向的 下降步形成的高度为1的峰.从(0,0)出发到(2n,0)的Fine格路记做n-Fine格路。 Catalan数与Fine数之间的关系 命题1: 命题2: 致谢