组合数学作业讲解

1、组 合 数 学,主 讲 教 师: 万 涛,2020/9/15,离散数学,2,习题一,1.2 5个女生，7个男生进行排列。 (a)若女生在一起有多少种不同的排列？ (b)女生两两不相邻有多少种不同的排列？ (c)两男生A和B之间正好有3个女生的排列是多少？ 解： (a)将5个女生看做一个整体。 所求为8！5！ (b)先排7个男生，5个女生选择8个间隔位中不同位置排列。 所求为7！ (c)取3个女生与AB（或BA）构成一个整体， 然后与余下的7人进行排列。 所求为2！ 8！ 或6！2！ 5！,2020/9/15,离散数学,3,习题一,1.8 求1040和2030的公因数数目？ 解： 1040240

2、540 2030260530 1040和2030 的最大公约数为240530 1040和2030 的公因数数目也即240530的因子数 所求为(40+1)(30+1)=1271 1.16 n个完全一样的球放到r个有标志的盒(nr)中，无一空盒， 试求方案数？ 解：所求为,2020/9/15,离散数学,4,习题一,1.22 求从O到P的路径数？ (a)路径必须过A点； (b)路径必须过道路AB； (c)路径必须过A和C； (d)道路AB封锁(但A、B两点开放)。 解：(a)按OA P路径， 所求为 (b)按OAB P路径，所求为 (c)按OA C P路径，所求为 (d)所有路径去除(b)中路径，

3、所求为,2020/9/15,离散数学,5,习题一,1.27 6位男宾，5位女宾围一圆桌而坐， (a)女宾不相邻有多少种方案？ (b)所有女宾在一起有多少种方案？ (c)一女宾A和两位男宾相邻有多少种方案？ 解：(a)先圆排列男宾，然后女宾在间隔位排列 所求为 (b)女宾看做一个整体，所求为 (c)选择两位男宾和女宾A组成一个整体， 所求为,2020/9/15,离散数学,6,习题一,1.38 给出 的组合意义？ 组合意义一： 从a1, a2, , an+1不可重复的取r +1个的组合数为 将上述组合问题分为n-r +1类： (1)含a1的组合数为 (2)不含a1含a2的组合数为 (3)不含a1a

4、2，含a3的组合数为 . . . . . . (n-r)不含a1 a2 . An-r -1含An-r 的组合数为 (n-r +1)不含a1 a2 . An-r含An-r +1的组合数为,2020/9/15,离散数学,7,习题一,1.38 给出 的组合意义？ 组合意义二： 从(0, 0)到(r+1, n-r)的路径数=从(0, 0)经过所有点 (r, i)与 (r+1, i)之间的边的路径数之和(其中0i n-r),2020/9/15,离散数学,8,习题二,2.3 已知母函数 ，求序列an。 解：,2020/9/15,离散数学,9,习题二,2.8 求下列序列的母函数 （1）1，0，1，0，1，0

5、， （2）0，1，0，1，0，1， （3）1，1，1，1，1，1， 解：（1） （2） （3）,2020/9/15,离散数学,10,习题二,2.12已知 ， ，求序列an的母函数 解：令 是序列bn的母函数， 即有 则 由母函数性质3知 序列an的母函数,2020/9/15,离散数学,11,习题二,2.12已知 ， ，求序列an的母函数 另解：序列an的母函数,2020/9/15,离散数学,12,2.54 8台计算机分给3个单位，第1个单位的分配量不超过3台， 第2个单位的分配量不超过4台，第3个单位的分配量不超过5台， 问共有几个分配方案？ 解：,习题二,2020/9/15,离散数学,13,

6、习题三,2.18(a),解:特征方程为 特征根 递推关系通解 （其中 为待定常数）,2020/9/15,离散数学,14,习题三,解:设,则,2.18(a),2020/9/15,离散数学,15,习题三,2.24 设 ，求解递推关系？ 解:特征方程为 ，解得特征根 对应的齐次递推关系通解 而非齐次递推关系的特解为 将其代入 ，得 所以非齐次递推关系的通解为 代入初始值 后，得到方程组 所以递推关系的解为,2020/9/15,离散数学,16,2.27(g),解:特征方程为 ，解得,于是对应的齐次递推关系的通解为,而非齐次递推关系的特解为,将其代入非齐次递推关系得：,即,所以非齐次递推关系的通解为 （

7、A1待定）,习题三,2020/9/15,离散数学,17,2.27(j),解:特征方程为 ，解得,于是对应的齐次递推关系的通解为,将其代入非齐次递推关系得：,所以非齐次递推关系的通解为 （A1,A2待定）,而 的特解为,将其代入非齐次递推关系得：,而 的特解为,习题三,2020/9/15,离散数学,18,2.28 ，利用置换 求解,解：,特征方程为 ，解得,（A1,A2待定）,习题三,2020/9/15,离散数学,19,特征方程为 ，解得,解：,2.38 利用置换 求解 ，,代入初始值可解得,习题三,2020/9/15,离散数学,20,习题三,2.49 求由A, B, C, D组成的允许重复的排

8、列中AB至少出现一次 的排列数目？,解：设可重复的排列中不出现AB的排列数为an，则所求为4n- an 设 为长度为n的可重复排列中不出现AB的排列， 将其分为以下两类： (1) ，则 为长度为n-1的满足条件的排列， 总方案数为 。 (2) ，则 ，于是 为长度为n-1的满足 条件的排列中去掉 的排列(即长度n-2的满足条件排列)， 总方案数为 。,2020/9/15,离散数学,21,习题三,2.49 求由A, B, C, D组成的允许重复的排列中AB至少出现一次 的排列数目？,解： 特征方程为 ，解得特征根 递推关系通解 将其代入 ，得 所以 所求排列数为,2020/9/15,离散数学,2

