组合数学练习题(一)数学教学课件PPT

1、1组合数学练习题组合数学练习题(一一) 1. 有有20根完全相同的木棍从左至右竖立成一行，根完全相同的木棍从左至右竖立成一行，占占 据据20个位置个位置. 要从中选出要从中选出6根根. (1) 有多少种选择？有多少种选择？ (2) 如果选出的木棍中没有两根是位置相邻的，如果选出的木棍中没有两根是位置相邻的，又有多少种选择？又有多少种选择？ (3) 如果选出的每一对木棍之间必须至少有两如果选出的每一对木棍之间必须至少有两根木棍，又有多少种选择？根木棍，又有多少种选择？解解 (1) 有有 种种. 2062 (2) 所选出的所选出的6根木棍实际上可将这根木棍实际上可将这20根排成根排成一行的木棍分割

2、成一行的木棍分割成7段段(加上首和尾加上首和尾).设所选左边第设所选左边第1根木棍的左侧有根木棍的左侧有x1根未被选中的木棍；在第根未被选中的木棍；在第1 与与第第2根所选木棍之间有根所选木棍之间有x2根未被选中的木棍；根未被选中的木棍；在第在第5 与第与第6根所选木棍之间有根所选木棍之间有x6根未被选中的木根未被选中的木棍；在第棍；在第6根所选木棍的右侧有根所选木棍的右侧有x7根未被选中的木根未被选中的木棍，则由于没有两根选出的木棍是相邻的，所以棍，则由于没有两根选出的木棍是相邻的，所以=， 12345671714001,2,3,6ixxxxxxxxxxi3作变量代换作变量代换则原方程变成则

3、原方程变成，11771,2,3,6iiyxyxyxi 123456790,1,2,3,7iyyyyyyyyi这个方程的非负整数解的个数即为所求的选择数这个方程的非负整数解的个数即为所求的选择数971155005994(3) 同同(2)中的分析，此时有不定方程中的分析，此时有不定方程=， 12345671714002,2,3,6ixxxxxxxxxxi4711021044仿照仿照(2)，这个方程的非负整数解的个数即为所求这个方程的非负整数解的个数即为所求的选择数的选择数5 2. (1) 在在2n个物体中有个物体中有n个是相同的，则从这个是相同的，则从这2n个物体中选取个物体中选取n个的方法有几种

4、？个的方法有几种？ (2) 在在3n +1个物体中有个物体中有n个是相同的，则从这个是相同的，则从这3n +1个物体中选取个物体中选取n个的方法有几种？个的方法有几种？解解 (1) 若选出的物体有若选出的物体有 个不个不 (0,1,2, )k kn相同相同,则其余则其余n - - k个是相同的个是相同的,所以选取的方法数为所以选取的方法数为 201nnnnn 212212121122201nnnnnn(2) 类似于类似于(1)的分析可知，所以选取的方法数为的分析可知，所以选取的方法数为6 3. 用用 种颜色去涂种颜色去涂 棋盘，棋盘，每格涂一种颜色，求使得相邻格子异色，首末两格每格涂一种颜色，

5、求使得相邻格子异色，首末两格也异色的涂色方法数也异色的涂色方法数. (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从而从而7 111222(1)(1)(1)( 1)nnnnnnhm mhm mm mh 12333(1)(1)(1)( 1)nnn

6、nm 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)nnmm8 4. 用用 种颜色去涂种颜色去涂 棱锥的棱锥的n + 1个顶点个顶点,每个顶点涂一种颜色，求使得棱锥的每个顶点涂一种颜色，求使得棱锥的每条棱的两个端点异色的涂色方法数每条棱的两个端点异色的涂色方法数 (3)m m (3)n n(, ).K m n 解解 设设V是一个是一个n棱锥棱锥,则可依则可依如下两个步骤去完成如下两个步骤去完成V的

