南开大学ACM暑期集训之 组合数学 朱毅 2006年8月.

Presentation on theme: "南开大学ACM暑期集训之 组合数学 朱毅 2006年8月."— Presentation transcript:

1 南开大学ACM暑期集训之 组合数学 朱毅 2006年8月

2 主要参考文献 《组合数学》讲义 任课教师：黄连生 清华大学计算机系

3 内容提要 排列组合 鸽巢原理 递推关系与生成函数 二分图的最大匹配 Polya计数原理的相关数学基础

4 排列组合

5 圆排列 6位女士和6位先生围着一张圆桌聚餐，要求安排女士和先生交替就座。问：有多少可能的安排方案。
解. 由于要求安排女士和先生交替就座，因此可以先安排六位女士坐下，两位之间留出一个空位，然后再安排先生就座。安排六位女士坐下（圆排列）的方案数是 （种）

6 圆排列（续） 由于已经有女士在位，安排先生在六个空位上就座时，就不再是圆排列了，因为原先被看成相同圆排列的六位先生的就座方式所产生的全体人员的圆排列是不同的。故安排先生在六个空位上就座的方案数是 6！＝720 于是我们得到满足要求安排方案共计有

7 全排列生成算法 如果将整数n从『1，2。。。，n』的一个排列中删除，那么结果则是『1，2。。。，n-1』的一个排列。
算法描述： 从『1』开始，将2插入排列中得『1，2』的排列，以此类推，直至得到『1，2。。。，n』的排列

8 『1，2，3』全排列生成算法示例 1 2 2 1 ＝＝＝＝＝＝＝＝＝ 1 2 3 1 3 2 3 1 2 －－－－－－－－－－ 2 1 3
1 2 2 1 ＝＝＝＝＝＝＝＝＝ －－－－－－－－－－

9 STL中生成排列数的函数 #include <algorithm> int A[] = {2, 3, 4, 5, 6, 1};
prev_permutation(A, A+6); 结果：2　3　4　5　1　6 next_permutation(A, A+6); 结果：2　3　4　6　1　5

10 相关练习 NKOJ 1038 NKOJ 1108

11 鸽巢原理

12 鸽巢原理之一 鸽巢原理是组合数学中最简单也是最基本 的原理，也叫抽屉原理。即 “若有n个鸽子巢，n+1个鸽子，则至少有
　鸽巢原理之一 鸽巢原理是组合数学中最简单也是最基本 的原理，也叫抽屉原理。即 “若有n个鸽子巢，n+1个鸽子，则至少有 一个巢内有至少有两个鸽子。” 例１　367人中至少有２人的生日相同。 例２　10双手套中任取11只，其中至少有 两只是完整配对的。 例３　参加一会议的人中至少有２人认识 的别的参加者的人数相等。

13 鸽巢原理之二 鸽巢原理二 m1 , m2 , … , mn都是正整数， 并有m1 + m2 +… +mn－n + 1个鸽子住进n个
　鸽巢原理之二 鸽巢原理二　m1 , m2 , … , mn都是正整数， 并有m1 + m2 +… +mn－n + 1个鸽子住进n个 鸽巢，则至少对某个 i 有第 i 个巢中至少有 mi个鸽子，i = 1 , 2 , … , n． 上一小节的鸽巢原理一是这一原理的特殊 情况，即m1 = m2 = … = mn= 2， 　 m1 + m2 +… +mn－n + 1 = n + 1 如若不然，则对任一 i， 都有第 i 个巢中的 鸽子数≤mi－1　则

14 鸽巢原理之二 鸽子总数≤ m1 + m2 +… +mn－n ， 与假设相矛盾． 推论１ m只鸽子进n个巢，至少有一个巢 里有「－ |只鸽子．
　鸽巢原理之二 鸽子总数≤ m1 + m2 +… +mn－n ， 与假设相矛盾． 推论１　m只鸽子进n个巢，至少有一个巢 里有「－ |只鸽子． m n 推论２　n(m－1) + 1只鸽子进n个巢，至少 有一个巢内至少有m只鸽子． 推论３　若m1 , m2 , … , mn是正整数，且 > r－1,则 m1,… , mn至少有一个 不小于r m1 + … +mn n

