组合数学中常见的计数方法-论文答辩ppt课件

1、1研究背景和意义研究背景和意义u背景背景现代数学可以分为两大类：一类是研究现代数学可以分为两大类：一类是研究连续对象的，如分析、方程等，另一类连续对象的，如分析、方程等，另一类就是研究离散对象的组合数学。组合数就是研究离散对象的组合数学。组合数学不仅在学不仅在基础数学基础数学研究中具有极其重要研究中具有极其重要的地位，在其它的学科中也有重要的应的地位，在其它的学科中也有重要的应用，如计算机科学、编码和用，如计算机科学、编码和密码学密码学、物物理理、化学化学、生物等学科中均有重要应用。、生物等学科中均有重要应用。 4研究背景和意义研究背景和意义u意义意义组合数学不仅在软件技术中有重要组合数学不仅

2、在软件技术中有重要的应用价值，在企业管理，交通规划，的应用价值，在企业管理，交通规划，战争指挥，金融分析等领域都有重要的战争指挥，金融分析等领域都有重要的应用。在美国有一家用组合数学命名的应用。在美国有一家用组合数学命名的公司，他们用组合数学的方法来提高企公司，他们用组合数学的方法来提高企业管理的效益，这家公司办得非常成功。业管理的效益，这家公司办得非常成功。此外，试验设计也是具有很大应用价值此外，试验设计也是具有很大应用价值的学科，它的的学科，它的数学原理数学原理就是组合设计。就是组合设计。用组合设计的方法解决工业界中的试验用组合设计的方法解决工业界中的试验设计问题，在美国已有专门的公司开发

3、设计问题，在美国已有专门的公司开发这方面的软件。这方面的软件。论文结构和主要内容论文结构和主要内容u第一部分第一部分:开篇介绍了组合数学的研究背景和意开篇介绍了组合数学的研究背景和意义义, ,说明了组合数学在自然科学的许多领具有十说明了组合数学在自然科学的许多领具有十分重要的应用价值。分重要的应用价值。 u第二部分第二部分: :介绍了介绍了Catalan数的起源数的起源、定义、性定义、性质及其在生活中的质及其在生活中的应用。应用。 u第三部分第三部分: :介绍了介绍了Stirling数的起源数的起源、定义、性定义、性质质, ,并结合概率论有关知识并结合概率论有关知识, ,重点介绍了重点介绍了S

4、tirling数数在定理和恒等式证明方面的应用。在定理和恒等式证明方面的应用。 论文结构和主要内容论文结构和主要内容u第四部分第四部分: :简单介绍了简单介绍了Fine数和数和Plya计数。在计数。在Fine数一部分数一部分, ,引进格路的概念引进格路的概念, ,以以Dyck格路的形式格路的形式给出了给出了Fine数和数和Catalan数的定义数的定义, ,最后总结了最后总结了Fine数数和和Catalan数的若干性质并列举了数的若干性质并列举了Fine数的一些组合数的一些组合解释。在解释。在Plya计数一部分计数一部分, ,通过群的相关知识引出通过群的相关知识引出Plya定理定理, ,最后举

5、例说明最后举例说明Plya定理在组合计算中的定理在组合计算中的简单应用。简单应用。u第五部分第五部分: :总结。总结。Catalan数数u定义及求法定义及求法1.1.凸凸n+1+1边形的三角剖分数边形的三角剖分数: :将凸将凸n+1边形用不边形用不相交的对角线对进行三角剖分相交的对角线对进行三角剖分, 所有不同的三角剖分所有不同的三角剖分方案数即为方案数即为Catalan数数(所谓凸所谓凸n边形边形,即即n边形内任意两边形内任意两点的连线线段都在该点的连线线段都在该n边形内边形内) 。 2.2.路径模型及求法路径模型及求法: :从平面上从平面上(0,0)(0,0)点出发到点出发到( (n,n)

6、 )点的除端点外不接触直线点的除端点外不接触直线y=x, ,且在直线且在直线y=x下方下方的路径数即为的路径数即为CatalanCatalan数。数。Catalan数数u应用应用1.1.售票问题售票问题: :一个售票亭前排着一个售票亭前排着2n个人的队伍个人的队伍等候购票等候购票,假定他们都购买价值假定他们都购买价值1元的同一种票元的同一种票,其中有其中有n个人持个人持1元币元币,n个人持个人持2元币元币,而售票员开始售票时没而售票员开始售票时没有零钱有零钱,问有多少种排队方式问有多少种排队方式,可使得售票员能依次顺可使得售票员能依次顺利售票利售票,而不出现找不出钱的局面而不出现找不出钱的局面

