组合数学中常见的计数方法 - 下载本文

沈阳理工大学学士学位论文

18)有一个凸的(2n-1)角形A1,A2,?,A2n-2,将它们成对连接,并使得连接的线段在(2n-2)角形内不相交的方法数是Catalan数Cn-1?1?。

19)由n个1,n个0组成到2n位二进制数,要求从左向右扫描前2n-1,位数为1的累计数大于0的累计数,则满足这样条件的数的个数是Catalan数Cn-1?1?。

20)n个数相乘,不改变他们的位置,只用括号表示不同的相乘顺序,则构成不同的乘积的方法数是Catalan数Cn-1?1?。 2.5.2 Catalan数的应用

Catalan数列问题内涵丰富、应用广泛,对其进行真正意义上的科学研究并取得真正的进展需要很深的功力。下面我们针对Catalan数组合意义中的几类问题进行求解。

在日常生活中,我们常常会遇到以下的一些问题:

①售票问题:一个售票亭前排着2n个人的队伍等候购票,假定他们都购买价值1元的同一种票,其中有n个人持1元币,n个人持2元币,而售票员开始售票时没有零钱,问有多少种排队方式,可使得售票员能依次顺利售票,而不出现找不出钱的局面?

②城市线路问题:某城市的道路由若干条给定的相互垂直的街道组成,但由于各种地形、建筑的影响,有些地形并非完整.问从任意指定地点到另一地点共有多少种不同的最短路线?

③唱票问题:2(n-1)张选票投给甲、乙两个候选人,每人均各得n-1张,要求唱票时任一时刻甲所得票数?乙所得票数,问这样的唱票方式有多少种?

以上三个以及其他一些问题看似毫不相干,可是却奇迹般地建立在同一个数学基础之上,它就是我们要探究的主题:Catalan数列。

数列k1,k2,?,kn,?成为Catalan数列,若满足递推式:

?kn?k1kn-1?k2kn-2???kn-1k1 (n?2) (2.16) ?k?k?112?Catalan数列中的数称为Catalan数。Catalan数列的通项公式为

kn?1n-1(2n-2)!C2n-2? nn[(n-1)!]2并给出如下结论:

结论1 设x1,x2,?,xn是n个实数,则在乘积x1x2?xn中添加圆括号的不同方式数

an?k。

结论2 已知平面上的点O(0,0),A(n,n),则在对角线OA之上从O至A的非经路径(即

12

沈阳理工大学学士学位论文

行走方向向上或向右)的条数Cn?kn?1。 1、售票问题

现在分两步解决问题。

第一步,将持1元币的n个人彼此之间看作没有区别,均设为1,持2元币的n个人彼此之间也看作没有差异,均设为2。在此种假定条件下求符合条件的排队方式种数为xn。

建立如图2.3的坐标系,则从O到A在OA之上非降路径与问题中在上述假定条件下排队方式之间是一一对应关系。其方法是从O开始向上走一格意味着排“1”,向右走一格意味着排“2” 。如图2.51中粗线所对应的一种排队方式是12112211…122…2。因为从O至A在OA之上的每一条非降路径对应的一种排队方式,从前向后的每一个人前排“1”的均不少于票“2”的,故都是符合条件的排队方式。反之,符合条件的一种排队方式对应着从O到A在OA之上的一条非降路径。

故由结论2,xa?Cn?kn?1 。

第二步,对第一步的每种排队方式,对n个“1”进行全排列,对n个“2”也进行全排列,各有n!种排法.所以由乘法原理,问题的答案:

Dn?kn?1?(n!)2?

1 … (2n)! n?1 A 1 1 O 2 2 2 2… 2 图2.3 售票问题

2、城市线路问题

“城市线路问题”是一类问题的总称,其中有些情形复杂,有些情形简单。根据各城市路线布局的不同,这类问题会有各式各样的变化,并且需要各种不同的技巧。下面让我们以一种较为简单的情形作为例子来探讨一下。(如图2.4)

13

沈阳理工大学学士学位论文

