排列与合.ppt

组合数学 钱 江 jqian104@ 北邮理学院 定义：从 n 个不同的数中不重复的取出取出 r 个沿一圆周排列，称为一个圆周排列。 所有的r-圆周排列数记为 Q(n,r)。 注意圆周排列与排列的不同之处在于圆周排列首尾相邻。 如a、b、c、d的4种不同排列 abcd, dabc, cdab, bcda, 在圆周排列中都是一个排列。 4. 圆周排列 1 2 4 3 1234 1 2 4 3 2341 1 2 4 3 3412 1 2 4 3 4123 以4个元素为例 Q(n,r)=P(n,r)/r , 2≤r≤n Q(n,n)=(n-1)! 从 n 个中取 r 个的圆周排列的排列数为： 若无要求，则为Q(8,8)； 若要求蓝色珠子一起，则为Q(6,6)×P(3,3)； 若要求蓝色珠子不相邻，则为Q(5,5)×5×4×3。 例20 5颗红珠子，3颗蓝珠子装在圆板的四周，试问有多少种方案？若要求蓝色珠子不相邻，又有多少种排列方案？蓝色珠子在一起呢？ 例21 5对夫妇出席一个宴会，围一圆桌坐下，试问 有几种不同的坐法？要求每对夫妇相邻又如何？ 若无限制，则为Q(10,10)； 若要求相邻，则为Q(5,5)×2×2×2×2×2。 选取的 r 个元素叫做 S 的一个r-(可重)排列。当 时也叫做 S 的一个排列。 定义：从一个多重集 中有序 5. 可重排列 定义：多重集是指元素可以多次出现的集合，即元素可以重复。我们把某个元素 ai 出现的次数ni(ni=0,1,2,…)叫做该元素的重复数。 通常把含有 k 种不同元素的多重集 S 记作 定理：设多重集 则 S 的r-(可重)排列数是 kr。 推论：设多重集 且对一切的 i=1,2,…k，有ni≥r，则 S 的r-(可重)排列数是 kr。 所求的标志数是多重集{2红旗，3黄旗}的排列 数，故 N=5!/(2!×3!)=10。 例23 用两面红旗，三面黄旗依次悬挂在一根旗杆上，问可以组成多少种不同的标志? 例22 求不多于4位数的二进制数的个数。 设 则 S 的 r-排列数 N 满足： (1) 若r n, 则 N = 0; (2) 若r = n, 则 N = (3) 若r n ,且对所有的i, , 则 (4) 若r n ,且存在i, nir, 则对 N 没有一般的求解公式，具体解法以后再说。 定理：从 中取 r 个作可重的组合，其个数为C(k+r-1,r)。 6. 可重组合 r个相同的球 /\ ———————　———————— ／　　　　　　　　　　　　　 　　 \ 0…010…01…10…0 \ / ———— ———— 　　　　　 \/ 　 k-1个相同的盒壁 而后一问题又可转换为 r 个相同的球与 k-1 个相同 的盒壁的排列的问题。 则所求计数为 C(k+r-1,r)。 这个计数问题相当于 r 个相同的球放入 k 个不同的盒子里，个数没有限制的计数。 * * 组合数学就是按照一定的规则来安排一些离散个体的有关问题。其内容包括： 1、计数与枚举 2、容斥原理和鸽巢原理 3、组合设计 4、组合算法和组合优化 5、图论 排列、组合、母函数、递推关系、容斥原理、Burnside引理、Polya定理 第一章 排列与组合 1.1 排列与组合 1.2 排列组合的生成算法 1.3 组合意义的解释与应用举例 1.1 排列与组合 加法法则和乘法法则 一一对应 排列、组合 圆周排列 可重排列 可重组合 不相邻的组合