组合数学第三章ppt课件.ppt

《组合数学第三章ppt课件.ppt》由会员分享，可在线阅读，更多相关《组合数学第三章ppt课件.ppt（81页珍藏版）》请在三一办公上搜索。

1、2022/11/13,计算机科学与技术学院,1,3.5.1 集合的分划与第二类Stirling数 定义3.5.1 集合S的子集族称为n元集S的一个k-分划，如果这个子集族满足每个Si非空； 当ij时， 其中每个Si称为一个分划块，也把这个k-分划记为：,集合的分划与Stirling数,2022/11/13,计算机科学与技术学院,2,第二类Stirling数,2022/11/13,计算机科学与技术学院,3,第二类Stirling数,2022/11/13,计算机科学与技术学院,4,第二类Stirling数,2022/11/13,计算机科学与技术学院,5,第二类Stirling数,2022/11/1

2、3,计算机科学与技术学院,6,第二类Stirling数,2022/11/13,计算机科学与技术学院,7,第二类Stirling数,2022/11/13,计算机科学与技术学院,8,第二类Stirling数,2022/11/13,计算机科学与技术学院,9,第二类Stirling数,2022/11/13,计算机科学与技术学院,10,第二类Stirling数,2022/11/13,计算机科学与技术学院,11,作业,2022/11/13,计算机科学与技术学院,12,第一类Stirling数也与集合的分划相关 集合有A=1,2,3,47个2-分划，但我们要求将每个分划块做成圆排列(或者轮换)，则共可构成1

3、1个不同的圆排列组, 图示见书63页,第一类Stirling数,2022/11/13,计算机科学与技术学院,13,2022/11/13,计算机科学与技术学院,14,定义3.5.3 一个n元集合的全部k-分划所形成的不同的圆排列组的个数，即k-圆排列分划数记为第一类Stirling数，表示为 或S1(n,k),性质(1)性质(2)性质(3)性质(4),2022/11/13,计算机科学与技术学院,15,定理3.5.3 第一类Stirling数满足如下递推关系,第一类Stirling数,2022/11/13,计算机科学与技术学院,16,证明：等式左边 是将集合的k-圆排列分划数，这些圆排列组可以分成

4、两类： 第1类：an单独构成一个圆排列，只需对集合A-an进行(k-1)-圆排列分划，再加上an这个圆排列，就构成了A的k-圆排列分划，因此，这类分划有 个。,第一类Stirling数,2022/11/13,计算机科学与技术学院,17,第2类： an不是A的k-圆排列分划中的单独一个圆排列，此时，先构造A-an的k-圆排列分划，共有 种方法，然后对于A-an的每个k-圆排列分划，将an插入该k-圆排列分划的k个圆排列中的某一个圆排列中，共有n-1种不同的插入方法，因此集合A的此类k-圆排列分划共有 个。 综上以上分析，由加法原理，有,2022/11/13,计算机科学与技术学院,18,小结：S2

5、(n,k) vs. S1(n,k),S2 (n,1)=1S2 (n,n)=1S2 (n,n-1)=C(n,2)S2 (n,k)=0(kn)S2 (n+1,k)=S2 (n,k-1)+kS2 (n,k)S2 (n,k)的生成函数为,S1(n,1)=(n-1)!S1(n,n)=1S1(n,n-1)=C(n,2)S1 (n,k)=0(kn) S1(n+1,k)= S1 (n,k-1)+nS1 (n,k)S1 (n,k)的生成函数为P(x,n),2022/11/13,计算机科学与技术学院,19,正整数的分拆,2022/11/13,计算机科学与技术学院,20,正整数的分拆,2022/11/13,计算机科

6、学与技术学院,21,正整数的分拆,2022/11/13,计算机科学与技术学院,22,4的分拆,正整数的分拆,2022/11/13,计算机科学与技术学院,23,正整数的分拆,集合的（无序）分划A=a,b,c,dA=a,bc d =a,cb d =a,db c =b,ca d =b,da c =c,da bS2(4,3)=C(4,2)=6A=1,11 1B(4,3)=1,2022/11/13,计算机科学与技术学院,24,有序分拆,2022/11/13,计算机科学与技术学院,25,有序分拆,2022/11/13,计算机科学与技术学院,26,有序分拆,2022/11/13,计算机科学与技术学院,27,

