组合数学ch4.ppt

主要内容 §4.1 容斥原理 §4.2 多重集的r-组合数 §4.3 错位排列 §4.4 有限制条件的排列问题 §4.5 有禁区的排列问题 §4.6 M?bius反演 可以写成 或者 |A1 A2|=? 1000/[ 5,6] ?= ? 1000/30 ?=33 |A1 A3|=? 1000/[ 5,8] ?= ? 1000/40 ?=25 |A2 A3|=? 1000/[ 6,8] ?= ? 1000/24 ?=41 | A1 A2 A3|=? 1000/[ 5,6,8] ?= ? 1000/120 ?=8 根据定理4.1.1得 证明：（贡献法，思想） 等式左边是S中不具有性质P1, P2,…，Pm的元素数。我们将要证明，对S中的任何一个元素x, 如果x不具有性质P1, P2,…，Pm，则对等式右边的贡献为1；如果x至少具有其中的一条性质，则对等式右边的贡献为0。 设x不具有性质P1, P2,…，Pm，所以x Ai, i=1,2 …,m.令T={1,2, …,m}.对T的所有的2-组合{i,j}都有x Ai Aj,对T的所有的3-组合{i,j,k}都有x Ai Aj Ak ， …，直到 x A1 A1 … Am ,但x S,所以它对等式右边 的贡献是1-0+0-0+…+(-1)m0=1. 设x具有n条性质，n=1.则x对|S|的贡献为1， 对 的贡献为n= ,对 的贡 献为 ，对 的贡献为 所以x对等式右边的总贡献是： 证明结束。 例４.1.3 对50辆汽车做氧化氮（NOx）、碳氢化合物（HC）和一氧化碳（CO）的污染物排放量的测试。其中，1辆汽车的排放量超过所有三种污染物的环境标准，3辆汽车NOx和HC超标，2辆汽车NOx和CO超标，1辆汽车HC和CO超标，6辆汽车NOx超标，4辆汽车HC超标，3辆汽车CO超标，计算有多少辆汽车符合所有三种污染物的环境标准？ 对称筛公式 例４.1.6 将20个学生分成不同的3个组，每组至少有1个学生，求有多少种分法？ 3, 引入如下的记号： 则定理4.1.1的公式可写成： 定理4.1.2（Jordan公式） 集合 S中恰具有r(0≤r ≤m)种性质的事物的个数 （广义包含排斥原理） 例４.1.5 对50辆汽车做氧化氮（NOx）、碳氢化合物（HC）和一氧化碳（CO）的污染物排放量的测试。其中，1辆汽车的排放量超过所有三种污染物的环境标准，3辆汽车NOx和HC超标，2辆汽车NOx和CO超标，1辆汽车HC和CO超标，6辆汽车NOx超标，4辆汽车HC超标，3辆汽车CO超标，求有多少辆汽车正好超出1种污染物的环境标准？ 解 即我们要求的是N(1). 容易计算：W(1)=6+4+3=13，W(2)=3+2+1=6，W(3)=1, 则根据定理4.1.2有 =13-2×6+3×1=4.因此，有4辆汽车正好超出1种污染物的环境标准。 由定理4.1.1得： 例4.2.1 确定多重集S={3·a,4·b,5·c}的10-组合数。 解：令T= {∞·a,∞ ·b，∞ ·c} ,T的所有10-组合构成集合W,根据定理3.3.3得： 任取T的一个10-组合， 如果其中的a多于3个，则称它具有性质P1; 如果其中的b多于4个，则称它具有性质P2; 如果其中的c多于5个，则称它具有性质P3， 因此S的10-组合数就是W中同时不具有性质P1,P2和P3的元素个数，即W中同时满足a的个数小于等于3，b的个数小于等于4， 并且c的个数小于等于5的10-组合个数。 令Ai={ x|x?W并且x具有性质Pi} A1中的每个10-组合至少含有4个a, 把4个a 拿走就得到T的一个6-组合。反之，对T的 任意一个6-组合加上4个a就得到A1的一个 10-组合，所以|A1|就是T的6-组合数，即 同理可得： 用类似的方法可以计算 所以S的10-组合数为 列出这6个10-组合如下： {1·a,4·b,5·c}， {2·a,3·b,5·c}， {2·a,4·b,4·c} {3·a,2·b,5·c}， {3·a,3·b,4·c}， {3·a,4·b,3·c