A B 图2.4 城市路线问题

显然,在题中“最短路线”的限制下,最下面的一行、最左面的一列和顶部的两个小格是不能通过的,因此我们就可以把图2.4简化成图2.5的样子。

A B E1E2 E3E4E5 图2.5 简化的城市路线问题

E6 在图2.5中,我们注意到,E1-E2和E3-E4这两条虚线是不能通过的,因此E1、E2、

E3、E4这四个点就占有一定的特殊地位。

基于前面关于Catalan数阵的知识和简单的容斥原理,我们可以做出如下计算(用(X

→Y)表示从点X到点Y的不同走法总数) 。

A?B=A?E5E5?E6E6?B =A?E5E6?B

=[f(8,4)-A?E1f(7,3)-A?E3f(4,1)?A?E1E2?E3f(4,1)]E6

?B

13122?[f(8,4)-C1f(7,3)-C6f(4,1)?C1C4f(4,1)]C4

4313231012102?[(C12-C12)-C1(C10-C10)-C6(C5-C5)?C1C4(C5-C5)]C4

14

沈阳理工大学学士学位论文

?864

3、唱票问题

若将甲、乙二人所得的选票分别记为1与0,则问题即是将n-1个1与n-1个0排成一列,求对任意的1?k?n-1,使得前边k个数字中1的个数均不少于0的个数排列数Dn。可认定D1?1。对于n=2,3,4,将2(n-1)个数的符合上述要求的排列方式展示如下(从而得到D2?1,D3?2,D4?5):

10; 1100,1010; 111000,110100,110010,101100,101010。

按照要求,此种唱票序列的首元必是1。前面通过Catalan数的组合意义我们知道: 2n个点均匀分布在一个圆周上,用n条不相交的弦将这2n个点配对成n对,则不同的配对方式数是Cn,因此建立如下映射:

唱票问题?不相交连弦方式,即将唱票序列中(由前向后) 第一个出现的0与其前紧邻的1相配,然后划去此对0,1,再按如上做法继续,直到将唱票序列中配对点的序号两两连弦,即得到3)的一种不相交连弦。例如,n=6,唱票序列1011010010即对应于如下的不相交连弦(如图2.6),不难说明,这样定义的映射是一一映射,从而建立了关系Dn?Bn(Bn为不相交连弦的方式数)

10 0 987 10 0 610121134015图2.6 唱票问题

15

沈阳理工大学学士学位论文

3 Stirling数

3.1 Stirling产生的历史

Stirling数有两种,第一类和第二类Stirling数,它们自18世纪以来一直吸引许多数学家的兴趣,如欧拉、柯西、西尔沃斯特和凯莱等。后来哥本哈根(Copenhagen)大学的尼尔森(Niels Nielsen,1865-1931)提出了\Stirlingschen Zahlen erster Art\[第一类Stirling数]和\Stirlingschen Zahlen zweiter Art\第二类Stirling数],首次把这两类数冠以「Stirling数」之名。因为苏格兰数学家斯特林(1692-1770)首次发现这些数并说明了它们的重要性。Stirling数的概念是由J. Stirling于1730年在他的著作《Methodus Differentialis》中首次提出。此后,许多学者对这方面做了大量的研究。1933年,Ch. Jordan在他的一篇论文中对Stirling数做了彻底的阐述,并给出了一些Stirling数重要的性质。

3.2 第二类Stirling数

3.2.1定义

令hn?np,根据定理[11]8.21和8.22,hn的差分表的第0条对角线有形式

c?p,0?,c?p,1?,c?p,2?,?,c?p,p?,0,0,?

?n??n??n? n?c?p,0???0???c?p,1???1?????c?p,p???p?? (3.1)

??????p如果p=0,则hn?1,它是一个常数,公式(3.21)化为

?n?n0?1?1??0???1

??特别地

c?0,0??1

由于np作为n的多项式有一个等于0的常数项,故若p?1,也有

c?p,0??0 ?p?1?

通过引入新的表达式改写成公式(3.1).令

16