级组合数学复习题解答PPT学习教案

1、会计学1级组合数学复习题解答级组合数学复习题解答2 (2) 所选出的6根木棍实际上可将这20根排成一行的木棍分割成7段(加上首和尾).设所选左边第1根木棍的左侧有x1根未被选中的木棍；在第1 与第2根所选木棍之间有x2根未被选中的木棍；在第5 与第6根所选木棍之间有x6根未被选中的木棍；在第6根所选木棍的右侧有x7根未被选中的木棍，则由于没有两根选出的木棍是相邻的，所以=， 12345671714001,2,3,6ixxxxxxxxxxi第1页/共48页3作变量代换则原方程变成，11771,2,3,6iiyxyxyxi 123456790,1,2,3,7iyyyyyyyyi这个方程的非负整数解

2、的个数即为所求的选择数97115500599第2页/共48页4(3) 同(2)中的分析，此时有不定方程=， 12345671714002,2,3,6ixxxxxxxxxxi4711021044仿照(2)，这个方程的非负整数解的个数即为所求的选择数第3页/共48页5 2. (1) 在2n个物体中有n个是相同的，则从这2n个物体中选取n个的方法有几种？ (2) 在3n +1个物体中有n个是相同的，则从这3n +1个物体中选取n个的方法有几种？解 (1) 若选出的物体有 个不 (0,1,2, )k kn相同相同,则其余则其余n - - k个是相同的个是相同的,所以选取的方法数为所以选取的方法数为 2

3、01nnnnn 212212121122201nnnnnn(2) 类似于(1)的分析可知，所以选取的方法数为第4页/共48页6 3. 用 种颜色去涂 棋盘，每格涂一种颜色，求使得相邻格子异色，首末两格也异色的涂色方法数. (2)m m 1 ()n nm解 用hn表示所求方法数.易知 2(1).hm m用m种颜色去涂 棋盘，每格涂一种颜 1 ()n nm色，使得相邻格子异色的涂色方法数有 1(1)nm m种,其中使得首末两格同色的涂色方法有 种,所以 1nh 11(1) (2)nnnhm mhn从而第5页/共48页7 111222(1)(1)(1)( 1)nnnnnnhm mhm mm mh 1

4、2333(1)(1)(1)( 1)nnnnm mm mm mh 12322(1)(1) ( 1)(1)( 1)(1)nnnnm mm mm mm m 2332(1)(1)(1) ( 1)(1)( 1)nnnnm mmmm 12(1)( 1)(1)(1)1nnmm mm (1)( 1) (1)nnmm第6页/共48页8 4. 用 种颜色去涂 棱锥的n + 1个顶点,每个顶点涂一种颜色，求使得棱锥的每条棱的两个端点异色的涂色方法数 (3)m m (3)n n(, ).K m n 解 设V是一个n棱锥,则可依如下两个步骤去完成V的n + 1个顶点的涂色工作: 先涂顶点先涂顶点v0,有有m种涂色方法种

5、涂色方法;然后用异于然后用异于v0颜色的颜色的m - - 1种颜色种颜色去涂顶点序列去涂顶点序列v1， v2， vn, 使得相邻顶点异色使得相邻顶点异色且首末两个顶点也异色且首末两个顶点也异色.0v1v2v3vnv第7页/共48页9由上题可知,完成此步骤的方法有 (2)( 1) (2)nnmm种，由乘法原理,得所求涂色方法数为 (, )(2)( 1)(2)nnK m nm mm m第8页/共48页10na解解 所所求求种种类类数数 的的母母函函数数为为32321111(1)111(1)xxxxxx 24236( )(1)(1)(1)(1)G xxxxxxxx 5. 将充分多的苹果、香蕉、橘子和

6、梨这4种水果装袋，要求各袋有偶数个苹果，最多2个橘子，3的倍数个香蕉，最多1个梨. 如果每袋装n个水果，求装袋的种类数.第9页/共48页11001(1)nnnnnxnxn 1.nan 所所以以第10页/共48页12 6. 把n个相异的球放到4个相异盒子 中，求使得 含有奇数个球， 含有偶数个球的不同的放球方法数.1234,A A A A1A2A则数列 对应的指母函数为na解 设满足条件的放球方法数为.na3524232( )()(1)3!5!2!4! (1)2!3!exxxxGxxxxx 第11页/共48页13222xxxxxeeeee 414xe 1144!nnnxn 114!nnnxn 1

