组合数学习题解答

1、=WORD完满版-可编写-专业资料分享=第一章：1.2.求在1000和9999之间各位数字都不同样，而且由奇数组成的整数个数。解：由奇数组成的4位数只能是由1，3，5，7，9这5个数字组成，又要求各位数字都不同样，因此这是一组从5个不同样元素中选4个的排列，因此，所求个数为：P(5,4)=120。个人坐在一排看戏有多少种就坐方式？若是其中有两人不愿坐在一起，问有多少种就坐方式？解：这显然是一组10个人的全排列问题，故共有10！种就坐方式。若是两个人坐在一起，则可把这两个人捆绑在一起，如是问题就变成9个人的全排列，共有9！种就坐方式。而这两个人相捆绑的方式又有2种（甲在乙的左面或右侧）。故两人坐

2、在一起的方式数共有2*9！，于是两人不坐在一起的方式共有10！-2*9！。个人围圆桌而坐，其中两人不愿坐在一起，问有多少种就坐方式？解：这是一组圆排列问题，10个人围圆就坐共有10!种方式。10两人坐在一起的方式数为29!,故两人不坐在一起的方式数为：9！-2*8！。91.14.求1到10000中，有多少正数，它的数字之和等于5？又有多少许字之和小于5的整数？解：(1)在1到9999中考虑，不是4位数的整数前面补足0，比方235写成0235,则问题就变成求：x+x+x+x=5的非负整数解的个数，故有1234F（4，5）451565(2)分为求：x1+x2+x3+x4=4的非负整数解，其个数为F

3、（4，4）=35x+x+x+x=3的非负整数解，其个数为F（4，3）=201234x+x+x+x=2的非负整数解，其个数为F（4，2）=101234x1+x2+x3+x4=1的非负整数解，其个数为F（4，1）=4x1+x2+x3+x4=0的非负整数解，其个数为F（4，0）=1将它们相加即得，F（4，4）+F（4，3）+F（4，2）+F（4，1）+F（4，0）=70。第二章：2.3.在边长为1的正三角形内任意放置5个点，则其中最少有两个点的距离1/2。解：将边为1的正三角形分成边是为1/2的四个小正三角形，将5个点放入四个小正三角形中，由鸽笼原理知，最少有一个小正三角形中放有2个点，而这两点的距

4、离1/2。1/21/21/22.5.在图中，每个方格着红色或蓝色，证明最少存在两列有同样的着色。-完满版学习资料分享-=WORD完满版-可编写-专业资料分享=解：每列着色的方式只可能有224种，现有5列，由鸽笼原理知，最少有二列着色方式同样。2.7.一个学生打算用37天总合60学时自学一本书，他计划每天最少自学1学时，证明：无论他怎样按排自学时间表，必然存在接踵的若干天，在这些天内其自学总时数恰好为13学时。解：设a1是第一天自学的时数，a2是第一，二天自学的时数的和，aj是第一，二，第j天自学时数的和，j1,2,37于是，序列a1,a2,a37是严格递加序列(每天最少一学时)，而且，a11,

5、a3760于是序列a113,a3713也是严格递加的序列，故a371373因此74个数a1,a37,a113,a371373都在1和73两个整数之间，由鸽笼原理知，这74个数中必有两个是相等的，由于a1,a2,a37中任何两数都不相等，故a113,a3713中任何两个数也是不相等的，因此，必然存在两个数i,j使得aiaj13aiaj13因此，在j1,j2,i这些天中，这个学生自学总时数恰好为13。2.10.证明：在任意52个整数中，必存在两个数，其和或差能被100整除。证明：设52个整数a1，a2，.，a52被100除的余数分别为r1，r2，.，r,而任意一整数被100除可能的余数为0，1，2

6、，.,99，共100个，它可分为51个类：0，1，5299，2，98，.49，51，50。因此，将51个类看做鸽子笼，则由鸽笼原理知，将r，r，.，12r52个鸽子放入51个笼中，最少有两个属于同一类，比方ri,rj,于是ri=rj+r=100,这就是说aa可100整除，或a+a可被100整除。或rijijij第三章3.2.求1到1000中既非完满平方又非完满立方的整数个数。解：设S1,2,1000;A1表示1到1000中完满平方数的会集，则A1表示1到1000中不是完满平方数的会集；A2表示1到1000中完满立方数的会集，则A2表示1到1000中不是完满立方数的会集。_故A1A2表示1到10

