Chap3-1容斥原理、棋盘多项式和有限制条件的排列.ppt

计数问题是组合数学研究的重要问题之一 已学过的一些计数方法 如加法法则 母函数方法等 两个重要的计数原理 容斥原理和P lya计数定理 本次课我们先学习容斥原理及其应用 3 1容斥原理 解 2的倍数是 2 4 6 8 10 12 14 16 18 20 共10个 3 1容斥原理 例1求不超过20的正整数中2或3的倍数的个数 否 因为6 12 18在两类中重复计数 应减去 3的倍数是 3 6 9 12 15 18 共6个 答案是10 6 16个吗 故答案是 16 3 13 对于求两个有限集合A和B的并的元素数目 我们有 即具有性质A或B的元素的个数等于具有性质A的元素个数和具有性质B的元素个数减去同时具有性质A和B的元素个数 3 1容斥原理 3 1容斥原理 A B A B U 3 1容斥原理 定理2 3 1容斥原理 A B C A B A B C B C A C U 例2一个学校只有三门课程 数学 物理 化学 已知修这三门课的学生分别有170 130 120人 同时修数学 物理的学生45人 同时修数学 化学的20人 同时修物理化学的22人 同时修三门的3人 假设每个学生至少修一门课 问这学校共有多少学生 3 1容斥原理 解 令A为修数学的学生集合 B为修物理的学生集合 C为修化学的学生集合 即学校学生数为336人 3 1容斥原理 同理可推出 利用数学归纳法可得一般的定理 3 1容斥原理 3 1容斥原理 3 1容斥原理 5 容斥原理指的就是 4 和 5 式 用来计算有限集合的并或交的元素个数 例3求从1到500的整数中能被3或5除尽的数的个数 3 1容斥原理 解 令A为从1到500的整数中被3除尽的数的集合 B为被5除尽的数的集合 被3或5除尽的数的个数为 解 令A B C分别为不出现a b c符号的集合 即有 3 1容斥原理 例4求由a b c d四个字母构成的n位符号串中a b c都至少出现一次的符号串数目 a b c都至少出现一次的n位符号串数目为 3 1容斥原理 例5用26个英文字母作不允许重复的全排列 要求排除dog god gum depth thing字样的出现 求满足这些条件的排列数 3 1容斥原理 解 所有排列中 令 则 出现dog字样的排列 相当于把dog作为一个单元参加排列 故 类似有 由于god dog不可能在一个排列中同时出现 故 3 1容斥原理 由于gum dog可以在dogum中同时出现 故有 类似有 3 1容斥原理 3 1容斥原理 其余多于3个集合的交集都为空集 3 1容斥原理 故满足要求的排列数为 1 再解错排问题 n个元素依次给以标号1 2 n n个元素的全排列中 求每个元素都不在自己原来位置上的排列数 设Ai为元素i在第i位上的全体排列 i 1 2 n 则有 U n 因元素i不能动 因而有 3 2容斥原理 应用 同理 每个元素都不在原来位置的排列数为 3 2容斥原理 应用 3 2 容斥原理 应用 2 1棋盘多项式 n个不同元素的一个全排列可看做n个相同的棋子在n n的棋盘上的一个布局 布局满足同一行 列 中有且仅有一个棋子 x x x x x 排列41352对应于如图所示的布局 3 2 容斥原理 应用 可以把棋盘的形状推广到任意形状 布子规定同上 令rk C 表示k个棋子布到棋盘C上的方案数 3 2 容斥原理 应用 3 2 容斥原理 应用 规定r0 C 1 包括C 时 设Ci是棋盘C的某一指定格子所在的行与列都去掉后所得的棋盘 Ce是仅去掉该格子后的棋盘 在上面定义下 显然有 rk C rk 1 Ci rk Ce 3 2 容斥原理 应用 从而 3 2 容斥原理 应用 例如 3 2 容斥原理 应用 如果C由相互分离的C1 C2组成 即C1的任一格子所在的行和列中都没有C2的格子 则有 R C R C1 R C2 4 故 3 2 容斥原理 应用 利用 和 可以把较复杂的棋盘逐步分解成相对比较简单的棋盘 从而得到其棋盘多项式 3 2 容斥原理 应用 2 2有禁区的排列 例设对于排列P P1P2P3P4 规定P1 P 4 P 2 P4 2 这样的排列对应于有禁区的布子 如左图有影线的格子表示禁区 3 2 容斥原理 应用 定理 设rk为k个棋子布入禁区的方案数 k 1 2 n 则有禁区的布子方案数 即禁区内不布子的方案数 为 3 2 容斥原理 应用 例2 四位工人 A B C D四项任务 条件如下 不干B 不干B C 不干C D 不干D 问有多少种可行方案 3 2 容斥原理 应用 解 由题意 可得如下棋盘 其中有影线的格子表示禁区 方案数 4 6 4 1 10 4 2 4 4 3 0 4 4 4 3 2 容斥原理 应用 例3三论错排问题错排问题对应的是n n的棋盘的主对角线上的格子是禁区的布子问题 R C 则有 故错排问题的解为 欧拉函数是指小于n且与n互素的正整数的个数 设1到n的n个数中pi倍数的集合为 解 若n分解为素数的乘积 3 2 容斥原理 应用 3