7、4.nna 所以第12页/共48页14 7. 由数字1至9组成的每种数字至少出现1次的 位数有多少个？ (9)n n解 设所求的数为an,则an的指母函数为 9(9)09( 1)kk xkek 2399( )()(1)2!3!xexxG xxe 9009( 1)(9)!nknknxknk 9009( 1)(9)!nknnkxknk 909( 1)(9)knnkakk所以第13页/共48页15 8. 由字母a,b,c,d,e组成的总字母数为n的单词中，要求a与b的个数之和为偶数，求这样的单词的个数. 解 这样的单词有两类：一类包括偶数个a与偶数个b；另一类包括奇数个a与奇数个b.设所求的数为an

8、,则an的指母函数为 242323352323( )(1) (1)2!4!2!3! () (1)3!5!2!3!exxxxG xxxxxxxx第14页/共48页16 223322xxxxxxeeeeee故 50011()(5)22!nnxxnnnxxeenn 0512!nnnxn 512nna第15页/共48页17 9.有多少个长度为n的0与1串, 在这些串中, 既不包含子串010，也不包含子串101？解 设这种数串的个数为 将满足条件的数串分为两类： ,nf1224ff则则，3n 时时， (1) 最后两位数字相同. 这种长度为n的数串可由长度为n-1的串最后一位数字重复一次而得，故这类数串的

9、个数 1nf ； (2) 最后两位数字不同. 这种长度为n的数串可由长度为n-2的串最后一位(设为a)重复一次，再加上与a不同的数字而得, 故这类数串的个数为 2.nf 第16页/共48页18于是得递推关系12122, 4 nnnfffff 由Fibonacci数列,得通解121515()()22nnnfcc代入初值,得 125555,55cc1121515 ()()225nnnf所所以以第17页/共48页19 10. 由0,1,2,3组成的长度为n的序列中，求含偶数个0的序列个数和含奇数个0的序列个数. 解 设an为含偶数个0的序列个数，bn为含奇数个0的序列个数.则有 114 3nnnnn

10、nababa解得1122 4,nnna1144(22 4)nnnnnnba112 42nn第18页/共48页20 11. 十个数字十个数字(0到到9)和四个运算符和四个运算符( +，- -，*，/ )组成组成14个元素，求由其中的个元素，求由其中的n个元素的排列构成一个元素的排列构成一形式算术表达式的个数形式算术表达式的个数. 解 令an表示n个元素排列成算术表达式的数目，则 1212104010, 120 nnnaaaaa解得133 65133 65(565)(565)5252nnna第19页/共48页21 12. 在一圆周上均匀地取2n个点，用n条两两不相交的弦把这些点配成对，求所有这种配

11、对的方式数. 解 设所求配对的方式数为hn,则h1 = 1,则h0 = 1,设2n个点依次为， ， ， ，1222,knvvvv连接，12,kvv12k2(1)n 2配对方式数为配对方式数为hk- -1,则将圆周一分为二则将圆周一分为二,一边有一边有2(k - -1)个点个点,另一边有2(n- -k)个点，配对方式数为个点，配对方式数为hn- -k.第20页/共48页22于是 10112101nnkn knnnkhhhh hh hhh解得 211nnhnn第21页/共48页23 13.一个计算机系统把一个十进制数字串作为一个编码字，如果它包含偶数个0，就是有效的.求有效的n位编码字的个数an

12、.解 显然 19.a 若末位数是1到9中某个数，则前面n-1位组成的有效数有an-1个，因此，末位数不是0的n位有效数字有 9 an-1个.若末位数是0，则这样的n位十进制数有10n-1个， 而不是有效数的有 an-1个 (因n-1位的有效数后面添一个0就不是有效数了), 所以末位数是0的有效数有 第22页/共48页241110nna 个.于是得递推关系 11119(10)9nnnnaaaa 1118109nnnaaa 即 解得通解 185 10,nnnaC 代入初始条件得 1.2C 故所求有效数字有 114 85 10nnna 个. 第23页/共48页25 14.把 件彼此相异的物品分给甲、

