ch5-容斥原理

Chapter 5 容斥原理及其应用 §1. 容斥原理 一. 引言 1. 例1：求{1,2, ……,n}的1不在首位的全排列的个数。 解: (1) 直接计数：按首元分类 (2) 间接计数 例2：求在1、2、……、600中不能被6整除的数的 个数. 2. 归纳： A S A A A S  － ，即 3. 例3：蝙蝠的故事 例4：求[1，20]中为2或3的倍数的数的个数. 解：2的倍数是：2，4，6，8，10，12，14，16， 18，20，共10个； 3的倍数是：3，6，9，12，15， 18，共 6个； 答案 八年级地理上册填图题岩土工程勘察试题省略号的作用及举例应急救援安全知识车间5s试题及答案 为10+6=16个？ 因为6，12，18在两类中重复计数，应减去。 故答案是：16-3=13 否！ 4. 此即： A B S A B A B     (1) A B A B A B   (2) A B C A B C A B A C B C A B C     - A B C S A B C A B A C B C A B C         + 注： (1) 文氏图 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示 (2) 可将A,B,C看作集合S中分别具有性质a,b,c的元所 构成的子集合 (3) 基本思路：将“反交”用所有“正交”表示出来 二. 容斥原理 1 1 1. , , {1, , } { , , } . n k X i i X S A A S n n n X i i A A A S       记号： 为有限集； 为 的 个子集； ； 若 ，则 ；记 1 2 | | | | 1 2 | | 0 | | 1 | | 2 | | 1 2 1 1 2. 1 | | ( 1) | | ( 1) | | | | | | | | ( 1) | | | | | | | | 1 | | n n X X n X X X n X n X X X X X X n n n i i j n i i j n A A A S A A A A A S A A A S A A A A A A                                定理 ：设 ， ， ， 为有限集 的n个子集，则 － （－） | | 1 1 2 | | 1 1 1 2 1 1 | | ( 1) | | | | | | | | n X n X X n n i i j n i i j n A A A A A A A A A A                 此即： （－1） 注： (1) 前式“反交”：即为S中所有不具有性质pi的元 的个数 (2) 后式“正并”：即为S中至少具有一条性质pi 的元的个数 (3) 意义：如果任若干个“正面交”的个数好求， 则“反面交”的个数也好求 Proof: 1 , ( ) 0 ( ) ( ) ( ), ( ) 1 ( ) A A B A B a A a A S A f a a A f a f a f b f a f A a         定义 上的特征函数： 则有： 设 1 2 1 2 1 2 1 2 1 2 1 1 1 1 , ( ) ( ) ( ) ( ) ( ) (1 ( ))(1 ( )) (1 ( )) 1 ( ) ( ) 1 ( ) ( ) ( ) ( ) 1 ( ) ( ) ( 1) ( ) n n n i i j n i i j n i j n A A A A A A A A A n A A A i A A A n n A A A A A n A i ni j a S L a f a f a f a f a f f f f f f a f a f a f a a a a a a f a a ff a                                     （－） 对 1 2 1 2 1 1 2 1 1 1 ( ) [1 ( ) ( ) ( 1) ( ) | | | | | | | | 1 | ] | i i j n a S n n A A A A A n i j n n n i i j n i A a S i i j n A A A f S A A A A A A L a f a a f a                                  左 （－） 右 从而: 3. 解决问题的实际步骤: (1). 按照题目意思构造集合S (2). 构造S中的n个子集(将题中所要求的条件反过来) (3). 确定诸集合AX，并求出其基数|AX| (4). 代入容斥原理公式，并计算化简 例2： 九个字母M, A, T, H, I, S, F, U, N排列，使得单 词MATH, IS, FUN均不发生的排列数为多少？ 例3： 求在1和1000之间不能被5，6，8整除的数的个数。 例1：某校只有三门数理化课程。已知修这三门课的学 生分别有170、130、120人；同时修数理的45人；同 时修数化的20人；同时修理化的22人；同时修三门的3 人。问这学校共有多少学生？ 三. 实例 §2. 原理应用(一) 一. 应用之一：欧拉函数 1. 简单注释： 素数=质数；因子=约数；素因子=质约数 1 2 1 2 1 2. , ,k rr r k k n n p p p p p n 记号：设整数 有如下唯一素因子分解式： ，其中 为 的全部不同的素因子， ( ) ( ) .n n n n   问题： 记 为 中与 互素的数的个数,求 表达式 1 3. , , k m m n m p p 分析：对任正整数 ， 与 互素 不是 中的任一个的倍数 注：将一个条件化为若干个条件 1, , k m n m n p p m 与 不互素 与 有非平凡的公因子 中某一个是 的因数 4. 解答步骤： (1). 取S={1,2,…,n} (3). {1 }, X i i X n X k A p      对 ， ， 求出 (2). 取S的k个子集如下： 1 { | } 1,..., ( ) | | . i i k A m S m p i k n A A     是 的倍数， ，则可知 | | X i X i i Xi X X i i X A a a p A n A A p           数 为 的倍数 | | 1 | | 1 (4). ( ) | | ( 1) | | ( 1) ( ) 1 ( ). 1 1 X k X X k X X k i k i i i X n A A A n n p p                    | | 1 1 2 ) (1 ) ( ) 1 1 ( ( )) (1 )(1 1 (1 ) ( 1) ( ) k k i X k i X X k i X Xi X X ki ii i a aa a p p p                       附： 二. 应用之二：重复组合数 1. 原引理： 1 1 1 k i i i x x n n r k x r k               带限制条件(下限)的不定方程： ， (这里 )的整数解的个数为 1{ , , }k i i a a n i a r  注：此即 中取 个元素，使得第个元 至少取 个的取法数 2. 现问题： 1 . k i i x x n x r N      求带限制条件(上限)的不定方程： ， (这里 )的非负整数解的个数 3. 解答： (1)“去限”得S：{x1+…+xk=n的非负整数解} (2)“反限”得Ai：{x1+…+xk=n,且xi≥ri的整数解} (3) {1 }, XX k A 对 ，， 求出 1 | 1 | 1 i i X X k i i Xx x n x r i rn k A k                 即不定方程： ，(这里 ， ) 其整数解的个数为: 1 1 2 24. { , , , }k kS n a n a n a r    思考：多重集 的 组合数 是多少呢？ (4) 利用容斥原理求得N | | 1 | | | | ( 1) | | ( 1) 1 1i i X X k X X k X X k r N A A k A n k                       5. 例题： 1 2 3 4 1 2 3 4 18 1 5 2 4 0 5 3 9. x x x x N x x x x        例1：求方程 ＋ ＋ ＋ ＝ 的整数解的个数 ， 其中 ，－ ， ， 1 1 2 2 3 3 4 41 2 3y x y x y x y x解：(1) 令 ＝ －， ＝ ＋ ， ＝ ， ＝ －， 1 2 3 4 1 2 3 4 16 0 4 0 6 0 5 0 6. y y y y y y y y        (2) 将问题转化为 ＋ ＋ ＋ ＝ ， 其中 ， ， ， (3) 利用容斥原理求得N. 1 2 3 4{4 ,6 ,5 ,6 } 16 . T a a a a N     例2：求多重集 的 -组合数 (1)“去限”得S：重复度无限制时的16-组合数 (2)“反限”得Ai (3) 利用容斥原理求得N 解： 另解：此即求T的5-组合数N. 1: 5 ( 0,1, ,4)N i a i 将 分类 含有个 的 组合 4 4 0 0 3 2 7 7 5 3 1 7 2 2 1 2 2 1 7 1 5 1 2 5 i i j j i i j N j                                                §3 原理应用(二) 一. 应用之三：错排问题 1. {1,2, , } “ ”. n n j j n   定义：集合 的一个全排列中， 元 素均不在它的自然位置第 位上，则此全排列称为 阶 全错位排列 (2)又称n阶更列数，记为Dn 1 2 32. 0, 1, 2D D D  例： 1 2 n ki i i i k 注：(1)此即 ，满足 0 3. 1 ( 1) 1 1 1 1 ! !(1 ( 1) ). ! 1! 2! 3! ! in n n i n n D n n i n          定理：对 ，全体 阶更列个数为 ＝ Proof , !S n S n  ：(1)构造 为 的全体排列所成集合 则 1 { | }, | | . i i n k S A S i D A A      (2)构造 的子集 则 (3) , XX n A  对 求出 ( | |)!XA n X  (4) 利用容斥原理求出Dn | | 1 | | |0| | 0 0 |0 | | ( 1) | | ( 1) | | ( 1) ( )! ( 1) ( )! ( 1) ! ! X n X X n X i X n n n i i n X i X i i i i n i D A A A A n i n i n i n i                                0 ( 1) (1) ! ! in n i D n i  注： 更列的概率为： (2)概率的极限为e-1 1 11 1 1(3) ! ! ( 1)! 1 2 n n D e n e D n n n          故而Dn是与n!e -1最接近的整数 二. 例题 例1. P69: 数1，2，…，9的全排列中，求偶数在原 来位置上，其余都不在原来位置的排列个数。 解：实际上是1，3，5，7，9五个数的错排问题， 总数为： 5 1 1 1 1 1 5!(1 ) 44 1! 2! 3! 4! 5! D        例2. n男n女参加舞会，第一支舞曲n女选n男作舞伴 的方案数为多少？第二支舞曲每人必须更换舞伴的方 案数为多少？ 例3. 设有编号为1，2，3，4，5的五个球和编号为1， 2，3，4，5的五个盒子，现将这五个球投放入五个盒 内，要求每个盒内投放一个球，并且恰好有两个球的编 号与盒子的编号相同，求这样的投放方法总数. 例4. 某省决定对所辖8个城市的党政一把手进行任职交 流，要求把每个干部都调到另一个城市去担任相应的职 务．问共有多少种不同的干部调配方案？ 三. 错排的递推公式 2 11. ( 1)( )n n nD n D D   递推关系之一： 1 2 1 -2 0 0 12 2 0 0 2 1 0 ( 1) ( 1) ( 1)! ( 2)! ! ! ( 1) ( 1) ( 1) ( 1)![ ] ( 2)! ! ( 1)! ! ( 1) ( 2)! ( 1) ! i in n n n i i i n in n i i in n i D D n n i i n n i n i n n i                                       ＝Proof1： 2 1 ( 1)( )n n nn D D D   故而： 2| | | | ( 1) | |i j nDB B n B     Proof2：将所有错排按照首元i分为(n-1)类,记为Bi 2 1 ( 1)( )n n nn D D D   故而： 3 4 2 2 3 2 3 4 ,2,1, , , , , , 2, , , , ,, ,2 n n n i i i B i i i i i i i    又 中的元 即 2 B 1,3,4 ,n问题一： 是否是 ， 的错排？ | | | | ?i jBB 问题二：为什么 12. ( 1) n n nD nD   递推关系之二： Proof: 利用前递推关系之一 ! ( 1)[( 2)! ( 1)!] 3 ! ( 1)!, 2 n n n n n n n n n           ， 注：类比于 2 1 1 2 2 3 2 1 1 2 2 2 ( 1)( ) ) ( 1) )( ( 1) ( ( 2) ( 1) ( 2 ) ( 1) n n n n n n n n n n n D nD D n D D n D D n D D D D                             四. 错排与积和式的关系 1 2 1 2 1 2 ( ) ( ) ( ) 1. ( ) m m n ij i i mi i i i S m n m A a pe a S rA n m n m erA a ap        ， 这里 是指集合 的所有 元 矩阵 的 无重复 积 排 和式 列 定义为： 的集合. (1) perA注： 积和式 即一些“积之和式” (2)此即A中所有可能的m个两两不共线元素的乘 积之和 1 2 1 2 1 2 ( ) n n n i i ni i i i S aam n r ape A    （3） 时，即 ( ). 2. 1n n n n nper n n D J E J E n   结论：若 是元素全为 的 阶方阵， 为 阶单位阵， 则 阶更列数 1 2 1 2 1 2 ( ) Pr B 0 1 B )( n n n n n ij n i i ni i i i S b b b oof perB J E perB b         ：记 = 的 ， 则 中任 展开式中每一项亦均为 或 何一部分元素之积必为0或1. 此和式中的非零项个数 1 2 1 21 2 1 2 1 2 1 2 0 1, 2, , ( ) n ni i ni i i ni n n b n b i i i n i i i n b b b b       ， ， 均不在个因子 ， 排列 是一个 对角 上又 线， 阶更列 n perB B n D   故， 的积和式展开式中非零项个数 阶更列数 二. 应用之四： 有限制条件的排列计数 1. 引例：有8位同学排成一队出去散步，第二天时均不 希望前面同学与昨日相同，求排法数。 分析：问题可转化为求第二天不出现12，23，…， 78这些模式的排列的个数 注：此为对元素间相邻关系的限制，而非对位置的 限制 2. {1,2, , } 12 23 ( 1) nQ n n n n    记号： 表示在 中不出现 “顺向相邻对”,即 ， ， ， 这些模式的 全排列的个数. 1 0 1 1 3. ( 1) ( )! 1 1 1 ! ( 1)! ( 2)! ( 1) 1! 1 2 1 n i n i n n Q n i i n n n n n n n                                       定理： 1 2 31, 1, 3Q Q Q  例： Proof: (2) 取Ai为出现顺向邻对i(i+1)的全排列的集合， 这里i=1,2,…,n-1 (3) 1 , | | XX n X k A    对 设 ，求出 ① 设X中对应的k个邻对造成r个连团如下： 1 1 2 21 2 1 1 2 1 1 2 1 , , , r rm m m m m m a a a b b ba z z zb z   1 2 rm m m k     (1) 取S为的所有全排列的集合 (4) 利用容斥原理求Qn ② AX中总团数=单团数+连团数 ③ 从而|AX|=这些团的全排列=(n-k)!=(n-|X|)! 1 2 1 2 1) 1) 1 ( [ ( ( ( )] )( r r n r n m m m n m k r m m n                     总团数 所有连团中已出现元） 1 0 1 1 0 | | | | 1 | 0 | | | ( 1) | | ( 1) | | ( 1) ( )! ( 1) )! 1 ( X X X X X n X i n n i n n i X i i i i n Q A A n i n i i                                 14. n n n n nQ D Q D D－与 的关系： ＝ ＋ 2 n nn Q D 注：由此知： 时， ；故错位排列限制更严格. 1 0 0 1 1 1 1 Pr ( 1) ( )! ( 1) ( )! 1 1 ( 1) [ ]( )!= ( 1) [ ]( )! 1 1 ( 1) n n i i n n i i n n i i i i i n n oof Q D n i n i i i n n n n i n i i i i n i                                                          ： 1 1 1 0 [( 1) ( 1)]! 1 1 = ( 1) ( 1 )! n i n t n t n i n n t D t                        §3 应用之五─有禁区的排列问题 一. 问题引入 1. 定义：(错排推广) 1 2 1 2 1 2 ( , , , ) { , 1,2, , }, , , , n n j j n S n P X X X i i i S i X j n X X X n           为 的全排列的集合，定义 | 这里 为 的子集. 1 2 1 2( , , , ) | ( , , , )n nP X X X p X X X注：(1) 记| (2) 特别，Xj={j}时即为原错排问题 (3) Xj可视为第j个位置的“禁区” 1 2 3 4 1 2 4, {1,2}, {2,3}, {3,4}, {4,1}, ( , , , ).n n X X X X p X X X     2. 例1： 求 3. 棋盘与排列的关系： (1) n n n n 一般： 元全排列 个棋子在 棋盘上的布局： 要求每行每列只有一个棋子 1 2 1 2(1, ),(2, ), , ( , )n ni i i n i i n i此即： 放 个棋子在 ( , )i j i j注： 点在盘中即位置处放元素(行：位置，列：元素) 1 2(2) ( , ) 1,2, , ni i i n j j j n   有限制： 错排 放 个棋的布局， 使得棋子不能放在 处， 1 2(3) ( , , , )nP X X X 有禁区： 布棋中某些棋子 不能放在某些位置上(禁区) (4)例1的对应棋盘： 二. 有禁区的排列数： 1 2 0 ( 1) ( )! ! 1 ! 2 ! ( 1) , n i n i n i i n n n N r n i n r n r n r r i              1.定理： 个相同的棋子放到有禁区的 盘上的排列数为： （ ） （ ） 其中 为 个棋子落在禁区内的方案数。 Proof: (2) 设Ai为S的子集，满足第i行的棋子落在禁区内， 即落在Xi所含列中 | | (3) | | X X k X n X k A      对 ，设 ，求 X | | ( )!X X k k nA r k    这里rk表示k个棋子落在禁区的方案数 (1) S表示无禁区时的所有全排列所成集合 2. 问题：如何求rk? (4) 用容斥原理求N | | | | 0 | 1 0 | ( 1) | | ( 1) | | ( 1) ( )! n X X X X X n X i i i n i i N A A r n i                 三. 棋盘多项式 ( ) :kr C k C 1.定义1：布棋方案数 将 个相同的棋子放到 棋盘 上的不同方案数 注： (1) C可以任意形状 (2) 布棋仍按规定，每行每列只有一个棋 (3) 将C看作禁区，此即前面定理中的rk (4) 规定r0(c)=1 2. 例如（括号中的图象便是棋盘的形状） r1( )=1， r1( )=2， r1( )=2， r2( )=0， r2( )=1， r2( )=2 3. 性质： (1) r1(C)=C中方格数 (2) 若k＞C中方格数，则rk(C)=0 (3) 若C1经旋转或翻转变为C2，布棋方案数不变 1 (4) ( ) ( ) ( ) i l k k i k l C C C C r C r C r C－ 令 为 中删去某格所在行列后所剩棋盘， 为 中去掉该格后所剩棋盘，则布棋方案数 ＝ 注：由此知约定r0(C)=1是合理的 (特取k=1) 1 2 1 2 0 (5) ( ) ( ) ( ) k k i k i i C C r C r C r C  若 与 的行列均不重叠，则 ＝ Proof:将k个棋子布局在棋盘C上可分为k+1类 1 2 ( 0 ,, )1,i i C k i C i k 第类：个棋子在 中， 个在 中， 1 2 1 2 0 ( ) ( ) ( ) ( ) ( ) i k i k k i k i i i r C r C r C r C r C       第 类的布局数为 ＝ 0 4. ( ) ( ) kk k R C r C x   棋盘多项式： 注: (1) 最多只有n项，这里n为棋盘C的总格数 (1) ( ) ( ) ( )i lR C xR C R C  (2) 此多项式常数项是什么？一次项系数呢？ 1 2(2) ( ) ( ) ( )R C R C R C 5.性质： 6. 例如： R( )=1+2x； R( )=1+ x； R( )= x R( ) + R( ) = x(1 + x )+1 + x =1+ 2x +x2 四. 实例 0 0 ( 1) 1 ! = ( 1) ( )! ! in n i n i i n D n n i ii          例：错排问题： ＝ 解：求禁区的棋盘多项式得ri，再代公式 0 ( 1) ) (( )n n n i i i x n R C R x n r i i                   0 0 0 ( 1) ( 1) ( )! ( 1) ( )! ! ! in n n i n i i i i i n D r n i n i n i i                 ＝ 例2：有5名乘客甲乙丙丁戊要去5个地方京津沪浙闽旅 游，其中甲不愿去京闵，乙不愿去津沪，丙不愿去沪 浙，戊不愿去闵，问有多少种让每人都满意的旅游方 案？ 京 津 沪 浙 闵 甲 乙 丙 丁 戊 京 闵 津 沪 浙 甲 戊 丁 乙 丙 2 2 1 2) 1 4 3 (B ) 1+3 , (R x x R B x x    解： 2 2 2 3 4 ( ) (1+3 ) 1 4 3 13 3 ( ) 1 7 16 x xR C x x x x x x          1 2 3 4 57, 16, 13, 3, 0r r r r r      0 ( 1) (5 )! 5 4! 16 3! 13 2! 3 1! 0 25 ! 7 0! n i i iN r i                  带入容斥原理公式，得