1 递推关系与母函数 潘海为 智能信息处理研究中心（ RCIIP ）

Presentation on theme: "1 递推关系与母函数 潘海为 智能信息处理研究中心（ RCIIP ）"— Presentation transcript:

1 1 递推关系与母函数 潘海为 http://rciip.hrbeu.edu.cn 智能信息处理研究中心（ RCIIP ）

2 2 特殊计数序列 Catalan 数  Catalan 序列即序列 C 0,C 1,...,C n,...  满足递推关系 C n =C 1 C n-1 +C 2 C n-2 +…+C n-1 C 1 C 1 =1

3 3 特殊计数序列 Catalan 数  递推关系求解得：  组合意义：在一个凸 n 边形中，用不在其内部相交的对角线把 它拆分成若干个三角形，不同的拆分数为 C n

4 4 特殊计数序列 定理： n 个 +1 和 n 个 -1 构成的 2n 项 a 1,a 2,...,a 2n ， 其部分和满足 a 1 +a 2 +...+a k ≥0 (k = 1,2,..., 2n) 的数列的个数等于第 n 个 Catalan 数

5 5 特殊计数序列 例 41 有 2n 个人排成一行进入剧场。入场费 50 美分。 2n 个人中的 n 个人有 50 美分一个的分币， n 个人有一美 元的纸币。剧院售票处相当草率用一个空的现金收银 机开始售票。有多少种列队方法使得只要有 1 美元的 人买票，售票处就有 50 分币找零？

6 6 总结 n 个球 m 个盒是否为空 不同方案数 有区别有区别 不同不同 是 mnmn 否 m!S 2 (n, m) 相同相同 是 S 2 (n,1)+S 2 (n,2)+ … +S 2 (n,r), r=min(n,m) 否 S 2 (n,m) 无区别无区别 不同不同 是 C(n+m-1, n) 否 C(n-1, m-1) 相同相同 是 展开式中 x n 的系数 否

7 7 容斥和鸽巢原理 智能信息处理研究中心（ RCIIP ）

8 8 本讲内容 容斥原理 容斥原理 鸽巢原理 鸽巢原理 Ramsey 定理 Ramsey 定理

9 9 回顾 加法原理 A BC

10 10 问题 例 1 求不超过 20 的正整数中为 2 或 3 的倍数的数  假设 2 的倍数的集合为 A, 则 A={2,4,6,8,10,12,14,16,18,20}, |A|=10  假设 3 的倍数的集合为 B, 则 B={3,6,9,12,15,18}, |B|=6 =10+6 ？  既为 2 又为 3 的倍数的集合为, 则  则所求为 容 斥

11 11 容斥原理 A BC

12 12 容斥原理 — 全或形式 设 A 1,A 2,…,A n 是 n 个有限集合，则 容斥原 理

13 13 容斥原理 — 全非形式 假设在集合 S 上讨论 A 1, A 2, …, A n, |S|=N, 逐步淘汰原理

14 14 容斥原理 — 第三种形式

15 15 容斥原理求解问题步骤 1. 构造有限集合 S = {e 1, e 2, …, e t } 2. 构造性质集合 P = {P 1, P 2, …, P n } 3. 构造集合 A = {A 1, A 2, …, A n } ， A i 是具有性质 P i 的所 有元素组成的子集 问题的关键在于如何构造 P ，使得 |A 1 A 2 … A k | 比较 容易计算，其中 k=1,2,…,n

16 16 容斥原理 例 2 求 a, b, c, d, e, f 六个字母的全排列中，不允许出现 ace 和 df 的排列数 S={a, b, c, d, e, f 的全排列 } P 1 ={ 允许出现 ace}——A 1 P 2 ={ 允许出现 df}——A 2 求

17 17 容斥原理 例 3 求 a, b, c, d 4 位字符构成的 n 位字符串中， a,b,c 至少各出现一次的字符串的数目 例 4 有 3 本高数书， 4 本普通物理书， 5 本数据结构， 求从中取 10 本书的方案数？ 方法一：生成函数法 方法二：容斥原理法 6

18 18 容斥原理 错排问题  定义：对集合 {1,2,3,...,n} 作全排列，但元素 1 不排在第 一位，元素 2 不排在第二位,..., 元素 n 不排在第 n 位，这样 的全排列称为错排。用 D n 表示 例 5 班里有 8 个男生受邀参加章子怡的 party ，他们把自己 的帽子放衣帽间后就急匆匆进去了，突然停电； 他们每一个人再从衣帽间各取一顶帽子，没有人能取到自 己帽子的概率是多少？ D8D8

19 19 容斥原理 例 6 在 8 个字母 A,B,C,D,E,F,G,H 的全排列中，求使 A,C,E,G 不在原位置上的排列数目

20 20 容斥原理 例 7 无继排问题  n 个数字 1,2,...,n 的全排列中，若出现一次 i(i+1) ，则称该排列 中含有一个继排  i(i+1)(i+2) 表示出现两个继排  ……  12…n 出现 n-1 个继排

21 21 容斥原理 例 8 某甲参加一种会，会上有 6 位朋友，某甲  和其中每 1 人在会上相遇 12 次  和其中每 2 人在会上相遇 6 次  和其中每 3 人在会上相遇 4 次  和其中每 4 人在会上相遇 3 次  和其中每 5 人在会上相遇 2 次  和其中每 6 人在会上相遇 1 次  一人未遇到的有 5 次， 问他共参加了多少次会议？

22 22 容斥原理 例 9 求从 [1,500] 的整数中，能够被 3 但不能被 5 和 7 整 除的数的个数

23 23 容斥原理 例 10 求从 [1,500] 的整数中，能够被 3,5,7 中的两个数 整除的数的个数