1.8应用举例习题课.ppt

1、即Vandermonde恒等式 解释1：从m个互异红球和n个互异蓝球中取r个球,按r个球中红球的个数分类. 解释2：(0,0)到(m+n-r，r)点的路径. (0,0)(m-r+k,r-k)(m+n-r,r) C(m,r-k) C(n,k),1.7 组合意义的解释,1.7 组合意义的解释,例1 从号码1,2,N中每次取出一个并登记，然后放回，连取n次，得到一个由n个数字组成的数列，问按这种方式能得到 (1)多少个严格递增数列(nN); (2)多少个不减数列？,解 (1) 无重组合 C(N,n) (2) 可重组合 C(N+n-1,n),1.8 应用举例,例2 某保密装置须同时使用若干把不同的钥匙

2、才能打开。现有人，每人持若干钥匙。须人到场，所备钥匙才能开锁。问至少有多少把不同的钥匙？每人至少持几把钥匙？,1.8 应用举例,解 每人至少缺把钥匙，且每人所缺钥匙 不同。故至少共有C(7,3)=35把不同的钥匙。,任一人对于其他人中的每人,都至少有把 钥匙与之相配才能开锁.故每人至少持C(6,3)20 把不同的钥匙。,注：任意3个人所持的钥匙至少比规定的少1把，不同的3人组所缺的钥匙是不同的， 否则，比如a,b,c与a,b,d所缺的钥匙相同，这样两组合并有4人a,b,c,d仍缺1把钥匙，与4人到场就不缺钥匙的假设相矛盾，故至少有C(7,3)把钥匙。7个人中的任意一个人必须有足够多的钥匙，对于

3、其他6人中的每3个人都至少有1把不同的钥匙与之相配才能开锁，故每人至少持C(6,3)把钥匙。,1.8 应用举例,这里所做的分析还只是一种可能性，为了容易理解，举一个较简单的例子加以说明，注意这个例子构造的对称性或均衡性： 比如：现有4人，每人持若干钥匙。须3人到场，所备钥匙才能开锁。所求如上。那么共有C(4,2)=6把不同的钥匙。每人有C(3,2)=3把钥匙。,1.8 应用举例,例3 有4个相同质点,总能量为4E0,E0是常数。每个质点所具能量为kE0,k=0,1,2,3,4. A)若能级为kE0的质点可有k2 +1种状态，而且服从Bose-Einstein分布，即同能级的质点可以处于相同的状

4、态,问系统有几种不同的状态?(或图像) B)若能级为kE0的质点可有2(k2 +1)种状态，而且服从Fermi-Dirac分布，即不允许同能级的两个质点有相同状态,问系统有几种不同状态?(或图像),1.8 应用举例,解,1.8 应用举例,1.8 应用举例,例4. 凸n边形没有3条对角线交于一点. 计算各边及各对角线所组成的互不重叠的多边形区域的个数.,1.8 应用举例,解 令Nk:区域中k边形的个数。,从两种角度计算各区域的顶点数(包含重复计得的数目)首先可以如下计算,其中m是最大多边形的边数。,另一方面，每两条对角线决定一个内部多边 形的顶点，因此(1)式中计算内部的多边形 顶点数所得数值是

5、4C(n,4)(每个内部顶点在(1)式 中重复计算4次，因为总是4个区域共一个顶点),1.8 应用举例,而(1)中凸多边形的每个顶点重复计数n-2次，故,现在，再从两个角度来计算所有区域的内 角和的总和，首先，它显然是,1.8 应用举例,第一章 习题,1.3. m个男生，n个女生，排成一行，其中m，n都是正整数，若 (a) 男生不相邻(mn+1)； (b) n个女生形成一个整体； (c) 男生A和女生B排在一起； 分别讨论有多少种方案.,解：首先所有数都用6位表示，从000000到999999中在每位上0出现了105 次，所以0共出现了6105 次，0出现在最前面的次数应该从中去掉， 0000

6、00到999999中最左1位的0出现了105次，000000到099999中左数第2位的0出现了104次，000000到009999左数第3位的0出现了103次, 000000到000999左数第4位的0出现了102 次, 000000到000099左数第5位的0出现了101次, 000000到000009左数第6位的0出现了100 次。 另外1000000的6个0应该被加上。 所以0共出现了 6105 105 104 103 102 101 100 +6 = 488895次。,1.15. 试求从1到1000000的整数中，0出现了多少次？,解：每个盒子不空，即每个盒子里至少放一个球，因为球完全一样，问题转化为将n-r个小球放入r个不同的盒子，每个盒子可以放任意个球，可以有空盒，根据可重组合定理可得共有C(n-r+r-1,n-r) = C(n-1,n-r)种方案。根据C(n,r)=C(n,n-r)，可得 C(n-1,n-r)=C(n-1,n-1-(n-r)=C(n-1,r-1) 个方案.,1.18. 8个盒子排成一列，5个有标志的球放到盒子中，每盒最多放一个球，要求空盒不相邻，问有多少种排列方案？,解：先将5个球进行全排列，有