13、乙、丙三人，使得甲至少分得两件物品，乙和丙至少分得一件物品，有多少种不同的分法？(4)n n 解 设有N种不同的分法. 因为把n件彼此相异的物品分给3个人，使得每人至少分得一件物品的方法共有 332033!( , )( 1)33 23innniSn kii 种，其中使得甲恰分得一件物品的分法有 221102( 1)(22)inninini 第24页/共48页种，故 11(33 23)(22) 3(6)223nnnnnNnnn 第25页/共48页27 15. 令m和n是非负整数且 , 有m + n 个人站成一排进入剧院，入场费为每人50元.这 m + n 个人中有n个人有50元面额的钞票，而另外

14、m个人只有100元面额的钞票.售票处开门时使用一个空的现金收银机.求能够使得需要的时候总有零钱可找的队列方式数. nm 证证 将有将有50元的人用元的人用1标识，有标识，有100元的人用元的人用-1标标识，则该问题为：包括识，则该问题为：包括m个个- -1和和n个个1的的m + n个数个数 12,m na aa构成的序列，使第26页/共48页28120, 1,2,kaaakmn这m + n个数的排列是集合 的排列， 1,( 1)nm排列数为 mnm 设A是满足以上要求的序列全体，称为可接受排列.设U为不可接受排列的全体，则 |mnAUm第27页/共48页29 由于U是不可接受排列的集合，对U中

15、任一个排列，必有最小的k，使120kaaa从而有 1210, 1kkaaaa即即k - -1是偶数，且是偶数，且 中有相等个数的中有相等个数的1 121,ka aa和和- -1.将将121,kkm na aaaa中前中前k个变号后，可得一个个变号后，可得一个由由n +1个个1和和m - -1个个- -1的序列的序列.第28页/共48页30 反反之之n +1个个1和和m - -1个个- -1的序列的序列.由于由于 ,故故必存在必存在k，使，使 中中1的个数恰比的个数恰比- -1的个数的个数多多1.只要将只要将这这n +1个个1和和m - -1个个- -1的的序列前序列前k项变号，项变号，就可得一

16、就可得一个有个有n个个1和和m个个- -1的的U中中一个排列一个排列.所以所以U是集合是集合 的排列全体，于是的排列全体，于是 nm12,ka aa (1) 1,(1) ( 1)nm |1mnUn所以 |1mnmnAmn 11mnnmnm第29页/共48页31组合数学练习题(二)一一部部由由 楼楼上上升升到到楼楼的的电电梯梯内内共共有有 个个乘乘客客 他他们们分分别别到到 楼楼至至楼楼去去，该该电电梯梯从从 楼楼开开始始每每层层楼楼都都停停 以以便便让让乘乘客客决决定定是是否否离离开开电电梯梯求求 个个乘乘客客离离开开电电梯梯的的不不同同方方法法的的种种数数求求 至至楼楼每每层层楼楼都都有有人

17、人离离开开电电梯梯的的不不同同方方法法的的种种数数 1. 110, 5105, . (1) . (2) 5 0. 1nn第30页/共48页32(1) 5 6 7 8 9 106,6.nn 解解 因因为为每每个个人人可可以以选选择择在在 、 楼楼离离开开电电梯梯，即即每每人人离离开开电电梯梯的的方方法法有有 种种由由乘乘法法原原理理 个个乘乘客客离离开开电电梯梯的的不不同同方方法法有有种种(2),|6 .nSnS 令令 表表示示由由 个个乘乘客客离离开开电电梯梯的的全全部部不不同同方方法法所所成成之之集集 则则, , 4 (1,2,6), | 1,2,6iiiaSai iaPAaS aPi 设设