7、00中既非完满平方又非完满立方的整数的会集，由容斥原理（3.5）式）知：A1A2SA1A2A1A2(3.5)其中-完满版学习资料分享-=WORD完满版-可编写-专业资料分享=|S|1000，|A1|100031,|A2|3100010A1A2表示1到1000中既是完满平方又是完满立方的数的会集，故AA=61000=3,12将以上数值代入(3.5)式得A1A21000(31+10)+3=962故1到1000中既非完满平方又非完满立方的整数个数为962。3.8.在所有的n位数中，包含数字3，8，9但不包含数字0，4的数有多少？解：除去0，4，则在1，2，3，5，6，7，8，9这8个数字组成的n位数

8、中，令S表示由这8个数字组成的所有n位数的会集。则|S|=8n.P表示这样的性质：一个n位数不包含3；1P表示这样的性质：一个n位数不包含8；2P3表示这样的性质：一个n位数不包含9；并令Ai表示S中拥有性质Pi的元素组成的会集（i=1,2,3）。则A1A2A3表示S中包含3，又包含8，又包含9的所有n位数的会集。由容斥原理（3.5）式）得3|A1A2A3|=|S|Ai|AiAj|A1A2A3|（3.5）i1ij而A1nnn7,A27,A37A1A2nA3nA3n6,A16,A26A1A2A3n5，代入（3.5）式得A1A2A38n3?7n3?6n5n故所求的n位数有8n37n36n5n个。3

9、.10.求重集B3a,4b,5c的10-组合数。解：构造会集B=a,b,c。令会集B的所有10-组合组成的会集为S。由第一章的重复组合公式(1.11)有|S|F（3，10）310110=66。-完满版学习资料分享-=WORD完满版-可编写-专业资料分享=令p1表示S中的元素最少含有4个a这一性质，令p2表示S中的元素最少含有5个b这一性质，令p3表示S中的元素最少含有6个c这一性质，并令Ai(i=1,2,3)表示S中拥有性质pi(i=1,2,3)的元素所组成的会集，于是B的10-组合数就是S中不拥有性质p1,p2,p3的元素个数。由容斥原理（3.5）式）有：3|A1A2A3|=|S|Ai|Ai

10、Aj|A1A2A3|(3.5)i1ij由于已经求得|S|=66，下面分别计算(3.9)式右端其他的项。由于A1中的每一个10-组合最少含有4个a，故将每一个这样的组合去掉4个a就获取会集B的一个6-组合。反之，若是取B的一个6-组合并加4个a进去，就获取了A1的一个10-组合。于是A1的10-组合数就等于B的6-组合数。故有|A361|=F（3，6）2816同样的解析可得|A2351|=F（3，5）5|A3341|=F（3，4）42115用近似的解析方法可分别求得|A1311A2|F（3，1）1|A1301A3|F（3，0）031|A2A3|0（由于561110）|A1A2A3|0（同上）将以

11、上数值代人(3.9)式获取：|A1A2A3|66（282115）（310）06故所求的10-组合数为6。3.14.求由数字1，2，8所组成的全排列中，恰有4个数字在其自然地址上的全排列个数。8解：4个数在其自然地址共有种方式，对某一种方式，均有4个数字不在其自然地址，这4正好是一个错排，其方式数为D4（见定理3.2），由乘法规则有，恰有4个数字在其自然地址上的全排列数为-完满版学习资料分享-=WORD完满版-可编写-专业资料分享=8D4630。4第四章4.6求重集Ba,3b,5c,7d的10-组合数。解：设重集B的n-组合数为an，则序列an的一般母函数为f(x)(1xx2)(1xx2x3)(

12、1xx2x3x4x5)(1xx2x3x4x5x6x7)11x41x61x8=1x1x1x1x=(1-x4-x6-x8+x10+x12+x14-x18)3kxk3k031036343230因此a=1033333=286-84-35-10+1=158故重集B的10组合数为158。4.9.设重集Bb1,b2,b3,b4,b5,b6,并设ar是B满足以下条件的r-组合数，求序列a0,a1,ar,的一般母函数。a.每个bI出现3的倍数次。I1,2,3,4,5,6b1,b2至多出现1次，b3,b4最少出现2次，b5,b6最多出现4次。c.b1出现偶数次，b6出现奇数次，b3出现3的倍数次，b4出现5的倍数

