组合数学(西安电子科技大学(第二版第四章容斥原理.ppt

《组合数学(西安电子科技大学(第二版第四章容斥原理.ppt》由会员分享，可在线阅读，更多相关《组合数学(西安电子科技大学(第二版第四章容斥原理.ppt（54页珍藏版）》请在装配图网上搜索。

1、第4章 容斥原理,引言 容斥原理 应用 限制排列与棋盘多项式 莫比乌斯反演公式,4.1 引言,例 在一根长的木棍上有两种刻度线，第一种刻度线将木棍分成10等份，第二种将木棍分成12等份。如果沿每条刻度线将木棍锯断，木棍总共被锯成多少段？,4.1 引言,例 在一根长的木棍上有三种刻度线，第一种刻度线将木棍分成10等份，第二种将木棍分成12等份，第三种将木棍分成15等份。如果沿每条刻度线将木棍锯断，木棍总共被锯成多少段？,4.1 引言,4.1 引言,4.1 引言,4.2 容斥原理,4.2 容斥原理,4.2 容斥原理,4.2 容斥原理,4.2 容斥原理,4.2 容斥原理,4.2 容斥原理,4.2 容

2、斥原理,4.2 容斥原理,4.3 应用,例 1与1000之间不能被4,5和6整除的整数有多少个？,解: 令A=1,2,3,1000，则 |A|=1000. 记A1、A2、A3分别为在1与1000之间能被4,5和6整除的整数 集合，则有： |A1| = L1000/4=250, |A2| = L1000/5=200, |A3| = L1000/6=166,4.3 应用,于是A1A2 表示A中能被4和5整除的数,即能被20整除的数，其个数为 |A1A2|=L1000/20=50； 同理, |A1A3|=L1000/12=83, |A2A3|=L1000/30=33,4.3 应用,A1 A2 A3

3、表示A中能同时被4,5,6整除的数，即A中能被4,5,6的最小公倍数lcm(4,5,6)=60整除的数，其个数为 | A1A2A3|=L1000/60= 16. 由容斥原理知，A中不能被4,5,6整除的整数个数为:,4.3 应用,例 六一儿童节快到了，有爱心巧手妈妈做了3个布娃娃、4个小布熊、5个布兔子共12个布玩具，现选10个送给某儿童福利院，如果忽略同类玩具的差异那么有多少种选送方法？,此问题相当于求S=3a,4b,5c的10-组合数.,4.3 应用,例 求S=3a,4b,5c的10-组合数.,解: 令S=a, b,c，则S的10-组合数为,设集合A是S的10-组合全体，则|A|66，现在

4、要求在10 组合中的a的个数小于等于3，b的个数小于等于4，c的个 数小于等于5的组合数. 定义性质集合P=P1,P2,P3,其中： P1：10组合中a的个数大于等于4； P2：10组合中b的个数大于等于5； P3：10组合中c的个数大于等于6. 将满足性质Pi的10-组合全体记为Ai(1i3).,4.3 应用,那么，A1中的元素可以看作是由S的1046组合再拼上4个a构成的，所以,同理，,类似地，,而a的个数小于等于3，b的个数小于等于4，c的个数小于等于5的10-组合全体为 由容斥原理知，它的元素个数为:,4.3 应用,例 确定在非负整数x1,x2,x3,x4不大于7时，方程x1+x2+x

5、3+x4=10的整数解的个数。,解 设S为该方程的整数解的非负整数解集合，|S|=286,令Pi是性质xi=8(i=1,2,3,4),并令Ai为S中具有性质Pi的集合，问题变为求,A1是方程x1+x2+x3+x4=10(x1=8,x2=0,x3=0,x3=0)的整数解集合。,类似地，,而Ai(i=1,2,3,4)的任意两个以及两个以上的交集均为空集，故,4.3 应用,4.3 应用,例 在一次聚会上有n为男士和n位女士。这n位女士能够有多少种方法选择男舞伴？如果每个人必须换舞伴，那么第二次跳舞又有多少种选择方法？,4.3 应用,证明：令S是1,2,n的全排列的全体，则|S|n!. 定义S上的性质

6、集合P=P1,P2,P3,.,Pn,其中Pi表示排列中i在其自然顺序的位置上(1in).令Ai为S中满足性质Pi的全排列的集合.,因Ai中的每一个全排列形如 j1ji-1iji+1jn， 而j1ji-1ji+1jn是1,2,i-1,i+1,n的全排列，所以有 |Ai|=(n-1)! (1in). 同理，有|AiAj|=(n-2)! (1ijn). 一般地，有 |Ai1Ai2Aik|=(n-k)!， 其中1i1,i2,ikn,且i1,i2,ik互不相等.,4.3 应用,而Dn为S中不满足性质Pi的元素的个数，由容斥原理，有,4.3 应用,例 确定1,2,3,4,5,6,7,8的没有偶数在它的自然

7、位置上的排列数。,例 确定1,2,n的恰有k个整数在它们的自然位置上的排列数。,4.3 应用,4.3 应用,4.3 应用,4.3 应用,4.3 应用,4.3 应用,4.3 应用,4.3 应用,4.4 限制排列与棋盘多项式,4.4 限制排列与棋盘多项式,4.4 限制排列与棋盘多项式,4.4 限制排列与棋盘多项式,例 8个小孩围坐在旋转木马上，问有多少种变换座位的方法，使得每个小孩前面坐的都不是原来的小孩？,解 将围坐在旋转木马上的8个小孩按逆时针方向用1,2,8编号,那么,问题就是在1,2,8的循环排列中没有模式12,23,78,81的全体的数目。,设S是1,2,8的循环排列全体，则|S|=7!

8、。,设 A1=S中1和2连续排在一起的循环排列 A2=S中2和3连续排在一起的循环排列 A8=S中8和1连续排在一起的循环排列,则问题归结为求,4.4 限制排列与棋盘多项式,(1) |Ai|=6!,i=1,2,8. (2) |AiAj|=5!. |Ai1Ai 2 Aik |=(8-k)!,所以，,4.4 限制排列与棋盘多项式,6.4、5 带有禁止位置的排列,例求多重集S=3a, 4b, 2c的排列数，其中同一种字母的全体不得连续出现（例如，abbbbcaac是不允许的，而abbbacacb是允许的）。,4.4 限制排列与棋盘多项式,4.4 限制排列与棋盘多项式,4.4 限制排列与棋盘多项式,4.4 限制排列与棋盘多项式,4.4 限制排列与棋盘多项式,4.4 限制排列与棋盘多项式,4.4 限制排列与棋盘多项式,4.4 限制排列与棋盘多项式,4.4 限制排列与棋盘多项式,4.4 限制排列与棋盘多项式,再见,