《第3章容斥原理和鸽巢原理》由会员分享，可在线阅读，更多相关《第3章容斥原理和鸽巢原理（132页珍藏版）》请在金锄头文库上搜索。
1、第3章 容斥原理和鸽巢原理,2018/9/3,2,例 对1,2,n的排列 计数，其中 。解 直接计数：(1) ：有 个；(n-1) :有 个；共有 个 间接计数： ：有 个所以共有 个,容斥原理,2018/9/3,3,例 计算1到600中不能被6整除的整数个数。证 能被6整除的整数个数为所求数的个数为一般，若 ，则 或,容斥原理,2018/9/3,4,作为上述法则的第一个推广：令S是一个有限集合，P1, P2是S中每个的元素可能具有的两个性质。 ， 分别表示S中具有性质P1， P2的元素的集合，那么有更一般地，设P1, P2，Pn是S中每个的元素可能具有的n个性质。令Ai(i=1,2,n)是S
2、中具有性质Pi的元素的集合，则有,容斥原理,2018/9/3,5,定理3.2 证 任取S中的一个元素a，(1) 若a不具有这n个性质中的任何一个，则a对方程左端的贡献为1，而对方程右端的贡献为,容斥原理,2018/9/3,6,(2) 若a具有这n个性质中的m个，则a对方程左端的贡献为0，而对方程右端的贡献为,容斥原理,2018/9/3,7,推论 证,容斥原理,2018/9/3,8,例3.2 一个学校只有三门课程：数学、物理、化学。已知修这三门课的学生分别有170、130、120人；同时修数学、物理两门课的学生45人；同时修数学、化学的20人；同时修物理、化学的22人；同时修三门课的学生3人，问
3、这学校共有多少人？解 设M为修数学课学生的集合P为修物理课学生的集合C为修化学课学生的集合,容斥原理,2018/9/3,9,由题意知，所求人数为,容斥原理,2018/9/3,10,例3.3 求a,b,c,d,e,f 六个字母的全排列中不允许出现 ace 和 df 图象的排列数。解 A1为出现ace图象的排列的集合，A2为出现df图象的排列的集合，那么有所求排列数为,容斥原理,2018/9/3,11,例3.4 N=1,2,500，求N中能被2，3，5整除的数的个数。解 设 分别为被2、3、5整除的数的集合。那么有,容斥原理,2018/9/3,12,容斥原理,2018/9/3,13,例3.5 求由
4、a, b, c, d四个字符构成的n位符号串中，a, b, c至少出现一次的符号串的数目。证 设 分别表示不出现a, b, c的n位符号串的集合。则,容斥原理,2018/9/3,14,另解：设 为所求的n位符号串数目，则an的指数型母函数为,容斥原理,2018/9/3,15,例3.6 求不超过120的素数的个数。 解 若一个正整数n是一个合数，那么n必能被某个素数 整除。由112=121知，不超过120的合数必能被2,3,5,7之一整除。设 为不超过120,但被i整除的数的集合, i=2,3,5,7,容斥原理,2018/9/3,16,容斥原理,2018/9/3,17,所求素数个数为：27+4-
5、1=30。,容斥原理,2018/9/3,18,例3.7 用26个英文字母作不允许重复的全排列，要求排除dog, god, gum, depth, thing字样的出现，求满足这些条件的排列数。解 设A1为出现dog的排列的集合；A2为出现god的 排列的集合；A3为出现gum的排列的集合；A4为出现depth的排列的集合；A5为出现thing的排列的集合。,容斥原理,2018/9/3,19,所求的排列数为,容斥原理,2018/9/3,20,例3.8 求完全由n个布尔变量确定的布尔函数的个数。解 设n个布尔变量为 ，自变量可能的取值有 个，n个布尔变量的布尔函数有 个。 设 是 一个布尔函数，
6、不依赖于变量 是指对于每一都有,容斥原理,2018/9/3,21,不依赖于某个布尔变量的布尔函数有 个。不依赖于k个布尔变量的布尔函数有 个。设 为不依赖于布尔变量xi的函数的集合，那么所求函数的个数为当n=2时,容斥原理,2018/9/3,22,例3.9 欧拉函数 表示不大于n，且与n互素的正整数的个数。设 ， 表示从1到n中能被 整除的数的集合，那么有,容斥原理,2018/9/3,23,容斥原理,2018/9/3,24,例,容斥原理,2018/9/3,25,例3.10 错排问题设 表示i在第i位排列的集合，则有，,容斥原理,2018/9/3,26,例2.66 在8个字母A,B,C,D,E,
7、F,G,H的全排列中，求使A,C,E,G四个字母不在原来位置上的排列的数目。解 设A1,A2,A3,A4分别表示A,C,E,G在原来位置上排列的集合。所求数目为,容斥原理,2018/9/3,27,习题,3.1 3.2 3.16 3.62,2018/9/3,28,例3.11 在4个x，3个y，2个z的全排列中，求不出现xxxx、yyy、zz图象的排列数。解 设 分别为出现 xxxx、 yyy、 zz图象的全排列的集合。则,有限制的排列,2018/9/3,29,所有全排列的个数为：,有限制的排列,2018/9/3,30,n个元素的一个排列 可以看作是n个棋子在 的棋盘上的一种布局，每行每列有且仅有
8、一个棋子，其中 是棋盘第 i 行棋子所在的列数例如 排列3 1 4 2所对应的棋盘布局如下图所示,棋盘多项式,2018/9/3,31,可以把棋盘C推广到任意形状。令 表示k只棋子布到棋盘C的不同的方案数，规则是当一个棋子置于棋盘的某一格子时，则这一格子所在的行和列都不能再布任何棋子。,棋盘多项式,2018/9/3,32,对于给定的棋盘C，称下列多项式为棋盘C的棋盘多项式，其中n为棋盘C的格子数，并定义 。例如对右图所示的棋盘，其棋盘多项式为,棋盘多项式,2018/9/3,33,在棋盘C上选定一个格子，将 分为两类：(1)该格子放置棋子：有 种放法；(2)该格子不放置棋子:有 种放法.故有其中
9、表示从棋盘C中删除所选定格子所在的行和列后所得到的棋盘，而 表示从棋盘C中删除所选定格子后所得到的棋盘。,棋盘多项式,2018/9/3,34,由上述关系得,棋盘多项式,2018/9/3,35,棋盘多项式,2018/9/3,36,棋盘多项式,2018/9/3,37,棋盘多项式,2018/9/3,38,若棋盘是由两个部分棋盘C1和C2组成，其没有C1中的格子与C2中的格子在同一行或同一列中，那么有这时有,棋盘多项式,2018/9/3,39,棋盘多项式,2018/9/3,40,有禁区的排列,例 考虑1，2，3，4的排列， 要求 不能为3，不能为1和4， 不能为2和4， 不能为2。,2018/9/3,
10、41,定理3.3 有禁区的排列数为其中 是有 个棋子布置到禁区部分的方案数。证 设Ai(i=1,2,n)为第i行的棋子落在禁区内的方案数，那么有,有禁区的排列,2018/9/3,42,有禁区的排列,例3.12 有G,L,W,Y 4位工作人员，A,B,C,D为四项任务，但G不能从事任务B；L不能从事任务B，C；W不能从事任务C，D；Y不能从事任务D。若要求每人从事各自力所能及的一项工作，试问有多少种不同的方案？解,G L W Y C D B A,2018/9/3,43,有禁区的排列,图中禁区的棋盘多项式为所求的方案数为,2018/9/3,44,例3.13 错排问题。错排的个数为,有禁区的排列,2
11、018/9/3,45,有禁区的排列,例3.14 设4种材料A,B,C,D拟分配去做1,2,3,4这4种产品。若A不宜于1的产品；B不宜于3,4的产品；C不宜于1,3的产品；D不宜于4的产品。试问有多少种分配方案，使每种产品有一种其适宜的材料。,A B C D 2 1 4 3,2018/9/3,46,有禁区的排列,2018/9/3,47,有禁区的排列,所求分配方案数为,2018/9/3,48,广义容斥原理,设P1, P2，Pn是S中每个的元素可能具有的n个性质。令Ai(i=1,2,n)是S中具有性质Pi的元素的集合.记,2018/9/3,49,广义容斥原理,2018/9/3,50,广义容斥原理,
12、定理 3.4,2018/9/3,51,证 任取一个元素a。若a有少于m个性质，那么a对方程的左端和右端的贡献都为0。若a恰有m个性质，那么a对方程的左端和右端的贡献都为1。若a恰有 个性质，那么a对等式的左端贡献为0，而对等式的右端的贡献为,广义容斥原理,2018/9/3,52,广义容斥原理,2018/9/3,53,例3.15 某学校有12位教师，已知教数学、物理、化学课教师分别有8位，6位，5位，其中有5位既教数学又教物理，有4位兼教数学和化学，兼教物理和化学的有3位；有3位教师教3门课，试问教数、理、化以外课的教师有几位？只教一门课的教师有几位？正好教两门课的教师有几位？解 设A1, A2 , A3分别表示教数学、物理、化学课教师的集合。则,广义容斥原理,2018/9/3,54,广义容斥原理,教数、理、化以外课的教师的人数为 只教一门课的教师的人数为 正好教两门课的教师的人数为,2018/9/3,55,问题：求满足线性方程的非负整数解的数目。上述方程的非负整数解与 r 个无区别的球放进n个有标志的盒子 方案一一对应。故上述方程非负解的个数为,若干应用,2018/9/3,56,考虑下列问题：求方程的整数解的数目。若无上界条件，方程 非负整数解的数目为,