13、次。d.每个bII1,2,3,4,5,6至多出现8次。解：a.f(x)(1x3x6x9)6F(6,k)(x3)kk0b.f(x)(1x)2(x2x3x4)2(1xx2x3x4)2c.f(x)(1x2x4)(xx3x5)(1x3x6x9)(1x5x10)+2+3+)2(1xxx-完满版学习资料分享-=WORD完满版-可编写-专业资料分享=d.f(x)(1x2x3x8)64.10有两颗骰子，每个骰子六个面上刻有1，2，3，4，5，6个点。问掷骰子后，点数之和为r，两颗骰子的点数有多少种搭配方式？解：每个骰子是不同样的，但谈论点数之和的时候不考虑序次，故该问题是组合问题。设有满足条件的搭配方式有ar

14、种，则其一般母函数为f(x)(xx2x6)2其中xr的系数ar即为所求的搭配方式数。4.14求由数字2，3，4，5，6，7组成的r位数中，3和5都出现偶数次，2和4最少出现一次的r位数的个数。解：这是一个排列问题。设满足条件的r位数的个数为ar，则序列(a1,a2,ar,)对应的指数母函数为：fe(x)(1x2x4.)2(xx2.)2(1xx2x3.)22!4!2!2!3!12(exex)2(ex1)2e2x21(6r25r34r43rrxr=322)4r1r!因此，ar1(6r0,r025r34r43r32r2),r045.2.若是用a表示没有两个0相邻的n位三元序列（即由0，1，2组成的序

15、列）的个数。求ann所满足的递归关系并解之。解：对n位三元序列的第一位数有三种选择方式:1)第一位选1，则在剩下的n-1位数中无两个0相邻的个数为an-1;2)第一位选2，则在剩下的n-1位数中无两个0相邻的个数为an-1;3)第一位选0,则在第二位又有两种选择方式：(1)第二位选1，则在剩下的n-2位数中无两个0相邻的个数为an-2；(2)第二位选2，则在剩下的n-2位数中无两个0相邻的个数为an-2显然有-完满版学习资料分享-=WORD完满版-可编写-专业资料分享=12=8a=3,a由加法规则得an所满足的递归关系为：an2an12an2(n3)a13,a28其特色方程为x2-2x-2=0

16、特色根为x1=1+3,x2=1-3由定理5.3知其通解为an=c1(1+3)n+c2(1-3)n由初始条件有c1(13)c2(13)3c1(13)2c2(13)28解以上方程组得c1323，c232366an13231n3231n3365.4.某人有n元钱，她每天要去菜市场买一次菜，每次买菜的品种很单调，也许买一元钱的蔬菜，也许买两元钱的猪肉，也许买两元钱的鱼。问，她有多少种不同样的方式花完这n元钱?解：设花完这n元钱的方式有an种，则第一次花销可分为下面几种情况：若第一次买一元钱的菜，则花完剩下的n-1元钱就有an-1种方式，若第一次买二元钱的肉，则花完剩下的n-2元钱就有an-2种方式，若

17、第一次买二元钱的鱼，则花完剩下的n-2元钱就有an-2种方式，显然有a1=1，a2=3.由加法规则,得递归关系以下：anan12an2(n3)a11,a23其特色方程为：x2x20.特色根x11,x22.通解anc1(1)nc22n.-完满版学习资料分享-=WORD完满版-可编写-专业资料分享=由初始条件得c1(1)c221c1(1)2c2223解得2c12.33故该递归关系的解为,can1(1)n2n233故她有1(1)n2n2种不同样的方式花完这n元钱。335.6求解以下递归关系an6an19an23(n2)a0,a11a0解：这是一个常系数线性非齐次递归关系式，其导出的齐次递归关系为：a

18、n*6an*19an*2其特色方程为x26x90，解得q1q23由定理5.3知，所导出的齐次线性递归关系的通解为a*nc1c2n-3n由于f(n)=3,且1不是式递归关系式的特色根，故设特解为anA将anA代入递归关系得A6A9A33A16由定理5.6知，递归关系式的通解为anaa*3c1c2n(-3)n16将初值条件代入上式并解得3c1161c212-完满版学习资料分享-=WORD完满版-可编写-专业资料分享=故an331n(-3)n。161612ban5an16an23n2(n2)a00,a11解：这也是一个常系数线性非齐次递归关系式，其导出的齐次递归关系的特色方程为x25x60特色根为x

19、12,x23由定理5.3知，所导出的齐次线性递归关系的通解为anc1(2)nc2(3)n由于f(n)=3n2,且1不是递归关系式的特色根，故设特解为anA0n2A1nA2将上式代入递归关系式解得A01,A117,A2115424288通解anananc1(2)nc2(3)n1n217n115424288由初始条件有c1c2115028811152c13c2174241288解得14,c237932故递归关系的解为：cananan14(2)n37(3)n1n217n115932424288an7an110an23n(n2)c.0,a11a0解：对应齐次递归关系的特色方程为x2-7x+10=0其特色根x1=5,x2=2an*5nc12nc2又f(n)=3n,且3不是递归关系式的特色根，故设特解为anA3n，将anA3n代-完满版学习资料分享-=WORD完满版-可