发布时间 : 星期日 文章组合数学中常见的计数方法更新完毕开始阅读
沈阳理工大学学士学位论文
???f(1)f(n?1)?f(2)f(n?2)???f(n?1)f(1)?xn
n?2?从而可得:s(x)?x?s2(x)
11解之可得:s(x)?(1?1?4x)或s(x)?(1?1?4x)
221由s(x)定义有s(0)?0,从而只能取:s(x)?(1?1?4x)
2 由牛顿二项式定理有
111(?1)?(?n?1)?2?2n-2?nnn2221?4x?1??(?4)x?1??(?)??n-1??x n!nn?1n?1????11?2n-2?nnx?s(x)代入s(x)?(1?1?4x)有:s(x)???,所以的的系数f(n)为: x??2n?1n?n-1?1?2n-2??f(n)??? n-1n???2.4 Catalan数的性质
性质1 Cn?1?性质2 Cn?14n-2Cn n?1n?2n?CkCn?k,n?3 ?2(n?3)k?2?n?k?性质3 Cn?1??(?1)k??k?1??Cn?k
k?0????n?k?1??n?k???性质4 Cn??(?1)k?1???k????k?1???Cn?k,n?3
k?1???????2n??2n?性质5 Cn???n?????n?1??,n?0
????性质6 C0?1,Cn?1?2(2n?1)Cn n?221n?n?性质7 Cn???i?? n?1i?0???性质8 C0?1,Cn?1??CiCn?i,n?0
i?0n9
沈阳理工大学学士学位论文
性质9 设m是任一正整数,当n?m时,有: i)
k!!k?n?m???CC?C?(-1)??a1a2am?k?2m-nn!(k-2n)!!;
a1?a2???am?nk?0??mnmii)
a1?a2????n?C2a1-1C2a1-1?C2am-1???(-1)j?0k?0k?1-j?m?(m-k)!!k!!???k?22(m-n)?1j!(2n-j-1)!(m-k-2j)!!(k?2j?2-4n)!! ??m2nm-kkiii)当n?2m时,有:
k?l?p?m??m-k??k??CC?C?(-1)?????2a12a22am?k????l????j??
a1?a2???am?nk?0p?0l?0j?0??????
(m-k)!!k!!
22(m-n)p!(2n-p)!(l-2p)!!(l?p-2n)!!性质10 Cn~4nn32,这个是Catalan数的增长趋势.
?2.5 Catalan数的组合意义及应用
2.5.1 Catalan数的组合意义
经典Catalan数具有许多组合应用背景,除了以上所引几何、代数、三角问题外,不少是组合学或图论问题的实例。我们依据文献[13],查阅若干相关著作,又补充若干新例,得到以下20种,有的具有典型性,有的可以看作组合模型,有的形式有别,实质相同。 1)不同构的有n条边的种植树(planted tree)的棵树是Catalan数Cn2)有n片树叶的有序三度树根的个数是Catalan数Cn-1?1?。
3)n个顶点的不同二元树的个数是Catalan数Cn0二元树的定义:空集或一组有限个顶点,满足:①有一个特定的点称作“根点”;②去掉这个根点后,余下的顶点组成两支子二元树:左子树与右子树?1?。
4)从点(0,0)到点(n+1,n+1),除端点外与对角线不相交的(在在对角线一侧的)非降路径数是Catalan数Cn?1??1?。
。
5)循环序列满足递推关系:C0?1,(n?2)Cn?1?(4n?2)Cn,(n?0), Cn是Catalan数。由此
6可知:C0?1,Cn?(4-)Cn-1?1?。
n6)2n个均匀分布在一个圆周上,用n条不相交的弦将这2n个点配对成n对,则不同的配对
10
沈阳理工大学学士学位论文
方式数是Cn=
1?2n??1?,(n0) 。 ?????n?1?n?7)序列(x1,x2,…x2n),其中xi=+1或-1,(i=1,2,…,2n)
?x?x2???xk?0满足条件?1 ,对于每个k=1,2, …,2n-1,2n,则满足上述条件
x?x???x?022n?1的数是Catalan数?1?。
8)n个1和n个0组成一2n位的二进制数,要求从左到右扫描,1的累计数不小于0的累计数,满足这一条件的2n位的二进制数的个数是Catalan数?1?。
9)在两个候选人A和B的投票选举中,共有2n个人投票,最终结果是支持A的票数和B票数都是n票。在开票过程中始终使A的票数不少于B的票数的投票方案数是Catalan数Cn?1?。
10)有2n个人在剧院票房门前准备买票入场。每张票价是50美分,而且此时票房售票员没有零钱。这2n人恰好有n个人有50美分的钱,其余n个人只有1美分的钱。如果在任何时候售票员都能找开零钱的2n个人的排列方法数是Catalan数Cn是Catalan数Cn?1??1?。
11)有2n个高低不同的人,排成两行,使得第一排n个人都比第二排n个人高的排列方法
。
12)设Sn是n个正整数a1,a2,?,an不同排列的集合数,且a1,a2,?,an满足下列条件: ① a1?a2??an?n,② a1?a2??ak?k (对任意的k a1?1,a2?2,?,an?n,则a1,a2,?,an满足上述条件的序列的个数是Catalan数?1?。 14)设a1,a2,?,an与b1,b2,?,bn是两个完全不同的序列,则把这两个序列融合在一起组成一个新的序列,使得后一个序列与前一个序列相对应的数始终排在前一个序列数后面的排列的个数是Catalan数?1?。 15)设a1,a2,?,an与b1,b2,?,bn是两个完全不同的序列, 则把这两个序列融合在一起组成一个新的序列。一个逆序是指ai排在bi的后面(i=1,2,…,n),则这两个序列融合在一起恰有k个逆序的排列数是Catalan数?1?。 16)设在E?{e1,e2,?,en}上定义了一种非结构合、非交换的乘法运算,则由A的全体元素作成的乘积的方法数Un-1?n!Cn-1,其中Cn-1为Catalan数?1?。 17)有2n个人围着桌子就坐,手臂不相交的握手的方法数是Catalan数Cn?1?。 11 沈阳理工大学学士学位论文 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