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

4.1 引言 4.1 引言 4.1 引言 4.1 引言 4.1 引言 4.2 容斥原理 4.2 容斥原理 4.2 容斥原理 4.2 容斥原理 4.2 容斥原理 4.2 容斥原理 4.2 容斥原理 4.2 容斥原理 4.2 容斥原理 4.3 应用 4.3 应用 4.3 应用 4.3 应用 4.3 应用 4.3 应用 4.4 限制排列与棋盘多项式 4.4 限制排列与棋盘多项式 引言 容斥原理 应用 限制排列与棋盘多项式 莫比乌斯反演公式 例 在一根长的木棍上有两种刻度线，第一种刻度线将木棍分成10等份，第二种将木棍分成12等份。如果沿每条刻度线将木棍锯断，木棍总共被锯成多少段？ 例 在一根长的木棍上有三种刻度线，第一种刻度线将木棍分成10等份，第二种将木棍分成12等份，第三种将木棍分成15等份。如果沿每条刻度线将木棍锯断，木棍总共被锯成多少段？ 例 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 应用 于是A1∩A2 表示A中能被4和5整除的数,即能被20整除的数，其个数为 |A1∩A2|=L1000/20」=50； 同理, |A1∩A3|=L1000/12」=83, |A2∩A3|=L1000/30」=33, 4.3 应用 A1 ∩A2 ∩ A3 表示A中能同时被4,5,6整除的数，即A中能被4,5,6的最小公倍数lcm(4,5,6)=60整除的数，其个数为 | A1∩A2∩A3|=L1000/60」= 16. 由容斥原理知，A中不能被4,5,6整除的整数个数为: 4.3 应用 例 六一儿童节快到了，有爱心巧手妈妈做了3个布娃娃、4个小布熊、5个布兔子共12个布玩具，现选10个送给某儿童福利院，如果忽略同类玩具的差异那么有多少种选送方法？ 此问题相当于求S={3·a,4·b,5·c}的10-组合数. 4.3 应用 例 求S={3·a,4·b,5·c}的10-组合数. 解: 令S∞={∞·a, ∞·b,∞·c}，则S的10-组合数为 设集合A是S∞的10-组合全体，则|A|＝66，现在要求在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(1≤i≤3). 4.3 应用 那么，A1中的元素可以看作是由S∞的10－4＝6组合再拼上4个a构成的，所以 同理， 类似地， 而a的个数小于等于3，b的个数小于等于4，c的个数小于等于5的10-组合全体为 由容斥原理知，它的元素个数为: 4.3 应用 例 确定在非负整数x1,x2,x3,x4不大于7时，方程x1+x2+x3+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上的性质集合P={P1,P2,P3,...,Pn},其中Pi表示排列中i在其自然顺序的位置上(1≤i≤n).令Ai为S中满足性质Pi的全排列的集合. 因Ai中的每一个全排列形如 j1…ji-1iji+1…jn， 而j1…ji-1ji+1…jn是{1,2,…,i-1,i+1,…n}的全排列，所以有 |Ai|=(n-1)