组合数学作业讲解.ppt

离散数学 第三类置换：绕经过圆环上某珠子的对称轴翻转的置换 p6= (1)(25)(34)，p7= (2)(13)(45)，p8= (3)(15)(24)， p9= (4)(12)(35)，p10= (5)(14)(23)； 以上置换的格式：1个15, 4个51, 5个11 22 [4.16] 用b,r ,g这3种颜色的5 颗珠子镶成的圆环， 共有多少种不同的方案？ ? l = (35 + 4?31 + 5? 33)/10 = 39 解：使圆环重合的运动群有如下几种情况： 1 2 3 4 5 第一类置换：不动置换p1= (1)(2)(3)(4)(5) ； 第二类置换：绕O旋转的置换 p2= (12345)，p3= (13524)，p4= (14253)， p5=(15432)； 离散数学 [2.34] ， ，求 解： 习题三 * 组 合 数 学 主 讲 教 师: 万 涛 离散数学 习题一 [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！ 离散数学 习题一 [1.8] 求1040和2030的公因数数目？ 解： 1040＝240×540 2030＝260×530 1040和2030 的最大公约数为240×530 1040和2030 的公因数数目也即240×530的因子数 所求为(40+1)(30+1)=1271 [1.16] n个完全一样的球放到r个有标志的盒(n≥r)中，无一空盒， 试求方案数？ 解：所求为 离散数学 习题一 [1.22] 求从O到P的路径数？ (a)路径必须过A点； (b)路径必须过道路AB； (c)路径必须过A和C； (d)道路AB封锁(但A、B两点开放)。 解：(a)按O→A →P路径， 所求为 (b)按O→AB →P路径，所求为 (c)按O→A → C →P路径，所求为 (d)所有路径去除(b)中路径，所求为 x y O P A C B 离散数学 习题一 [1.27] 6位男宾，5位女宾围一圆桌而坐， (a)女宾不相邻有多少种方案？ (b)所有女宾在一起有多少种方案？ (c)一女宾A和两位男宾相邻有多少种方案？ 解：(a)先圆排列男宾，然后女宾在间隔位排列 所求为 (b)女宾看做一个整体，所求为 (c)选择两位男宾和女宾A组成一个整体， 所求为 离散数学 习题一 [1.38] 给出 的组合意义？ 组合意义一： 从{a1, a2, … , an+1}不可重复的取r +1个的组合数为 将上述组合问题分为n-r +1类： (1)含a1的组合数为 (2)不含a1含a2的组合数为 (3)不含a1a2，含a3的组合数为 ... ... ... ... ... ... (n-r)不含a1 a2 ... An-r -1含An-r 的组合数为 (n-r +1)不含a1 a2 ... An-r含An-r +1的组合数为 离散数学 习题一 [1.38] 给出 的组合意义？ 组合意义二： 从(0, 0)到(r+1, n-r)的路径数=从(0, 0)经过所有点 (r, i)与 (r+1, i)之间的边的路径数之和(其中0≤i ≤n-r) (r, n-r-1) (r+1, n-r) x y (0, 0) (r, n-r) (r, 0) (r, 1) 离散数学 习题二 [2.3] 已知母函数