7、的n + 1个顶点的涂色工作个顶点的涂色工作: 先涂顶点先涂顶点v0,有有m种涂色方法种涂色方法;然后用异于然后用异于v0颜色的颜色的m - - 1种颜色种颜色去涂顶点序列去涂顶点序列v1， v2， vn, 使得相邻顶点异色使得相邻顶点异色且首末两个顶点也异色且首末两个顶点也异色.0v1v2v3vnv9由上题可知由上题可知,完成此步骤的方法有完成此步骤的方法有 (2)( 1) (2)nnmm种，种，由乘法原理由乘法原理,得所求涂色方法数为得所求涂色方法数为 (, )(2)( 1)(2)nnK m nm mm m10na解解 所所求求种种类类数数 的的母母函函数数为为32321111(1)111

8、(1)xxxxxx 24236( )(1)(1)(1)(1)G xxxxxxxx 5. 将充分多的苹果、香蕉、橘子和梨这将充分多的苹果、香蕉、橘子和梨这4种水果种水果装袋，要求各袋有偶数个苹果，最多装袋，要求各袋有偶数个苹果，最多2个橘子，个橘子，3的的倍数个香蕉，最多倍数个香蕉，最多1个梨个梨. 如果每袋装如果每袋装n个水果，求装个水果，求装袋的种类数袋的种类数.11001(1)nnnnnxnxn 1.nan 所所以以12 6. 把把n个相异的球放到个相异的球放到4个相异盒子个相异盒子 中，求使得中，求使得 含有奇数个球，含有奇数个球， 含有偶数个球的不含有偶数个球的不同的放球方法数同的放球

9、方法数.1234,A A A A1A2A则数列则数列 对应的指母函数为对应的指母函数为na解解 设满足条件的放球方法数为设满足条件的放球方法数为.na3524232( )()(1)3!5!2!4! (1)2!3!exxxxG xxxxx 13222xxxxxeeeee 414xe 1144!nnnxn 114!nnnxn 14.nna 所以所以14 7. 由数字由数字1至至9组成的每种数字至少出现组成的每种数字至少出现1次的次的 位数有多少个？位数有多少个？ (9)n n解解 设所求的数为设所求的数为an,则则an的指母函数为的指母函数为 9(9)09( 1)kk xkek 2399( )()

10、(1)2!3!xexxG xxe 9009( 1)(9)!nknknxknk 9009( 1)(9)!nknnkxknk 909( 1)(9)knnkakk所以所以15 8. 由字母由字母a,b,c,d,e组成的总字母数为组成的总字母数为n的单词的单词中，要求中，要求a与与b的个数之和为偶数，求这样的单词的个数之和为偶数，求这样的单词的个数的个数. 解解 这样的单词有两类：一类包括偶数个这样的单词有两类：一类包括偶数个a与与偶数个偶数个b；另一类包括奇数个；另一类包括奇数个a与奇数个与奇数个b.设所求设所求的数为的数为an,则则an的指母函数为的指母函数为 242323352323( )(1)

11、 (1)2!4!2!3! () (1)3!5!2!3!exxxxG xxxxxxxx16 223322xxxxxxeeeeee故故 50011()(5)22!nnxxnnnxxeenn 0512!nnnxn 512nna17 9.有多少个长度为有多少个长度为n的的0与与1串串, 在这些串中在这些串中, 既不既不包含子串包含子串010，也不包含子串，也不包含子串101？解解 设这种数串的个数为设这种数串的个数为 将满足条件的数串分为两类：将满足条件的数串分为两类： ,nf1224ff则则，3n 时时， (1) 最后两位数字相同最后两位数字相同. 这种长度为这种长度为n的数串可的数串可由长度为由长

12、度为n-1的串最后一位数字重复一次而得，故的串最后一位数字重复一次而得，故这类数串的个数这类数串的个数 1nf ； (2) 最后两位数字不同最后两位数字不同. 这种长度为这种长度为n的数串可的数串可由长度为由长度为n-2的串最后一位的串最后一位(设为设为a)重复一次，再加重复一次，再加上与上与a不同的数字而得不同的数字而得, 故这类数串的个数为故这类数串的个数为 2.nf 18于是得递推关系于是得递推关系12122, 4 nnnfffff 由由Fibonacci数列数列,得通解得通解121515()()22nnnfcc代入初值代入初值,得得 125555,55cc1121515 ()()225