15 递归关系和生成函数

16 母函数 定义：对于序列 构造一函数： 称函数G(x)是序列 的母函数

17 递推关系 利用递推关系进行计数这个方法在算法分析中经常用到，举例说明如下： 例一.Hanoi问题：这是个组合数学中的著名问题。N个圆盘依其半径大小，从下而上套在A柱上，如下图示。每次只允许取一个移到柱B或C上，而且不允许大盘放在小盘上方。若要求把柱A上的n个盘移到C柱上请设计一种方法来，并估计要移动几个盘次。现在只有A、B、C三根柱子可用。

18 递推关系 Hanoi问题是个典型的问题，第一步要设计算法，进而估计它的复杂性，集估计工作量。 算法： N=2时
第二步把下面的一个圆盘移到C上                       第一步先把最上面的一个圆盘套在B上 最后把B上的圆盘移到C上                       到此转移完毕 A B C

19 递推关系 对于一般n个圆盘的问题， 先把上面的n-1个圆盘经过C转移到B。 第二步把A下面一个圆盘移到C上
最后再把B上的n-1个圆盘经过A转移到C上 A B C

20 递推关系 上述算法是递归的运用。n=2时已给出算法；n=3时，第一步便利用算法把上面两个盘移到B上，第二步再把第三个圆盘转移到柱C上；最后把柱B上两个圆盘转移到柱C上。N=4，5，…以此类推。

21 递推关系 算法分析：令h(n)表示n个圆盘所需要的转移盘次。根据算法先把前面n-1个盘子转移到B上；然后把第n个盘子转到C上；最后再一次将B上的n-1个盘子转移到C上。 n=2时，算法是对的，因此，n=3是算法是对的。以此类推。于是有

22 递推关系 算法复杂度为： H(x)是序列 的母函数。给定了序列，对应的母函数也确定了。反过来也一样，求得了母函数，对应的序列也就可得而知了。当然，利用递推关系(2-2-1)式也可以依次求得 ，这样的连锁反应关系，叫做递推关系。

23 递推关系 下面介绍如何从(2-2-1)式求得母函数H(x)的一种形式算法。所谓形式算法说的是假定这些幂级数在作四则运算时，一如有限项的代数式一样。

24 递推关系 根据(2-2-1)， 或利用递推关系(2-2-1)有

25 递推关系 上式左端为： 右端第一项为： 右端第二项为：

26 递推关系 整理得 这两种做法得到的结果是一样的。即：

27 递推关系 如何从母函数得到序列 ？下面介绍一种化为部分分数的算法。 令

28 递推关系 由上式可得： 即：

29 递推关系 因为：

30 递推关系 例2. 求n位十进制数中出现偶数个5的数的个数。
先从分析n位十进制数出现偶数个5的数的结构入手 是n-1位十进制数，若含有偶数个5，则 取5以外的0，1，2，3，4，6，7，8，9九个数中的一个，若 只有奇数个5，则取 ，使 成为出现偶数个5的十进制数。

31 递推关系 解法1： 令 位十进制数中出现偶数个5的数的个数，  位十进制数中出现奇数个5的数 的个数。 故有：

32 递推关系 (2-2-2)式中的 表达了含有偶数个5的n位十进制数的两个组成部分。  表达由含有偶数个5的n-1位十进制数  ，令 取5以外的0，1，2，3，4，6，7，8，9九个数中的一个数构成的。 项表示当 是含有奇数个5的n-1位十进制数，令 而得 是含偶数个5的n位十进制数。 也有类似解释。

33 递推关系 (2-2-2)是关于序列 和 的连立关系。 设序列 的母函数为 ，序列 的母函数为 。 即：

34 递推关系 承前页：

35 递推关系 又： 故得关于母函数 和 得连立方程组：

36 递推关系

37 递推关系

38 递推关系 解法二： n-1位的十进制数的全体共 从中去掉含有偶数个5的数，余下的便是n-1位中含有奇数个5的数。故有：

39 递推关系 令