9、2,习题三,2.49 求由A, B, C, D组成的允许重复的排列中AB至少出现一次 的排列数目？,另解：将an 分类： (1) ，则 为长度为n-1的满足条件的排列， 总方案数为 。 (2) ， ，于是 为长度为n-2的满足 条件的排列，总方案数为 。 (3) ， ，于是 为长度为n-3的 满足条件的排列，总方案数为 。 (4) ， ，于是 为长度 为n-4的满足条件的排列，总方案数为 。 ,2020/9/15,离散数学,23,习题三,2.49 求由A, B, C, D组成的允许重复的排列中AB至少出现一次 的排列数目？,另解：将an 分类： (4) ， ，于是 为长度 为n-4的满足条件的

10、排列，总方案数为 。 (n-1) ， ，于是 为长度为1的 满足条件的排列，总方案数为 。 (n) ，总方案数为3。,2020/9/15,离散数学,24,习题四,3.2 求从1到500的整数中被3和5整除但不被7整除的数的个数？,解：设Ai 表示能被i 整除的数的集合。所求即为| A3A5 |,而： | A3A5 | = | A3A5 | | A3A5A7 |,= 33 4 = 29,= (1 + 3x + x2)(1 + x),3.10 A, B, C三种材料用作产品,的原料，要求禁 止用B和C作原料，不能用B作原料，不允许用A作原料， 问有多少安排方案？（假定每种材料只作一种产品的原料）,

11、= 1 + 4x + 4x2 +x3,所求方案数为3! 4 2! +4 1! 1 0! = 1,2020/9/15,离散数学,25,3.15 N = 1, 2, , 120 ，求其中被2, 3, 5, 7中m个数除尽的数 的数目，m = 0, 1, 2, 3, 4。求不超过120的素数的数目。,解：(0)120，, (0)(0) (1)+ (2) (3)+ (4) = 27, (1)(1) 2(2) +3(3) 4(4) = 53, (2)(2) 3(3) + 6(4) = 32, (3)(3) 4(4) = 8, (4)(4) = 0,2020/9/15,离散数学,26,3.22 求满足条件

12、x1 + x2 + x3 = 20，3 x1 9, 0 x2 8, 7 x3 17的整数解数目。,解：令 y1= x1 3， y2= x2，y3= x3 7,则原问题等价于求y1 + y2 + y3 = 10且y1 6, y2 8, y3 10的 非负整数解数目。,设A1, A2, A3分别表示y1 7,y2 9,y2 11 的非负整数解的集合。,所求即(0)。,求|A1|：令t1= y1 7，则y1 + y2 + y3 = 10且y1 7的非负整数解 等价于t1 + y2 + y3 = 10 7的非负整数解。,同理：, (1) |A1| + |A2| + |A3| = 10 + 3 = 13

13、,2020/9/15,离散数学,27,同理(2) 0，(3) 0,所求(0)= (0) (1) + (2) (3)661353,2020/9/15,离散数学,28,习题五,3.7 在边长为1的等边三角形内任取5点，试证至少有两点 距离小于1/2。,证明：以A表示5个点的集合，|A|= 5。将边长为1的等边三角形 分成4个边长为1/2的小等边三角形，以Ai 表示第i个小三角形的 点的集合，则 。由鸽巢原理必有某个Ai 满足|Ai | 2。 即5个点中必有2个点落在同一个小等边三角形内，他们的距离 小于小等边三角形的边长1/2 。,2020/9/15,离散数学,29,3.65 X = 0, 1,

14、2, , 9, 10 ，从X中任取7个元素， 则其中必有两个元素之和等于10。,证明：将X中的11个元素分成6组：0, 10, 1, 9, 2, 8, 3, 7, 4, 6, 5。由鸽巢原理：从6组中任取7个元素时， 至少存在某一组被同时取到至少两个元素。第6组只有 一个元素，至多能取一次，于是取到至少两个元素的组 为1 5组之一。而1 5组中每组的两个元素之和都等于10， 因此任取的7个元素中必有两个元素之和等于10。,习题五,2020/9/15,离散数学,30,习题六,4.13 对正六边形的6个顶点用5种颜色进行染色，试问有 多少种不同的方案？,解：使正六边形重合的刚体运动群， 有如下几种

15、情况：,第一类置换：不动置换p1= (1)(2)(3)(4)(5)(6) ；,第二类置换：绕O旋转的置换 p2=(123456)，p3=(135)(246)，p4=(14)(25)(36)， p5=(153)(264)，p6=(165432)；,第三类置换：绕对角线翻转的置换 p7= (1)(4)(26)(35)，p8= (2)(5)(13)(46)，p9= (3)(6)(15)(24)；,第四类置换：绕对边中点翻转的置换 p10= (12)(36)(45)，p11= (23)(14)(56)，p12= (16)(25)(34)；,2020/9/15,离散数学,31,以上置换的格式：1个16,

16、 3个1222, 4个23, 2个32, 2个61,4.15 对一个正六面体的8个顶点用y,r两种颜色染色，使 其中有5个顶点用色y，其余3个顶点用色r，求其方案数？, l = (56 + 354 + 4 53 + 2 52 + 2 51)/12 = 1505,解：由书中例4.15知使正六面体重合的运动群的24个置换 格式为：1个18, 6个42, 9个24, 8个1232,其中y 5r 3的系数为,2020/9/15,离散数学,32,第三类置换：绕经过圆环上某珠子的对称轴翻转的置换 p6= (1)(25)(34)，p7= (2)(13)(45)，p8= (3)(15)(24)， p9= (4)(12)(35)，p10= (5)(14)(23)