Microsoft PowerPoint - 第09讲容斥原理.ppt

Size: px

Start display at page:

Download "Microsoft PowerPoint - 第09讲容斥原理.ppt"

螺段
7 years ago
Views:

1 应用组合数学第 9 讲容斥原理张坤龙 zhagl@tu.edu.c

2 目录集合 N 个属性容斥原理求具有个属性之一并集的元素的个数求不具有个属性中任何一个交集的元素的个数广义容斥原理求恰好具有个属性的元素的个数

3 容斥原理并集的计数交集的计数容斥原理的应用有禁区的排列

4 两个集合的并集 [ 定理 ] BB- B U B B [ 例 ] 求不超过 0 的正整数中或的倍数的个数解 : 令为的倍数集合 B 为的倍数集合 0 / 0 } B 0 / 6 BB- B B 0 / 6

5 三个集合的并集 [ 定理 ] B B - B- -B B U B B B B [ 例 ] 一个学校只有三门课程 : 数学物理化学已知修这三门课的学生分别有人 ; 同时修数学物理两门课的学生 4 人 ; 同时修数学化学的 0 人 ; 同时修物理化学的人同时修三门课程的人问这学校共有多少学生假设每个学生至少修一门课? 解 :M P

6 多个集合的并集证明 : 数学归纳法 U U U ] [ > > > 是有限集合则设定理

7 De Moga 定理 [ 定理 4] 若 B 是 U 的子集则 U U B B B B [ 定理 ] 若是 U 的子集则 U U U U U U

8 Sylveste 公式 6] [ N N > > > 则和具有性质的集合给定集合定理

9 有限制的排列 [ 例 ] 求 abcdef 六个字母的全排列中不允许出现 ace 和 df 图象的排列数解 : 设为 ace 作为一个元素出现的排列集 B 为 df 作为一个元素出现的排列集则 N6! 4! 6!! 4!! 8 B! B B!

10 [ 例 4] 4 个 x 个 y 个 z 的全排列中求不出现 xxxx yyy zz 图象的排列数解 : 所有出现 xxxx 图象的排列集合记为出现 yyy 图象的排列集合记为出现 zz 图象的排列集合记为则 N P9;4 [ P6; P7;4 P8;4] [ P4; P; P6;4]- P;

11 Eatosthees 筛法 [ 例 ] 求不超过 0 的素数的个数解 : 不超过 0 的合数必然是 7 的倍数且不超过 0 的合数的因子不可能都超过设为不超过 0 的数的倍数集 N

12 由于 7 是素数不是素数故所求的不超过 0 的素数个数为 :74-0

13 欧拉函数 φ 6] [ h h p p p p p p p p p p p p p p p p p p p > > > φ φ φ 则的倍数的集合之间为到证明 : 设则有是小于等于且与互素的正整数的个数假设欧拉函数例

14 错排问题 - 容斥原理 [ 例 7] 求整数的全排列中所有都不在第个位置上的排列的个数解 : 设表示在第个位置上的所有排列则所求的排列数为 : D N!!!!! - -!! -!

15 有禁区的排列 [ 例 8] 对于整数 4 的全排列 PP P P P 4 规定 P P 4 P 4 P 4 4 P P P P 4 问题可以转换为在有禁区的棋盘上放置车使得每行每列有且只有一只车

16 棋盘多项式将若干只车放置在一个 x 的棋盘 B 上要求每行每列有且只有一个车记 B 表示棋盘 B 上放置只车的不同方案数则称多项式 R B B x 0 B B x B x 0 为棋盘 B 的棋盘多项式由于在 x 的棋盘 B 上最多可以放置只车因此当 > 时 B0 棋盘多项式 RB 只有有限项

17 有禁区的布局在棋盘 B 上放置车时有的位置是禁区下面画棋盘时省略了禁区部分 0 ; 0 0; R x R x 0 ;R xx

18 棋盘多项式的递推关系 * B B B e B - B B e ; RBxRB RB e R xr R x xx * * R xr R xxxxx

19 R * xr R xxxxx * R xr R 4xx * R xr R x6x x * R xr R 6x0x 4x

20 有禁区的布局数 [ 定理 7] 在 x 的棋盘上放置只车不同的方案数为其中是有只车布置到禁区部分的方案数证明 : 令表示第只车放入第行的禁区则 - - ±!!! N ± ±!! -!

21 任务分配 [ 例 9] G W Y 四位工人 B D 四项任务若 G 不能从事任务 B 不能从事任务 B W 不能从事任务 DY 不能从事任务 D 则有多少种可行方案使得每人从事各自力所能及的一项工作? 解 : 每一种分配方案相当于右图所示的有禁区的排列由于 R 6x0x 4x G W Y B D 所求的排列数为 : 4!-6*!0*!-4*!-04

22 错排问题 - 有禁区的排列 [ 例 0] 如图所示可求得禁区的棋盘多项式为 x 4 4 则错排的方案数为!--!-!- ±

23 广义容斥原理广义容斥原理广义容斥原理的应用多重集的 - 组合对夫妻问题

24 次个性质的元素计数了具有则令和性质给定集合 N N > > > 0

25 β 0 0 ; ] [ 0 0 N N β β β ± ± 推论 : 个性质的元素被计数的总次数是于是具有次根据恒等式中计算个则在项的元素假设是个性质个性质的元素 ; 多于恰有个性质的元素证明 : 少于个性质的元素个数则中恰有表示令和性质给定集合广义容斥原理

26 广义容斥原理 - 例题 [ 例 ] 某校有个教师已知教数学的有 8 位教物理的有 6 位教化学的位 ; 教数理的位教数化的 4 位教理化的位 ; 教数理化的位问教其他课的有几位? 只教一门课的有几位? 只教两门课的有几位? 解 : 令教数学的教师属于教物理的属于教化学的属于则 β β β- -

27 广义容斥原理 - 例题 [ 例 ] 求从 O 点到 P 点恰好经过 BDEFGH 中任何两条路径的路径数 y P0 B D E F H G O00 x

28 解 : 令表示从 O 点到 P 点经过 B 的路径表示从 O 点到 P 点经过 D 的路径表示从 O 点到 P 点经过 EF 的路径 4 表示从 O 点到 P 点经过 GH 的路径则 β

29 广义容斥原理 - 例题证明 : 等式左边是 -- 即从 { } 中取出个数其中必定包含 {...} 的方案数等式右边第一项是从 { } 中取出个数的方案数命表示选取的个数中不包含 ± 0 [ 例 ] 证明恒等式

30 线性方程的整数解数目 [ 例 4] 求满足线性方程 x x x x 0 x 0 x 0 的整数解的数目解 : 这个方程的任意一个整数解都可以看作是个无区别的球放进个有标志的盒子每盒个数不限因此解的个数为 - 6

31 线性方程的整数解数目 [ 例 ] 求满足线性方程 x x x x 6 x 0 x 0 的整数解的数目解 : 可以用换元法求解命 y x -6 y x y x 则问题变为求满足线性方程 y y y 9 y 0 y 0 y 0 的整数解的数目即 9

32 线性方程的整数解数目 [ 例 6] 求满足线性方程 x x x 0 x x 0 x 0 的整数解的数目解 : 令 N 为线性方程的全体非负整数解为其中 x 6 的解则 0N6 9 β

33 多重集的 - 组合 [ 例 7] 给定多重集 { x6 y7 z} 求从中取个元素的组合数解 : 令 N 为从 {xyz} 选出个元素的全体可重复组合为 N 中至少 6 个 x 的组合为 N 中至少 7 个 y 的组合为 N 中至少 8 个 z 的组合则 β 这个问题实际上也就是求满足线性方程 :x x x 0 x 0 x 6 0 x 7 的整数解的数目

34 S 的计算公式 S S N!! > > > 个有区别的盒子无一空盒的方案数为注意到个有标志的球放进个有区别的盒子无一空盒的方案数为因此个有标志的球放进表示第个盒子为空的事件则个有区别的盒子令个有标志的球放进 β

35 错排问题的推广 < < < t t t t t t t a D D a a a a N N t t 0 0 0!!!!! } { 9] [ β β 注意这里性质的个数是个所求为计数因此对有个数未错排的排列的排列则表示所有满足证明 : 令时有来表示则当个数是错排这样的排列数用即有个数满足要求其中有中取个进行排列得从定理

36 不相邻的组合不相邻的组合是指从 { } 中取个其中不存在两个相邻的数同时出现于一个组合中的组合例如不能出现 {} [ 定理 0] 从 { } 中取个作不相邻的组合其组合数为 - 证明 : 从 { } 中取个作不相邻的组合与从 { -} 中取个作组合一一对应 b b b b b b -b - b -

37 不相邻的组合 [ 定理 ] 假定数个顶点沿一圆周排列则从其中选取个不相邻顶点的方法数是 / --- 证明 : 对于任意一个顶点先取然后再从不和相邻的 - 个其他顶点中取 - 个不相邻顶点显然可得到符合定理要求的组合这种组合的个数为注意到一共有个顶点而且在每个组合中有个元素即可完成证明

38 对夫妻问题 [ 例 8] 有对夫妻围一圆桌而坐则有多少种方案使男女交错而又避免夫妻相邻? 解 : 先让位妻子围桌而坐每两个人之间留一个空位并按顺时针给予到的编号然后让丈夫找空位坐下令性质 : 丈夫坐在妻子的右边 : 丈夫坐在妻子的左边 : 丈夫坐在妻子的右边妻子 4 : 丈夫坐在妻子的左边妻子 : 丈夫坐在妻子的右边 : 丈夫坐在妻子的左边显然和不能同时成立注意

39 < < < < < < < 0 0!! 0!! 0 0 β β 最终由广义容斥原理可得时当时有因此当

求出所有的正整数 n 使得 20n + 2 能整除 2003n n 20n n n 20n n 求所有的正整数对 (x, y), 满足 x y = y x y (x, y) x y = y x y. (x, y) x y =

求出所有的正整数 n 使得 20n + 2 能整除 2003n + 2002 n 20n + 2 2003n + 2002 n 20n + 2 2003n + 2002 求所有的正整数对 (x, y), 满足 x y = y x y (x, y) x y = y x y. (x, y) x y = y x y 对于任意正整数 n, 记 n 的所有正约数组成的集合为 S n 证明 : S n 中至多有一半元素的个位数为

Microsoft PowerPoint - 第09讲 容斥原理.ppt

Microsoft PowerPoint - 第09讲容斥原理.ppt