Chap3-2广义容斥原理.ppt

《Chap3-2广义容斥原理.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、例2一个学校只有三门课程：数学、物理、化学。已知修这三门课的学生分别有170、130、120人；同时修数学、物理的学生45人；同时修数学、化学的20人；同时修物理化学的22人。同时修三门的3人。假设每个学生至少修一门课，问这学校共有多少学生？3.3.广义容斥原理若将３.1中的例子2改为“单修一门数学的学生有多少？”“只修一门课的学生有多少”“只修两门课的学生有多少？”单修一门数学的用来表示，则有类似的同样的设有与性质１,2,···,n相关的元素N个，Ai为有第i种性质的元素的集合.i=1,2,…,n定义a(0)=n；当m>1时b(m)是正好具有m个性质的元素的个数

2、。例如，对于n=3,m=2利用这些记号b(1)=a(1)-2a(2)+3a(3)b(2)=a(2)-3a(3)定理（广义容斥原理）：特别的，当m=0时例1某校有12个教师，已知教数学的有8位，教物理的有6位，教化学的5位；数、理5位，数、化4位，理、化3位；数理化3位。问教其他课的有几位？只教一门的有几位？只教两门的有几位？解:令教数学的教师属于A1，教物理的属于A2，教化学的属于A3。则a(0)＝12，a(1)＝

3、A1

4、+

5、A2

6、+

7、A3

8、＝8+6+5＝19;a(2)＝

9、A1∩A2

10、+

11、A1∩A3

12、+

13、A2∩A3

14、＝12；a(3)＝

15、A1∩A2∩A3

16、＝3；故教

17、其他课的老师数为：b(0)=a(0)-a(1)+a(2)-a(3)=2只教一门的教师数为：b(1)=a(1)-2a(2)+3a(3)=4恰好教两门的老师数为：b(2)=a(2)-3a(3)=33.4.广义容斥原理应用1、非负整数解线性方程的非负整数解：非负整数解的个数为C(n+r-1,r)非负整数解一一对应于r个相同的球放入n个不同的盒子中的方案但对于方程求满足附加条件的解的个数。若无上界条件限制，则非负整数解的个数为C(15+3-1,15)=C(17,2)令N为全体非负整数解；为其中的解；为其中的解；为其中的解；对于A1，相当于求方程的非负整数解类似的故方程满足

18、条件的解为另解：做变量替换则问题转化为求方程的非负整数解。其个数为C(3+3-1,3)=C(5,2)=102、第二类Stirling数的展开式先考虑m个有标志的球放入n个有区别的盒子,无一空盒的情形则m个有标志的球放入n个有区别的盒子,无一空盒的方案数为3、错排问题的推广例如，3个中取2个的排列有P(3,2)=6个，其中D(3,2,0)=3213123D(3,2,1)=21332D(3,2,2)=1124、n对夫妻问题n对夫妻围一圆桌坐下，要求男女相邻而又避免夫妻座位相邻，求这样的方案数。从1,2,…,n中取r个不相邻的数的组合方案数为C(n-r+1,r)首先讨论

19、问题：假定数1,2,…,n沿一圆周排列，整数k满足0≤k≤[n/2]，其k元子集中无一相邻数的方案数为c(k)(1和n相邻)。定理：证明：设di表示这样的k元子集中含有元i的数目设A1表示含有元1的k元子集，则A1不含有2和n，故它的其他k-1个元素是从3,4,..,n-1中取不相邻的又由于每个集合有k个元素，因此求和时每个子集都重复计算了k次，故有假定n位夫人先依次围圆桌坐下，要求相邻两位之间留下一个空位。然后，她们的丈夫再找空位坐，这样保证了男女相间而坐。设正好有r对夫妻相邻而坐的方案数为M(n,r)，则证明：设N是所有的所有排列的集合注意：对于n

20、于0

21、n时，由不重复的d个元素重复n/d次构成的圆排列只能形成d个不同的线排列。若一个圆排列可由一个长度为k的线排列重复若干次形成，则这样的k中最小者称为该圆排列的

22、周期。一个圆排列中元素的个数（重复者按重数计）称为它的长度。设由集合1,2,…,m中元素形成的长度与周期都是d的圆排列的个数为M(d)，n是给定的正整数。若d

23、n，每个长度与周期都是d的圆排列可在d个位置上断开，重复n/d次形成d个长度为n的可重排列，因此有根据反演定理有长度为n的可重圆排列个数为