18、若若在在方方法法 之之下下 没没有有人人在在第第楼楼离离开开电电梯梯 则则称称 具具有有性性质质令令具具有有性性质质| (61)5 1,2,6nniAi则则有有 第31页/共48页33| (62)4 nnijA Aij同样 同样 1212, | (6) (16)kniiikA AAkiii一般地一般地126,666| 6543123666 210456nnnnnnnAAA 由逐步淘汰原理 所求方案数为由逐步淘汰原理 所求方案数为506( 1)(6)knkkk 第32页/共48页34 2.将4个黑球、3个白球、2个红球排成一列，但不能让任何一种同颜色的球全部排在一起，问有多少种排法(假定同色球不

19、加区别)？ 解 设所求数为N，以S表示由4个黑球，3个白球，2个红球作成的全排列之集，A，B，C分别表示S中4个黑球，3个白球，2个红球排在一起的全排列之集. 则 ，！ ！ ！9!6|1260 |604! 3! 2!1 32SA第33页/共48页35，！ ！ ！ ！ ！ ！ ！78|105 |2804 1 243 14!5!|12 |201! 1! 2!1! 3! 1!6!|30 |364 1 1BCABACBCABC所以| | (|) (|)|NABCSABCABACBCABC 871第34页/共48页36 3. n个单位各派2名代表出席一个会议，2n名代表围一圆桌坐下.试问： (1) 同一

20、单位代表相邻而坐的方案有多少种？ (3)同一单位的代表不相邻的方案有多少种? 解 (1) 这是2n个元的圆排列,故各单位代表入座方式有 (21)!.n 种种 (2) 将同一单位代表看作一个整体参与排列，有 (1)!.n 种种2 (1)!.nn 种种而同一单位的两位代表坐法有2种(左或右),故同一单位代表相邻而坐的方案有第35页/共48页37(3) 设这2n个人入座方式的全体为S，则 | (21)!.SnS中第i个单位的两个人相邻的入座方式 iA 设设1,2,in ，则 |2(22)!iAn；2|2 (23)!, ijA Anij ；3|2 (24)!, , ,ijkA A Ani j k互互异

21、异；12|2 (1)!nnA AAn第36页/共48页38由容斥原理，所求方案数为122| (21)!2(22)!1 2 (23)!( 1)2 (1)!2nnnnAAAnnnnnnn 同类问题： n对夫妻围圆桌而坐，求夫妻不相邻的入坐方案数.第37页/共48页39 4.用10 个球垒成一个三角阵，使得1个球在2个球之上，2个球在3个球之上，3个球在4个球之上.这个三角阵可自由旋转.用红色与蓝色对该阵各球着色，求不等价着色数.如果再允许翻转该阵，不等价着色数又有多少种？ 12345678910 解 将三角阵上的球标以110表示，它分别绕其中心逆时针旋转0 ,120 ,240得置换群第38页/共4

22、8页40其中 123,Qppp 1(1)(2)(3)(4)(5)(6)(7)(8)(9)(10)p(恒等置换)， 2(1 10 7)(2 6 8)(3 9 4)(5) p(逆时转 )120 3(1 7 10)(2 8 6)(3 4 9)(5) p(逆时转 )240 由 定理知，所求方案数为Polya 1 13 3104(222 )352L第39页/共48页41如果球阵可以翻转，则置换群为 123456,Qpppppp其中 同前，123,ppp， 456(1)(5)(2 3)(4 6)(7 10)(8 9)(1 10)(2 9)(3 6)(4 8)(5)(7)(1 7)(2 4)(3 8)(6

23、9)(5)(10)ppp1 16 61046(22232 )208L由 定理知，所求方案数为Polya 第40页/共48页42 5.将一个3行3列棋盘的9个正方形着红色和蓝色，棋盘可以绕对称中心旋转，但不能绕对称轴翻转，求不等价的着色方案数.从而得置换群Q所含的置换为90 ,180 ,270 ，解 棋盘可以分别绕对称中心逆时针旋转0 , 1234(1)(2)(3)(4)(5)(6)(7)(8)(9)(1 3 9 7)(2 6 8 4)(5)(1 9)(2 8)(3 7)(4 6)(5)(1 7 9 3)(2 4 8 6)(5)qqqq 123456789第41页/共48页43故由 定理知不等价的着色方案数为Polya 9351(22 22 )1404L 第42页/共48页44证证 用用表表示示相相邻邻 个个数数之之和和. . (1,2,10)3iq i注注意意到到这这些些数数中中的的每每个个数数都都在在作作和和数数时时出出现现了了 次次 故故有有12101,2,10,3,qqq 101 3(1210)165iiq 6.把1到10这10个数随机地写成一个圆圈.证明：