清华版组合数学(第二版)第一章习题答案.docVIP

组合数学第一章答案 3 再证表示的唯一性： 设n=∑ai·i!=∑bi·i!, 不妨设aj＞bj,令j=max{i|ai≠bi} aj·j!+aj-1·(j-1)!+…+a1·1! =bj·j!+bj-1·(j-1)!+…+b1·1!, (aj-bj)·j!=∑(bi-ai)·i!≥j!＞∑i·i! ≥∑|bi-ai|·i!≥∑(bi-ai)·i! 另一种证法：令j=min{i|ai≠bi} ∑ai·i!=∑bi·i!, 两边被(j+1)!除,得余数aj·j!=bj·j!,矛盾. * * i=1 k i=1 k i=1 j-1 i=1 j-1 i=1 j-1 i=1 j-1 i≥j i≥j * * * 6.解：首先所有数都用6位表示，从000000到999999中在每位上0出现了10 次,所以0共出现了6·10 次,0出现在最前面的次数应该从中去掉，000000到999999中最左1位的0出现了10 次，000000到099999中左数第2位的0出现了10 次，000000到009999左数第3位的0出现了10 次, 000000到000999左数第4位的0出现了10 次, 000000到000099左数第5位的0出现了10 次, 000000到000009左数第6位的0出现了10 次。 另外1000000的6个0应该被加上。 所以0共出现了 6·10 –10 –10 –10 –10 –10 –10 +6 = 488895次。 * * 5 5 5 4 3 2 1 0 5 5 4 3 2 1 0 * * * 22.证：(a)设有2n个不同球放入n个不同的盒子里，每盒两个，这个方案数应该是整数。对2n个球进行排列得到方案数为(2n)!。而把2个球放入同一个盒子里不计顺序，应该把全排列数除掉这些重复计算的次数，n个盒子内部的排列共重复计算了2 次。得到2n个不同球放入n个不同的盒子里，每盒两个的方案数(2n)!/2 若有3n个不同的球,放入n个不同盒子,故同理得(3n)!/(3!) 是整数。 * * n n n * * * 2.证： 组合意义： 等式左边：n个不同的球，先任取出1个，再从余下的n-1个中取r个； 等式右边：n个不同球中任意取出r+1个，并指定其中任意一个为第一个。 显然两种方案数相同。 * * nC(n-1,r) = n ———— = ——————— (n-1)! (r+1)·n! r!·(n-r-1)! (r+1)·r!·(n-r-1)! = —————— = (r+1)C(n,r+1). (r+1)·n! (r+1)!·(n-r-1)! * * * 3.证： 设有n个不同的小球，A、B两个盒子,A盒中恰好放1个球,B盒中可放任意个球。有两种方法放球： ①先从n个球中取k个球(k≥1),再从中挑一个放入A盒,方案数共为∑kC(n,k),其余球放入B盒。 ②先从n个球中任取一球放入A盒，剩下n-1个球每个有两种可能，要么放入B盒，要么不放，故方案数为n2 . 显然两种方法方案数应该一样。 * * k=1 n n-1 * * * 4.解：设取的第一组数有a个,第二组有b个,而要求第一组数中最小数大于第二组中最大的，即只要取出一组m个数(设m=a+b),从大到小取a个作为第一组,剩余的为第二组。此时方案数为 C(n,m)。从m个数中取第一组数共有m-1中取法。总的方案数为∑(m-1)C(n,m)=n·2 +1. 5.解：第1步从特定引擎对面的3个中取1个有C(3,1)种取法，第2步从特定引擎一边的2个中取1个有C(2,1)种取法，第3步从特定引擎对面的2个中取1个有C(2,1)中取法，剩下的每边1个取法固定。 所以共有C(3,1)·C(2,1)·C(2,1)=12种方案。 * * m=2 n n-1 * * * 7.解：把n个男、n个女分别进行全排列，然后按乘法法则放到一起，而男女分别在前面,应该再乘2,即方案数为2·(n!) 个. 围成一个圆桌坐下，根据圆排列法则，方案数为2 ·(n!) /(2n)个. 8.证：每个盒子不空，即每个盒子里至少放一个球，因为球完全一样，问题转化为将n-r个小球放入r个不同的盒子，每个盒子可以