13、nnnf所所以以19 10. 由由0,1,2,3组成的长度为组成的长度为n的序列中，求含的序列中，求含偶数个偶数个0的序列个数和含奇数个的序列个数和含奇数个0的序列个数的序列个数. 解解 设设an为含偶数个为含偶数个0的序列个数，的序列个数，bn为含奇为含奇数个数个0的序列个数的序列个数.则有则有 114 3nnnnnnababa解得解得1122 4,nnna1144(22 4)nnnnnnba112 42nn20 11. 十个数字十个数字(0到到9)和四个运算符和四个运算符( +，- -，*，/ )组成组成14个元素，求由其中的个元素，求由其中的n个元素的排列构成一个元素的排列构成一形式算术

14、表达式的个数形式算术表达式的个数. 解解 令令an表示表示n个元素排列成算术表达式的数目，个元素排列成算术表达式的数目，则则 1212104010, 120 nnnaaaaa解得解得133 65133 65(565)(565)5252nnna21 12. 在一圆周上均匀地取在一圆周上均匀地取2n个点，用个点，用n条两两条两两不相交的弦把这些点配成对，求所有这种配对的不相交的弦把这些点配成对，求所有这种配对的方式数方式数. 解解 设所求配对的方式数为设所求配对的方式数为hn,则则h1 = 1,则则h0 = 1,设设2n个点依次为个点依次为， ， ， ，1222,knvvvv连接连接，12,kvv

15、12k2(1)n 2配对方式数为配对方式数为hk- -1,则将圆周一分为二则将圆周一分为二,一边有一边有2(k - -1)个点个点,另一边有另一边有2(n- -k)个点，配对方式数为个点，配对方式数为hn- -k.22于是于是 10112101nnkn knnnkhhhh hh hhh解得解得 211nnhnn23 13.一个计算机系统把一个十进制数字串作为一个一个计算机系统把一个十进制数字串作为一个编码字，如果它包含偶数个编码字，如果它包含偶数个0，就是有效的，就是有效的.求有效的求有效的n位编码字的个数位编码字的个数an .解解 显然显然 19.a 若末位数是若末位数是1到到9中某个数，则

16、前面中某个数，则前面n-1位组成的位组成的有效数有有效数有an-1个，因此，末位数不是个，因此，末位数不是0的的n位有效数字位有效数字有有 9 an-1个个.若末位数是若末位数是0，则这样的，则这样的n位十进制数有位十进制数有10n-1个，个， 而不是有效数的有而不是有效数的有 an-1个个 (因因n-1位的有效数后面添一位的有效数后面添一个个0就不是有效数了就不是有效数了), 所以末位数是所以末位数是0的有效数有的有效数有 241110nna 个个.于是得递推关系于是得递推关系 11119(10)9nnnnaaaa 1118109nnnaaa 即即 解得通解解得通解 185 10,nnnaC

17、 代入初始条件得代入初始条件得 1.2C 故所求有效数字有故所求有效数字有 114 85 10nnna 个个. 25 14.把把 件彼此相异的物品分给甲、乙、件彼此相异的物品分给甲、乙、丙三人，使得甲至少分得两件物品，乙和丙至少分丙三人，使得甲至少分得两件物品，乙和丙至少分得一件物品，有多少种不同的分法？得一件物品，有多少种不同的分法？(4)n n 解解 设有设有N种不同的分法种不同的分法. 因为把因为把n件彼此相异件彼此相异的物品分给的物品分给3个人，使得每人至少分得一件物品的个人，使得每人至少分得一件物品的方法共有方法共有 332033!( , )( 1)33 23innniSn kii