7、?2.2.唱票问题唱票问题: :2(n-1)张选票投给甲、乙两个候选张选票投给甲、乙两个候选人人,每人均各得每人均各得n-1张张,要求唱票时任一时刻甲所得票数要求唱票时任一时刻甲所得票数乙所得票数乙所得票数,问这样的唱票方式有多少种问这样的唱票方式有多少种?Stirling数数u定义定义1.第二类第二类Stirling数数: , 我们把系数我们把系数 叫做第二类叫做第二类Stirling数数。 2. 2.第一类第一类Stirling数数: ,: , 我们把系数我们把系数 叫做第一类叫做第一类Stirling数。数。u重要定理重要定理1.1.第二类第二类Stirling数数定理定理1.1:1.1

8、:如果如果 , ,则则 pkkpnp,kSn0kpS, pkkp-kpnp,ks-n01p,ks1-1pk 1-, 1-, 1-,kpSkpkSkpSStirling数数 定理定理1.2:第二类第二类Stirling数数 ,是将是将p个元素的个元素的集合划分成集合划分成k个不可辨别的非空盒的划分的个数。个不可辨别的非空盒的划分的个数。 2.第一类第一类Stirling数数 定理定理2.1:如果如果 ,则则 定理定理2.2:第一类第一类Stirling数数 是将是将p个物体排个物体排成成k个非空的循环排列的方法数。个非空的循环排列的方法数。kpS,1-1pk 1-, 1-, 1-1-,kpskp

9、spkpskps,Stirling数数u应用应用Stirling数与概率恒等式证明数与概率恒等式证明定理定理1:如果随机变量如果随机变量V服从二项分布服从二项分布 ,则则它的任意它的任意m阶原点矩为阶原点矩为 这里这里 是第二类是第二类Stirling数数, 为降阶乘。为降阶乘。 定理定理2:假设假设 序列序列 并且并且 与与 独立独立, 则则 时时,第二类第二类Stirling数数 满满 足足pnB, 0,0mpnkmSEVmkkkmkmS, knvr.),1 (U0,12121,i.i.d,i.i.d,uuvr.iuj1n,k n,kSn-kkuuEknn,kS)()(1Fine数数、 C

10、atalan数与数与Dyck格路格路u定义定义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

11、,132,429,1430,4862, 2ZnCnCFine数数、 Catalan数与数与Dyck格路格路Fine数数:在在 中中,一条一条2n长的长的Fine格路是一条不包含格路是一条不包含hill的的2n长的长的Dyck格路。格路。一个一个hill是由是由(1,1)方向的方向的上升步和上升步和(1,-1)方向的方向的下降步形成的高度为下降步形成的高度为1的峰的峰.从从(0,0)出发到出发到(2n,0)的的Fine格路记做格路记做n-Fine格路。格路。 uCatalanCatalan数与数与FineFine数之间的关系数之间的关系命题命题1:1: 命题命题2:2:2ZxxxxFxxxF4-1-34-1-11)(1)-)(C(1)(12n-nnFFC致谢致谢u大学本科的学习生活即将结束。在此，我大学本科的学习生活即将结束。在此，我要感谢所有曾经教导过我的老师和关心过我要感谢所有曾经教导过我