《组合数学习题解答》由会员分享，可在线阅读，更多相关《组合数学习题解答（12页珍藏版）》请在金锄头文库上搜索。
1、第一章：1.2. 求在1000和9999之间各位数字都不相同，而且由奇数构成的整数个数。解：由奇数构成的4位数只能是由1，3，5，7，9这5个数字构成，又要求各位数字都不相同，因此这是一组从5个不同元素中选4个的排列，所以，所求个数为：P(5,4)=120。 1.4. 10个人坐在一排看戏有多少种就坐方式？如果其中有两人不愿坐在一起，问有多少种就坐方式？解：这显然是一组10个人的全排列问题，故共有10！种就坐方式。如果两个人坐在一起，则可把这两个人捆绑在一起，如是问题就变成9个人的全排列，共有9！种就坐方式。而这两个人相捆绑的方式又有2种（甲在乙的左面或右面）。故两人坐在一起的方式数共有2*9
2、！，于是两人不坐在一 起的方式共有 10！- 2*9！。1.5. 10个人围圆桌而坐，其中两人不愿坐在一起，问有多少种就坐方式？解：这是一组圆排列问题，10个人围圆就坐共有 种方式。两人坐在一起的方式数为,故两人不坐在一起的方式数为：9！-2*8！。1.14. 求1到10000中，有多少正数，它的数字之和等于5？又有多少数字之和小于5的整数？解：(1)在1到9999中考虑，不是4位数的整数前面补足0，例如235写成0235,则问题就变为求：x1+x2+x3+x4=5 的非负整数解的个数，故有F（4，5）56(2)分为求：x1+x2+x3+x4=4 的非负整数解，其个数为F（4，4）=35x1+
3、x2+x3+x4=3 的非负整数解，其个数为F（4，3）=20x1+x2+x3+x4=2 的非负整数解，其个数为F（4，2）=10x1+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个点，而这两点的距离1/2。
4、1/2 1/2 1/22.5. 在图中，每个方格着红色或蓝色，证明至少存在两列有相同的着色。解：每列着色的方式只可能有种，现有列，由鸽笼原理知，至少有二列着色方式相同。 2.7. 一个学生打算用37天总共60学时自学一本书，他计划每天至少自学1学时，证明：无论他怎样按排自学时间表，必然存在相继的若干天，在这些天内其自学总时数恰好为13学时。解：设是第一天自学的时数，是第一，二天自学的时数的和，是第一，二， ，第天自学时数的和，于是，序列是严格递增序列(每天至少一学时)，而且， 于是序列也是严格递增的序列，故因此74个数都在1和73两个整数之间，由鸽笼原理知，这74个数中必有两个是相等的，由于中
5、任何两数都不相等，故中任何两个数也是不相等的，因此，一定存在两个数使得因此，在这些天中，这个学生自学总时数恰好为13。 2.10. 证明：在任意52个整数中，必存在两个数，其和或差能被100整除。证明：设52个整数a1，a2，.，a52被100除的余数分别为r1，r2，.，r52,而任意一整数被100除可能的余数为0，1，2，.,99，共100个，它可分为51个类：0，1，99，2，98，.49，51，50。因此，将51个类看做鸽子笼，则由鸽笼原理知，将r1，r2，.，r52 个鸽子放入51个笼中，至少有两个属于同一类，例如ri,rj,于是ri=rj或ri+rj=100,这就是说aiaj 可1
6、00整除，或ai + aj 可被100整除。第三章3.2. 求1到1000中既非完全平方又非完全立方的整数个数。解：设1,2,1000;表示1到1000中完全平方数的集合，则表示1到1000中不是完全平方数的集合；表示1到1000中完全立方数的集合，则表示1到1000中不是完全立方数的集合。故表示1到1000中既非完全平方又非完全立方的整数的集合，由容斥原理（3.5）式）知：(3.5)其中1000，,表示1到1000中既是完全平方又是完全立方的数的集合，故=3,将以上数值代入(3.5)式得1000(31+10)+3=962 故1到1000中既非完全平方又非完全立方的整数个数为962。 3.8.
7、 在所有的n位数中，包含数字3，8，9但不包含数字0，4的数有多少？解：除去0，4，则在1，2，3，5，6，7，8，9这8个数字组成的n位数中，令S表示由这8个数字组成的所有n位数的集合。则|S|=8n.P1表示这样的性质：一个n位数不包含3；P2表示这样的性质：一个n位数不包含8；P3表示这样的性质：一个n位数不包含9；并令Ai表示S中具有性质Pi的元素构成的集合（i=1,2,3）。则表示S中包含3，又包含8，又包含9的所有n位数的集合。由容斥原理（3.5）式）得 |= （3.5）而，代入（3.5）式得 故所求的n位数有个。3.10. 求重集的10-组合数。解：构造集合B=。令集合B的所有1
8、0-组合构成的集合为S。由第一章的重复组合公式(1.11)有F（3，10）=66。令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.5)由于已经求得=66，下面分别计算(3.9)式右端其他的项。由于A1中的每一个10-组合至少含有4个a，故将每一个这样的组合去掉4个a就得到集合B的一个6-组合。反之，如果取B的一个6-组合并加
9、4个a进去，就得到了A1的一个10-组合。于是A1的10-组合数就等于B的6-组合数。故有=F（3，6）28同样的分析可得=F（3，5）21=F（3，4）15用类似的分析方法可分别求得F（3，1）3F（3，0）10（因为561110）0 （同上）将以上数值代人(3.9)式得到：|66（282115）（310）06故所求的10-组合数为6。 3.14. 求由数字1，2，8所组成的全排列中，恰有4个数字在其自然位置上的全排列个数。解：4个数在其自然位置共有种方式，对某一种方式，均有4个数字不在其自然位置，这正好是一个错排，其方式数为（见定理3.2），由乘法规则有，恰有4个数字在其自然位置上的全排列
10、数为630。 第四章4.6 求重集的10-组合数。解：设重集B的n-组合数为，则序列的普通母函数为 =(1-x4-x6-x8+x10+x12+x14-x18)所以a10= =286-84-35-10+1=158故重集B的10组合数为158。4.9. 设重集,并设是满足以下条件的r-组合数，求序列的普通母函数。a. 每个 出现3的倍数次。b. ,至多出现1次，至少出现2次，最多出现4次。c. 出现偶数次，出现奇数次，出现3的倍数次，出现5的倍数次。d. 每个至多出现8次。解：a. b. c. d. 4.10 有两颗骰子，每个骰子六个面上刻有1，2，3，4，5，6个点。问掷骰子后，点数之和为，两颗
11、骰子的点数有多少种搭配方式？解：每个骰子是不同的，但讨论点数之和的时候不考虑顺序，故该问题是组合问题。设有满足条件的搭配方式有种，则其普通母函数为 其中的系数即为所求的搭配方式数。4.14 求由数字2，3，4，5，6，7组成的位数中，3和5都出现偶数次，2和4至少出现一次的位数的个数。解：这是一个排列问题。设满足条件的位数的个数为，则序列对应的指数母函数为： =所以，5.2. 如果用an表示没有两个0相邻的n位三元序列（即由0，1，2组成的序列）的个数。求an所满足的递归关系并解之。 解：对n位三元序列的第一位数有三种选择方式:1)第一位选1，则在剩下的n-1位数中无两个0相邻的个数为an-1
12、;2)第一位选2，则在剩下的n-1位数中无两个0相邻的个数为an-1; 3)第一位选0,则在第二位又有两种选择方式： (1)第二位选1，则在剩下的n-2位数中无两个0相邻的个数为an-2； (2)第二位选2，则在剩下的n-2位数中无两个0相邻的个数为an-2显然有a1=3,a2=8 由加法规则得an所满足的递归关系为：其特征方程为x2-2x-2=0 特征根为x1=1+,x2=1-由定理5.3知其通解为an=c1(1+)n+c2(1-)n由初始条件有 解以上方程组得 ， 5.4. 某人有n元钱，她每天要去菜市场买一次菜，每次买菜的品种很单调，或者买一元钱的蔬菜，或者买两元钱的猪肉，或者买两元钱的
13、鱼。问，她有多少种不同的方式花完这n元钱?解：设花完这n元钱的方式有an种，则第一次花钱可分为下面几种情况： 1)若第一次买一元钱的菜，则花完剩下的n-1元钱就有an-1种方式， 2)若第一次买二元钱的肉，则花完剩下的n-2元钱就有an-2种方式， 3)若第一次买二元钱的鱼，则花完剩下的n-2元钱就有an-2种方式，显然有a1=1，a2=3. 由加法规则,得递归关系如下： 其特征方程为：特征根.通解 .由初始条件得解得.故该递归关系的解为 故她有种不同的方式花完这n元钱。5.6求解下列递归关系a解：这是一个常系数线性非齐次递归关系式，其导出的齐次递归关系为：其特征方程为， 解得 由定理5.3知
14、，所导出的齐次线性递归关系的通解为由于f(n) =3, 且1不是式递归关系式的特征根，故设特解为将代入递归关系得 由定理5.6知，递归关系式的通解为 将初值条件代入上式并解得故 。b解：这也是一个常系数线性非齐次递归关系式，其导出的齐次递归关系的特征方程为特征根为由定理5.3知，所导出的齐次线性递归关系的通解为由于f(n) =3n,且1不是递归关系式的特征根，故设特解为将上式代入递归关系式解得 通解由初始条件有 解得故递归关系的解为： c.解：对应齐次递归关系的特征方程为x2-7x+10=0其特征根x1=5,x2=2 又f(n)=3n, 且3不是递归关系式的特征根，故设特解为，将 代入原递归关系得解得A=通解为