18、种，其中使得甲恰分得一件物品的分法有种，其中使得甲恰分得一件物品的分法有 221102( 1)(22)inninini 种，故种，故 11(33 23)(22) 3(6)223nnnnnNnnn 27 15. 令令m和和n是非负整数且是非负整数且 , 有有m + n 个人个人站成一排进入剧院，入场费为每人站成一排进入剧院，入场费为每人50元元.这这 m + n 个个人中有人中有n个人有个人有50元面额的钞票，而另外元面额的钞票，而另外m个人只个人只有有100元面额的钞票元面额的钞票.售票处开门时使用一个空的现售票处开门时使用一个空的现金收银机金收银机.求能够使得需要的时候总有零钱可找的队求能够

19、使得需要的时候总有零钱可找的队列方式数列方式数. nm 证证 将有将有50元的人用元的人用1标识，有标识，有100元的人用元的人用-1标标识，则该问题为：包括识，则该问题为：包括m个个- -1和和n个个1的的m + n个数个数 12,m na aa构成的序列，使构成的序列，使28120, 1,2,kaaakmn这这m + n个数的排列是集合个数的排列是集合 的排列，的排列， 1,( 1)nm排列数为排列数为 mnm 设设A是满足以上要求的序列全体，称为可接受是满足以上要求的序列全体，称为可接受排列排列.设设U为不可接受排列的全体，则为不可接受排列的全体，则 |mnAUm29 由于由于U是不可接

20、受排列的集合，对是不可接受排列的集合，对U中任一个中任一个排列，必有最小的排列，必有最小的k，使，使120kaaa从而有从而有 1210, 1kkaaaa即即k - -1是偶数，且是偶数，且 中有相等个数的中有相等个数的1 121,ka aa和和- -1.将将121,kkm na aaaa中前中前k个变号后，可得一个个变号后，可得一个由由n +1个个1和和m - -1个个- -1的序列的序列.30 反反之之n +1个个1和和m - -1个个- -1的序列的序列.由于由于 ,故故必存在必存在k，使，使 中中1的个数恰比的个数恰比- -1的个数的个数多多1.只要将只要将这这n +1个个1和和m -

21、 -1个个- -1的的序列前序列前k项变号，项变号，就可得一就可得一个有个有n个个1和和m个个- -1的的U中中一个排列一个排列.所以所以U是集合是集合 的排列全体，于是的排列全体，于是 nm12,ka aa (1) 1,(1) ( 1)nm |1mnUn所以所以 |1mnmnAmn 11mnnmnm31组合数学练习题组合数学练习题(二二)一一部部由由 楼楼上上升升到到楼楼的的电电梯梯内内共共有有 个个乘乘客客 他他们们分分别别到到 楼楼至至楼楼去去，该该电电梯梯从从 楼楼开开始始每每层层楼楼都都停停 以以便便让让乘乘客客决决定定是是否否离离开开电电梯梯求求 个个乘乘客客离离开开电电梯梯的的不

22、不同同方方法法的的种种数数求求 至至楼楼每每层层楼楼都都有有人人离离开开电电梯梯的的不不同同方方法法的的种种数数 1. 110, 5105, . (1) . (2) 5 0. 1nn32(1) 5 6 7 8 9 106,6.nn 解解 因因为为每每个个人人可可以以选选择择在在 、 楼楼离离开开电电梯梯，即即每每人人离离开开电电梯梯的的方方法法有有 种种 由由乘乘法法原原理理 个个乘乘客客离离开开电电梯梯的的不不同同方方法法有有种种(2),|6 .nSnS 令令 表表示示由由 个个乘乘客客离离开开电电梯梯的的全全部部不不同同方方法法所所成成之之集集 则则, , 4 (1,2,6), | 1,2

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