40 递推关系

41 母函数和递推关系应用举例 例6：设有n条封闭的曲线，两两相交于两点，任意三条封闭曲线不相交于一点。求这样的n条曲线把平面分割成几个部分？
曲线所分割成的域的数目为 ，其中 条封闭曲线 所分割成的域的数目为 图

42 母函数和递推关系应用举例 第n条封闭曲线和这些曲线相交于 个点，这 个点把第n条封闭曲线截成
条弧，每条弧把 个域中的每个域一分为二。故新增加的域数为 利用递推关系 得

43 母函数和递推关系应用举例 设

44 母函数和递推关系应用举例 另解：利用欧拉公式 点数+域数-边数=2 点数= ， 边数= 点数 域数=

45 相关练习 NKOJ NKOJ 1052

46 二分图的最大匹配

47 相关概念 二分图是这样一种图：图被分成两个顶点集M和N，在同一个集合中的顶点不存在边，只有不在同一集合的顶点之间才存在边，
二分图匹配是指求出一组边，其中顶点分别在两个集合中，并且没有两个边有相同的依附顶点，也就是说一个顶点最多只属于一条边。 最大匹配就是找出这样的最大边数的一组边。

48 二分图及其最大匹配示意

49 二分图最大匹配算法（匈牙利算法） 令g=（x,*,y）是一个二分图，其中x={x1,x2...},y={y1,y2,....}.令m为g中的任意匹配。 1。将x的所有不与m的边关联的顶点表上￥，并称所有的顶点为未扫描的。转到2。 2。如果在上一步没有新的标记加到x的顶点上，则停，否则 ，转3 3。当存在x被标记但未被扫描的顶点时，选择一个被标记但未被扫描的x的顶点，比如xi，用（xi）标 记y 的所有顶点，这些顶点被不属于m且尚未标记的边连到xi。  现在顶点xi 是被扫描的。如果不存在被标记但未被扫描的顶点，转4。 4。如果在步骤3没有新的标记被标记到y的顶点上，则停，否则转5。 5。当存在y被标记但未被扫描的顶点时。选择y的一个被标记但未被扫描的顶点，比如yj， 用（yj）标记x的顶点，这些顶点被属于m且尚未标记的边连到yj。现在，顶点yj是被扫描的。 如果不存在被标记但未被扫描的顶点则转道2。 由于每一个顶点最多被标记一次且由于每一个顶点最多被扫描一次，本匹配算法在有限步内终止。

50 相关练习 NKOJ NKOJ

51 Polya计数原理的相关数学基础

52 群的概念 (1)群 定义 给定集合G和G上的二元运算 · ，满足下列条件称为群。 (a)封闭性：若a,b∈G,则存在c∈G,使得a·b=c.
(b)结合律成立：任意a,b,c∈G,有(a·b)·c=a·(b·c). (c)有单位元：存在e∈G,任意a∈G.a·e=e·a=a. (d)有逆元：任意a∈G,存在b∈G, a·b=b·a=e. b=a. 由于结合律成立，(a·b)·c=a·(b·c)可记做a·b·c. 例 证明对于a1,a2,…,an的乘积，结合律成立 a·a·…·a=a (共n个a相乘). -1 n

53 群的概念 (2) 简单例子 例 G={1,-1}在普通乘法下是群。 例 G={0,1,2,…,n-1}在mod n的加法下是群.
例 二维欧氏空间所有刚体旋转T={Ta}构成群。其中Ta = cosa sina -sina cosa TbTa= cosb sinb cosa sina -sinb cosb -sina cosa

54 群的概念 = cosacosb-sinasinb sinacosb+cosasinb
-sinacosb-cosasinb cosacosb-sinasinb = cos(a+b) sin(a+b) =Ta+b -sin(a+b) cos(a+b) 从而有(a)封闭性; (b)结合律成立：(TαTβ)Tγ = Tα(TβTγ) = TαTβTγ ; (c)有单位元： T0 = ; (d)有逆元：Ta =T-a = cosa -sina sina cosa 1 0 0 1

