第二章排列与组合.PDF

第二章排列与组合 集合的排列和组合 多重集排列 北航计算机学院：李建欣 Tel （G506） E-mail：lijx@ /lijx 主要内容 组合？  集合的循环排列  集合的组合 排列 排列  多重集的排列 普通集排  应用例子 线性排列 列 多重集排 循环排列 列 回顾 加法原理： 设集合S划分为S , S ,…, S 。则： 1 2 m |S|=|S |+|S |+…+|S | 1 2 m 乘法原理 设S是P和Q的乘积（即S ＝P ×Q ），则 |S|＝|P|×|Q| 集合的线性排列 排列计数 70 C1 25 60 60 55 C3 C2 45 50 40 C4 C 5 80 120 多少所有可能不同的巡回路径？ 几个热身问题？  10个人排成一列，其中2个人不愿彼此相邻， 有多少种排法？ 解法：共P(10,10)种,减去有5个（？）位置相 P(10,10)-2*9*P(8,8) 邻，两次先后位置换2 ，P(10,10)-5x2xP(8,8) 1 2 3 4 9 10  10个人围坐一个圆桌，其中2个人不愿彼此 挨着就座，问有多少种座位摆放