组合数学_第20讲（0530）.pptVIP

组合数学第20讲 王新红 第5章 递推关系 §5.5 母函数在递推关系中的应用 §5.5 母函数在递推关系中的应用 §5.5 母函数在递推关系中的应用 §5.5 母函数在递推关系中的应用 §5.5 母函数在递推关系中的应用 §5.5 母函数在递推关系中的应用 §5.5 母函数在递推关系中的应用 §5.5 母函数在递推关系中的应用 §5.5 母函数在递推关系中的应用 §5.5 母函数在递推关系中的应用 §5.5 母函数在递推关系中的应用 §5.5 母函数在递推关系中的应用 §5.5 母函数在递推关系中的应用 通常，称满足递推关系式(5.11) 的序列 为Catalan序列， 称序列中的数 为Catalan数。 §5.5 母函数在递推关系中的应用 §5.5 母函数在递推关系中的应用 §5.5 母函数在递推关系中的应用 本次授课到此结束 谢谢大家 §5.6 经典的递推关系（1） §5.6 经典的递推关系（2） §5.6 经典的递推关系（3） §5.6 经典的递推关系（4） §5.6 经典的递推关系（5） §5.6 经典的递推关系（6） §5.6 经典的递推关系（7） §5.6 经典的递推关系（8） §5.6 经典的递推关系（9） §5.6 经典的递推关系（9） §5.6 经典的递推关系（10） §5.6 经典的递推关系（11） §5.6 经典的递推关系（12） W(n)= O(nlogn) 归并排序 W(n) = 2W(n/2) + n?1 a = 2, b = 2, d(n) = O(n), XY = AC 2n + (AD+BC)2n/2 + BD 一般方法W(n)= O(n2) 分治法：令X = A2n/2 + B, Y = C2n/2 + D, 则 位乘问题：X,Y为n 位二进制数，n=2k, 求XY W(n)= 4 W(n/2) + cn W(1)= 1 a = 4，b = 2, W(n)= O(nlog4)= O(n2) XY = AC 2n + (AD+BC)2n/2 + BD 变换：AD + BC = (A-B)(D-C) + AC + BD W(n)= 3 W(n/2) + cn W(1)= 1 a = 3，b = 2, W(n)= O(nlog3)= O(n1.59) 作业: 红、白、兰涂色1?n方格，要求偶数个白色，问有多少种方案？ 母函数法和递推关系法 §5.6 经典的递推关系 5.6.1 Fibonacci数列 性质5.6.1：F1+F2+…+Fn=Fn+2-1 性质5.6.2：F1+F3+…+F2n-1=F2n 性质5.6.3：F12+F22+…+Fn2=Fn Fn+1 性质5.6.4：Fn-1 Fn+1-Fn2=(-1)n §5.6 经典的递推关系 5.6.2 第一类Stirling数 定义 5.5 定理 5.7 第一类Stirling数满足以下递推关系： 注：这是依赖于两个参数的递推关系。 令[x]n=x(x-1)(x-2)…(x-n+1)，若 ，则称S1(n,k)为第一类Stirling数。 证明：由定义易见，S1(0,0)=1, S1(n,0)=0 (n＞0) §5.6 经典的递推关系 5.6.3 第二类Stirling数 定义 5.6 定理 5.8 第二类Stirling数满足以下递推关系： 令[x]n=x(x-1)(x-2)…(x-n+1)，若 ，则称S2(n,k)为第二类Stirling数。 证明：由定义易见，S2(0,0)=1, S2(n,0)=0 (n＞0) §5.6 经典的递推关系 5.6.3 第二类Stirling数 定理 5.9 定理 5.9 第二类Stirling数S2(n,k)就是n个元素的集合划分为k个不相交的非空子集的方式数目。 n个有区别的球放入m个相同的盒子中，要求无一空盒的方式数即第二类Stirling数S2(n,m)。 证明：设A(n,k)是n个元素的集合划分成k个不相交的非空子集的方式数目。下面证明A(n,k)满足定理5.8中的递推关系式。 给定一个n元集合{a1,a2,…,an}，将这个n元集合划分成k个不相交的非空子集可以分为互不相容的两种情况： ①设{an}是k个子集合中的一个子集，于是把{a1,a2,…,an-1}划分为k-1个子集有A(n-1,k-1)种划分方式。②如果{an}不是k个子集合中的一个，