55 群的概念 前两例群元素的个数是有限的，所以是有限群；后一例群元素的个数是无限的，所以是无限群。 有限群G的元素个数叫做群的阶,记做|G|。
若群G的任意二元素a,b恒满足ab=ba。责称G为交换群，或Abel群。 设G是群,H是G的子集,若H在G原有的运算之下也是一个群,则称为G的一个子群。

56 群的概念 基本性质 单位元唯一 e1e2=e2=e1 消去律成立 ab=ac → b=c, ba=ca → b=c
每个元的逆元唯一 aa =a a = e, ab = ba = e , aa = ab , a = b (d)(ab….c) =c …b a . c …b a ab…c = e -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1

57 群的概念 (e) G有限，a∈G，则存在最小正整数r，使得a = e.且a = a .
证 设|G|=g,则a,a ,…,a ,a ∈G,由鸽巢原理其中必有相同项。设a =a ,1≤m＜l≤g+1, e=a ,1≤l-m≤g，令l-m=r.则有a =a a=e.即a =a .既然有正整数r使得a =e,其中必有最小者，不妨仍设为r. r称为a的阶。易见 H={a,a ,…a ,a =e}在原有运算下也是一个群。 r -1 r-1 g g+1 2 m l l-m r r-1 -1 r-1 r 2 r-1 r

58 置换群 置换群是最重要的有限群，所有的有限群都可以用之表示。
置换：[1,n]到自身的1-1变换。n阶置换。[1,n]目标集。( ), a1a2…an是[1,n]中元的一个排列。n阶置换共有n!个，同一置换用这样的表示可有n!个表示法。例如 p1=( )=( )，n阶置换又可看作[1,n]上的一元运算，一元函数。 1 2 … n a1 a2 … an

59 置换群 置换乘法 P1=( ),P2=( ) P1P2=( )( )=( ) 注意：既然先做P1的置换，再做P2的置换就规定了若作为运算符或函数符应是后置的。这与一般习惯的前置不一样。 一般而言，对[1,n]上的n阶置换，i[1,n]要写成(i)P1P2，而不是P1P2(i). (i)P有时写成i 在上面例中，1→3→2,2→1→4,3→2→3,4→4→1.也可写(1)P1P2=2,(2)P1P2=4,(3)P1P2=3,(4)P1P2=1. P2P1=( )( )=(　　 )≠P1P2. P2 P1 P2 P1 P2 P1 P2 P1

60 置换群 (1)置换群 [1,n]上的所有n阶置换在上面的乘法定义下是一个群。 (a)封闭性 ( )( )=( ) (b)可结合性 (( )( ))( ) =( )=( )(( )( )) (c) 有单位元 e=( ) (d) ( ) =( ) a1 a2 … an b1 b2 … bn 1 2 … n b1 b2 … bn 1 2 … n a1 a2 … an a1 a2 … an b1 b2 … bn 1 2 … n a1 a2 … an b1 b2 … bn c1 c2 … cn 1 2 … n a1 a2 … an a1 a2 … an b1 b2 … bn 1 2 … n c1 c2 … cn b1 b2 … bn c1 c2 … cn 1 2 … n -1 1 2 … n a1 a2 … an a1 a2 … an 1 2 … n

61 置换群 1 (2)例 等边三角形的运动群。 绕中心转动120，不动， 绕对称轴翻转。 P1=( ),P2=( ),P3=( ),P4=( ), P5=( ),P6=( )。 [1,n]上的所有置换(共n!个)构成一个群，称为对称群，记做Sn. 注意：一般说[1,n]上的一个置换群，不一定是指Sn.但一定是Sn的某一个子群。 1 2 3 1 2 3 2 3 1 1 2 3 3 1 2 1 2 3 1 3 2 1 2 3 3 2 1 1 2 3 2 1 3

62 Polya计数原理 参见清华大学相关学习资料（在公共邮箱中） 相关练习： 1135: Let it Bead

63 组合数学相关练习 1038: Lotto 1046: 正整数划分问题 1052: 圆的重叠问题
1060: Tian Ji -- The Horse Racing 1070: 信与信封问题 1108: Binomial Showdown 1135: Let it Bead