7、2022/11/13,计算机科学与技术学院,28,有序分拆,2022/11/13,计算机科学与技术学院,29,有序分拆,2022/11/13,计算机科学与技术学院,30,有序分拆,2022/11/13,计算机科学与技术学院,31,正偶数：,非负偶数：,2022/11/13,计算机科学与技术学院,32,有序分拆,2022/11/13,计算机科学与技术学院,33,有序分拆,2022/11/13,计算机科学与技术学院,34,2022/11/13,计算机科学与技术学院,35,无序分拆,2022/11/13,计算机科学与技术学院,36,无序分拆,2022/11/13,计算机科学与技术学院,37,无序分拆

8、,B(n,1)=1B(n,n)=1B(n,n-1)=1B(n,2)= n/2,2022/11/13,计算机科学与技术学院,38,无序分拆,2022/11/13,计算机科学与技术学院,39,无序分拆,2022/11/13,计算机科学与技术学院,40,无序分拆,2022/11/13,计算机科学与技术学院,41,无序分拆,2022/11/13,计算机科学与技术学院,42,无序分拆,2022/11/13,计算机科学与技术学院,43,无序分拆,2022/11/13,计算机科学与技术学院,44,分拆的Ferrers图,2022/11/13,计算机科学与技术学院,45,分拆的Ferrers图,2022/11

9、/13,计算机科学与技术学院,46,分拆的Ferrers图,2022/11/13,计算机科学与技术学院,47,分拆的Ferrers图,2022/11/13,计算机科学与技术学院,48,分拆的Ferrers图,2022/11/13,计算机科学与技术学院,49,分拆的Ferrers图,2022/11/13,计算机科学与技术学院,50,分拆的Ferrers图,2022/11/13,计算机科学与技术学院,51,分拆的Ferrers图,2022/11/13,计算机科学与技术学院,52,分拆的Ferrers图,2022/11/13,计算机科学与技术学院,53,分拆的Ferrers图,2022/11/13,

10、计算机科学与技术学院,54,分拆的Ferrers图,2022/11/13,计算机科学与技术学院,55,分拆的Ferrers图,2022/11/13,计算机科学与技术学院,56,小结：S2(n,k) vs. B(n,k),S2 (n,1)=1S2 (n,n)=1S2 (n,n-1)=C(n,2)S2 (n,2)=2n-1-1S2 (n+1,k)=S2 (n,k-1)+kS2 (n,k)有序分划k! S2 (n,k)S2 (n,k)有显示表达式,B(n,1)=1B(n,n)=1B(n,n-1)=1B(n,2)=n/2B(n+k,k)=B(n,1)+ B(n,2) + B(n,3)+B(n,k)有序

11、分拆C(n-1,k-1)B(n,k)无显示表达式,2022/11/13,计算机科学与技术学院,57,小结,2022/11/13,计算机科学与技术学院,58,分配问题,2022/11/13,计算机科学与技术学院,59,分配问题,2022/11/13,计算机科学与技术学院,60,分配问题,2022/11/13,计算机科学与技术学院,61,分配问题,2022/11/13,计算机科学与技术学院,62,分配问题,2022/11/13,计算机科学与技术学院,63,分配问题,2022/11/13,计算机科学与技术学院,64,分配问题,2022/11/13,计算机科学与技术学院,65,分配问题,2022/11

12、/13,计算机科学与技术学院,66,分配问题,2022/11/13,计算机科学与技术学院,67,分配问题,2022/11/13,计算机科学与技术学院,68,分配问题,习题3.43把n个不同的球放入m个不同的盒子里，允许有空盒，则放球的方法数为,2022/11/13,计算机科学与技术学院,69,分配问题,2022/11/13,计算机科学与技术学院,70,分配问题,2022/11/13,计算机科学与技术学院,71,分配问题,2022/11/13,计算机科学与技术学院,72,分配问题,2022/11/13,计算机科学与技术学院,73,分配问题,2022/11/13,计算机科学与技术学院,74,分配问题,2022/11/13,计算机科学与技术学院,75,分配问题,2022/11/13,计算机科学与技术学院,76,分配问题,2022/11/13,计算机科学与技术学院,77,分配问题,2022/11/13,计算机科学与技术学院,78,分配问题,2022/11/13,计算机科学与技术学院,79,分配问题,2022/11/13,计算机科学与技术学院,80,分配问题,2022/11/13,计算机科学与技术学院,81,作业,pp. 83 3.8, 3.9, 3.17, 3.21(1), 3.24, 3.25,