2015级组合数学复习题解答解析

1组合数学练习题(一)1.有20根完全相同的木棍从左至右竖立成一行，占据20个位置.要从中选出6根.(1)有多少种选择？(2)如果选出的木棍中没有两根是位置相邻的，又有多少种选择？(3)如果选出的每一对木棍之间必须至少有两根木棍，又有多少种选择？解(1)有种.2062(2)所选出的6根木棍实际上可将这20根排成一行的木棍分割成7段(加上首和尾).设所选左边第1根木棍的左侧有x1根未被选中的木棍；在第1与第2根所选木棍之间有x2根未被选中的木棍；…；在第5与第6根所选木棍之间有x6根未被选中的木棍；在第6根所选木棍的右侧有x7根未被选中的木棍，则由于没有两根选出的木棍是相邻的，所以=，，12345671714001,2,3,,6ixxxxxxxxxxi3作变量代换则原方程变成，，11771,2,3,,6iiyxyxyxi123456790,1,2,3,,7iyyyyyyyyi这个方程的非负整数解的个数即为所求的选择数971155005994(3)同(2)中的分析，此时有不定方程=，，12345671714002,2,3,,6ixxxxxxxxxxi4711021044仿照(2)，这个方程的非负整数解的个数即为所求的选择数52.(1)在2n个物体中有n个是相同的，则从这2n个物体中选取n个的方法有几种？(2)在3n+1个物体中有n个是相同的，则从这3n+1个物体中选取n个的方法有几种？解(1)若选出的物体有个不(0,1,2,,)kkn相同,则其余n-k个是相同的,所以选取的方法数为201nnnnn212212121122201nnnnnn(2)类似于(1)的分析可知，所以选取的方法数为63.用种颜色去涂棋盘，每格涂一种颜色，求使得相邻格子异色，首末两格也异色的涂色方法数.(2)mm1()nnm解用hn表示所求方法数.易知2(1).hmm用m种颜色去涂棋盘，每格涂一种颜1()nnm色，使得相邻格子异色的涂色方法数有1(1)nmm种,其中使得首末两格同色的涂色方法有种,所以1nh11(1)(2)nnnhmmhn从而7111222(1)(1)(1)(1)nnnnnnhmmhmmmmh12333(1)(1)(1)(1)nnnnmmmmmmh12322(1)(1)(1)(1)(1)(1)nnnnmmmmmmmm2332(1)[(1)(1)(1)(1)(1)]nnnnmmmmm12(1)(1)(1)(1)1nnmmmm(1)(1)(1)nnmm84.用种颜色去涂棱锥的n+1个顶点,每个顶点涂一种颜色，求使得棱锥的每条棱的两个端点异色的涂色方法数(3)mm(3)nn(,).Kmn解设V是一个n棱锥,则可依如下两个步骤去完成V的n+1个顶点的涂色工作:先涂顶点v0,有m种涂色方法;然后用异于v0颜色的m-1种颜色去涂顶点序列v1，v2，…，vn,使得相邻顶点异色且首末两个顶点也异色.0v1v2v3vnv9由上题可知,完成此步骤的方法有(2)(1)(2)nnmm种，由乘法原理,得所求涂色方法数为(,)(2)(1)(2)nnKmnmmmm10na解所求种类数的母函数为32321111(1)111(1)xxxxxx24236()(1)(1)(1)(1)Gxxxxxxxx5.将充分多的苹果、香蕉、橘子和梨这4种水果装袋，要求各袋有偶数个苹果，最多2个橘子，3的倍数个香蕉，最多1个梨.如果每袋装n个水果，求装袋的种类数.11001(1)nnnnnxnxn1.nan所以126.把n个相异的球放到4个相异盒子中，求使得含有奇数个球，含有偶数个球的不同的放球方法数.1234,,,AAAA1A2A则数列对应的指母函数为{}na解设满足条件的放球方法数为.na3524232()()(1)3!5!2!4!(1)2!3!exxxxGxxxxx13222xxxxxeeeee414xe1144!nnnxn114!nnnxn14.nna所以147.由数字1至9组成的每种数字至少出现1次的位数有多少个？(9)nn解设所求的数为an,则{an}的指母函数为9(9)09(1)kkxkek2399()()(1)2!3!xexxGxxe9009(1)(9)!nknknxknk9009(1)(9)!nknnkxknk909(1)(9)knnkakk所以158.由字母a,b,c,d,e组成的总字母数为n的单词中，要求a与b的个数之和为偶数，求这样的单词的个数.解这样的单词有两类：一类包括偶数个a与偶数个b；另一类包括奇数个a与奇数个b.设所求的数为an,则{an}的指母函数为242323352323()(1)(1)2!4!2!3!()(1)3!5!2!3!exxxxGxxxxxxxx16223322xxxxxxeeeeee故50011()(5)22!!nnxxnnnxxeenn0512!nnnxn512nna179.有多少个长度为n的0与1串,在这些串中,既不包含子串010，也不包含子串101？解设这种数串的个数为将满足条件的数串分为两类：,nf1224ff则，，3n时，(1)最后两位数字相同.这种长度为n的数串可由长度为n-1的串最后一位数字重复一次而得，故这类数串的个数1nf；(2)最后两位数字不同.这种长度为n的数串可由长度为n-2的串最后一位(设为a)重复一次，再加上与a不同的数字而得,故这类数串的个数为2.nf18于是得递推关系12122,4nnnfffff由Fibonacci数列,得通解121515()()22nnnfcc代入初值,得125555,55cc1121515()()225nnnf所以1910.由0,1,2,3组成的长度为n的序列中，求含偶数个0的序列个数和含奇数个0的序列个数.解设an为含偶数个0的序列个数，bn为含奇数个0的序列个数.则有1143nnnnnnababa解得11224,nnna1144(224)nnnnnnba11242nn2011.十个数字(0到9)和四个运算符(+，-，*，/)组成14个元素，求由其中的n个元素的排列构成一形式算术表达式的个数.解令an表示n个元素排列成算术表达式的数目，则1212104010,120nnnaaaaa解得1336513365(565)(565)5252nnna2112.在一圆周上均匀地取2n个点，用n条两两不相交的弦把这些点配成对，求所有这种配对的方式数.解设所求配对的方式数为hn,则h1=1,则h0=1,设2n个点依次为，，，，，1222,knvvvv连接，12,kvv12k2(1)n2配对方式数为hk-1,则将圆周一分为二,一边有2(k-1)个点,另一边有2(n-k)个点，配对方式数为hn-k.22于是10112101nnknknnnkhhhhhhhhh解得211nnhnn2313.一个计算机系统把一个十进制数字串作为一个编码字，如果它包含偶数个0，就是有效的.求有效的n位编码字的个数an.解显然19.a若末位数是1到9中某个数，则前面n-1位组成的有效数有an-1个，因此，末位数不是0的n位有效数字有9an-1个.若末位数是0，则这样的n位十进制数有10n-1个，而不是有效数的有an-1个(因n-1位的有效数后面添一个0就不是有效数了),所以末位数是0的有效数有241110nna个.于是得递推关系11119(10)9nnnnaaaa1118109nnnaaa即解得通解18510,nnnaC代入初始条件得1.2C故所求有效数字有1148510nnna个.2514.把件彼此相异的物品分给甲、乙、丙三人，使得甲至少分得两件物品，乙和丙至少分得一件物品，有多少种不同的分法？(4)nn解设有N种不同的分法.因为把n件彼此相异的物品分给3个人，使得每人至少分得一件物品的方法共有332033!(,)(1)3323innniSnkii种，其中使得甲恰分得一件物品的分法有221102(1)(22)inninini种，故11(3323)(22)3(6)223nnnnnNnnn2715.令m和n是非负整数且,有m+n个人站成一排进入剧院，入场费为每人50元.这m+n个人中有n个人有50元面额的钞票，而另外m个人只有100元面额的钞票.售票处开门时使用一个空的现金收银机.求能够使得需要的时候总有零钱可找的队列方式数.nm证将有50元的人用1标识，有100元的人用-1标识，则该问题为：包括m个-1和n个1的m+n个数12,,,mnaaa构成的序列，使28120,1,2,,kaaakmn这m+n个数的排列是集合的排列，{1,(1)}nm排列数为mnm设A是满足以上要求的序列全体，称为可接受排列.设U为不可接受排列的全体，则||||mnAUm29由于U是不可接受排列的集合，对U中任一个排列，必有最小的k，使120kaaa从而有1210,1kkaaaa即k-1是偶数，且中有相等个数的1121,,,kaaa和-1.将121,,,,,,kkmnaaaaa中前k个变号后，可得一个由n+1个1和m-1个-1的序列.30反之n+1个1和m-1个-1的序列.由于,故必存在k，使中1的个数恰比-1的个数多1.只要将这n+1个1和m-1个-1的序列前k项变号，就可得一个有n个1和m个-1的U中一个排列.所以U是集合的排列全体，于是nm12,,,kaaa{(1)1,(1)(1)}nm||1mnUn所以||1mnmnAmn11mnnmnm31组合数学练习题(二)一部由楼上升到楼的电梯内共有个乘客他们分别到楼至楼去，该电梯从楼开始每层楼都停以便让乘客决定是否离开电梯求个乘客离开电梯的不同方法的种数求至楼每层楼都有人离开电梯的不同方法的种数1.110,5105,.(1).(2)50.1nn32(1)56789106,6.nn解因为每个人可以选择在、、、、、楼离开电梯，即每人离开电梯的方法有种由乘法原理个乘客离开电梯的不同方法有种(2),||6.nSnS令表示由个乘客离开电梯的全部不同方法所成之集则,,4(1,2,,6),,{|}1,2,,6iiiaSaiiaPAaSaPi设若在方法之下没有人在第楼离开电梯则称具有性质令具有性质||(61)51,2,,6nniAi则有33||(62)4nnijAAij同样1212,||(6)(16)kniiikAAAkiii一般地126,666||6543123666210456nnnnnnnAAA