24、球全部排在一起，问但不能让任何一种同颜色的球全部排在一起，问有多少种排法有多少种排法(假定同色球不加区别假定同色球不加区别)？ 解解 设所求数为设所求数为N，以，以S表示由表示由4个黑球，个黑球，3个个白球，白球，2个红球作成的全排列之集，个红球作成的全排列之集，A，B，C分分别表示别表示S中中4个黑球，个黑球，3个白球，个白球，2个红球排在一起个红球排在一起的全排列之集的全排列之集. 则则 ，！ ！ ！9!6|1260 |604! 3! 2!1 32SA35，！ ！ ！ ！ ！ ！ ！78|105 |2804 1 243 14!5!|12 |201! 1! 2!1! 3! 1!6!|30 |

25、364 1 1BCABACBCABC所以所以| | (|) (|)|NABCSABCABACBCABC 87136 3. n个单位各派个单位各派2名代表出席一个会议，名代表出席一个会议，2n名名代表围一圆桌坐下代表围一圆桌坐下.试问：试问： (1) 同一单位代表相邻而坐的方案有多少种？同一单位代表相邻而坐的方案有多少种？ (3)同一单位的代表不相邻的方案有多少种同一单位的代表不相邻的方案有多少种? 解解 (1) 这是这是2n个元的圆排列个元的圆排列,故各单位代表入座故各单位代表入座方式有方式有 (21)!.n 种种 (2) 将同一单位代表看作一个整体参与排列，有将同一单位代表看作一个整体参与排

26、列，有 (1)!.n 种种2 (1)!.nn 种种而同一单位的两位代表坐法有而同一单位的两位代表坐法有2种种(左或右左或右),故同一单位代表相邻而坐的方案有故同一单位代表相邻而坐的方案有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互互异异；12|2 (1)!nnA AAn38由容斥原理，所求方案数为由容斥原理，所求方案数为12

27、2| (21)!2(22)!1 2 (23)!( 1)2 (1)!2nnnnAAAnnnnnnn 同类问题：同类问题： n对夫妻围圆桌而坐，求夫妻不相邻的入坐方对夫妻围圆桌而坐，求夫妻不相邻的入坐方案数案数.39 4.用用10 个球垒成一个三角阵，使得个球垒成一个三角阵，使得1个球在个球在2个球之上，个球之上，2个球在个球在3个球之上，个球之上，3个球在个球在4个球之个球之上上.这个三角阵可自由旋转这个三角阵可自由旋转.用红色与蓝色对该阵各用红色与蓝色对该阵各球着色，求不等价着色数球着色，求不等价着色数.如果再允许翻转该阵，如果再允许翻转该阵，不等价着色数又有多少种？不等价着色数又有多少种？

28、12345678910 解解 将三角阵上的球标将三角阵上的球标以以110表示，它表示，它分别分别绕其绕其中心逆时针旋转中心逆时针旋转0 ,120 ,240得置换群得置换群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 )352L41如果球阵可以翻转，则置换群为如果球阵可以翻转

29、，则置换群为 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 9)(5)(10)ppp1 16 61046(22232 )208L由由 定理知，所求方案数为定理知，所求方案数为Polya 42 5.将一个将一个3行行3列棋盘的列棋盘的9个正方形着红色和蓝色，个正方形着红色和蓝色，棋盘可以绕对称中心旋转，但不能绕对称轴翻转，棋盘可以绕对称中心旋转，但不能绕对称轴翻转，求不等价的着色方案数求不等价的着色方案数.从而得置换群从而得置换

30、群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 12345678943故由故由 定理知不等价的着色方案数为定理知不等价的着色方案数为Polya 9351(22 22 )1404L 44证证 用用表表示示相相邻邻 个个数数之之和和. . (1,2,10)3iq i注注意意到到这这些些数数中中的的每每个个数数都都在在作作和和数数时时出出现现了了 次次 故故有有12101,2,10,3,qqq 101 3(1210)165iiq 6.把把1到到10这这10个数随机地写成一个圆圈个数随机地写成一个圆圈.证明：证明：必存在某必存在某3个相邻数之和大于或等于个相邻数之和大于或等于17.45即即存存在在某某个个使使 , 17.iiqq问问题题归归结结为为: :把把件件物物品品放放入入个个抽抽屉屉里里16