第6章容斥原理及应用

1、组合数学第6章 容斥原理及应用 计算机与软件学院 陆克中 1 6.1 容斥原理 2 n加法原理给出了在集合间不相交的情况下计数并集中对象个数的公式。 容斥原理则给出最一般情形下的计数公式，而对集合之间是否相交没 有限制 n例子例子 计数1, 2, n的排列i1i2in中1不在第一个位置上的那些排列的 数目(即i11) 乘法原理 从2, 3, n中选出一个数k进入到第一个位置: n-1 后跟着集合1, k-1, k+1, n的一个(n-1)元素排列组成: (n-1)! (n-1).(n-1)! 减法原理 1在第一个位置上的排列个数等于2, 3, n的排列个数(n-1)! 1, 2, n的总排列个

2、数等于n! n!- (n-1)!=(n-1).(n-1)! n例子例子 计数1到600之间不能被6整除的整数个数 1到600之间能被6整除的整数个数为600/6 =100 每连续6个整数的第6个整数都能被6整除 1到600之间不能被6整除的整数个数是600-100=500个 计数1到600之间不能被6或8整除的整数个数？ 6.1 容斥原理 3 n 6.1 容斥原理 4 n 6.1 容斥原理 5 n 6.1 容斥原理 6 n 6.1 容斥原理 7 n 6.1 容斥原理 8 n 6.2 带重复的组合 9 n 6.2 带重复的组合 10 n 6.3 错位排列 11 n在一个聚会上，10位绅士查看他们

3、的帽子。有多少种方式使得 这些绅士中没有人能够拿到他们来时所戴的帽子？ nV-8发动机的8个火花塞从汽缸中被取出清洗。有多少种方式能 够将它们放回到汽缸中使得没有火花塞重新被放回到原先被取 出时的汽缸？ n有多少种方法能够将字母M, A, D, I, S, O, N写出，使得所拼的 “单词”与单词MADISON的拼写在下述意义上完全不同：没有 字母占据与它在单词MADISON中占据的位置相同？ n1, 2, n的一个错位排列错位排列是1, 2, n的一个排列i1i2in，使 得i11, i22, inn n用Dn表示1, 2, n的错位排列的数目 n=1，没有错位排列 n=2，有1个错位排列:

4、 21 n=3，有2个错位排列: 231, 312 n=4，有9个错位排列: 2143, 3142, 4123, 2341, 3412, 4312, 2413, 3421, 4321 6.3 错位排列 12 n 6.3 错位排列 13 n Dn=(n-1)(Dn-2+Dn-1) vs n!=(n-1)(n-2)!+(n-1)!) Dn=(n-1)dn dn是形式为2i2i3in, i22, i33, inn的错位排列的数目 dn=dn+dn dn是形为21i3i4in, i33, inn的错位排列的数目: Dn-2 dn是形为2i2i3in, i21, i33, inn的错位排列的数目: Dn

5、-1 nDn=nDn-1+(-1)n vs n!=n(n-1)! Dn-nDn-1=-Dn-1-(n-1)Dn-2=(-1)2Dn-2-(n-2)Dn-3=(-1)n-2(D2-2D1) n例子例子 在一次聚会上，有n位男士和n位女士。这n位女士能够有多少种 方法选择男舞伴开始第一支舞？如果每个人必须换舞伴，那么第二支 舞又有多少种选择方法？ n例子例子 设上述聚会中的n男n女在跳舞前存放他们的帽子。在聚会结束时 随机地返还给他们这些帽子。如果每位男士得到一顶男帽而每位女士 得到一顶女帽，但又都不是他们自己曾经存放的那顶幅子，那么他们 被返还帽子的方法有多少种？ 6.4 带有禁止位置的排列 1

6、4 n设X1, X2, Xn是1, 2, n的子集，用P(X1, X2, Xn) 表示1, 2, n的所有排列i1i2in的集合，使得ik不在 Xk内。其数目用p(X1, X2, Xn)=|P(X1, X2, Xn)|表示 n例子例子 设n=4, X1=1, 2, X2=2, 3, X3=3, 4, X4=l, 4。 则P(X1, X2, Xn)是由1, 2, 3, 4的所有满足i11, 2; i22, 3; i33, 4; i41, 4的排列i1i2i3i4组成的。P(X1, X2, Xn)只包含两个排列3412和4123。因此，p(X1, X2, Xn)=2 n例子例子 设X1=1, X2

7、 =2, Xn=n。则集合P(X1, X2, Xn)等于1, 2, n的所有排列i1i2in中满足i11, i22, inn的那些排列的集合。因此，P(X1, X2, Xn) 是1, 2, n的错位排列的集合，从而有p(X1, X2, Xn)=Dn 6.4 带有禁止位置的排列 15 n1, 2, n的排列 n行n列棋盘上非攻击型不可区分车的 放置 1, 2, n的排列i1i2in对应于棋盘上以方格(1, i1), (2, i2), (n, in)为坐标的n个车的位置。 n在P(X1, X2, Xn)中的排列对应着n行n列棋盘上的n个非攻 击型车的放置，对于这些非攻击型车来说在这个棋盘上有 某些

8、方格禁止放车 n例子例子 设n=5, X1=1, 4, X2=3, X3= , X4=1, 5, X5=2, 5。 则P(X1, X2, Xn)中的排列与下图所示的在棋盘上有禁止位 置的5个非攻击型车的放置一一对应12345 1 2 3 4 5 6.4 带有禁止位置的排列 16 n定理定理6.4.1 将n个非攻击型不可区分的车放到带有禁止 放置位置的n行n列棋盘上的放置方法数等于 n!-r1(n-1)!+ r2(n-2)!- +(-1)k rk(n-k)!+ (-1)krn S: n个非攻击型车在n行n列棋盘上的所有放置方法的集合 Pj: 在第j行上的车是在属于Xj的列上 |A1|=|X1|(

9、n-1)!, |Ai|=|Xi|(n-1)! |Ai|=r1(n-1)!，r1等于棋盘上禁止放车的方格的个数 |Ai Aj |=r2(n-2)!，r2等于把两个非攻击型车放到棋盘禁止 位置上的方法数 |Ai1 Ai2 Aik |=rk(n-k)!，rk等于把k个非攻击型车放到 棋盘禁止位置上的方法数 6.4 带有禁止位置的排列 17 n例子例子 确定特6个非攻击型车放到图中带有禁止位置的6 行6列棋盘上的方法数 禁止位置的集合可以划分成两个“独立”的部分：一个部 分F1包含靠近左上角的三个位置，而另一部分F2包含四个 位置 r1=7 r2=1+2+34=15 F1(2): 1; F2(2):

10、2; F1(1), F2(1): 34 r3=14+32=10 F1(2), F2(1): 14; F1(1), F2(2): 32 r4=12=2 r5= r6=0 方法数=6!-75!+154!-103!+22!=184 123456 1 2 3 4 5 6 6.5 另一个禁止位置问题 18 n设一个班级8个男孩每天练习走步。这些学生站成一队纵列前行，除第 一个男孩外每一个孩子的前面都有另一个男孩。为了让男孩不总看到 他前面的同一个人，第二天，这些学生们决定交换位置，使得没有孩 子前面的男孩与第一天在他前面的男孩是同一个人。他们有多少种方 法交换位置？ 给这些孩子指定数字1, 2, 8，第

11、一天队列为12345678 要求确定集合1, 2, 8的排列中不出现模式12, 23, 78的那些排列的 数量 31542876符合要求，84312657不符合要求 设Qn表示1, 2, n的排列中没有12, 23, (n-1)n这些模式出现的那些 排列的个数 n=1: 1 n=2: 21 n=3: 213, 321, 132 n=4: 4132, 4321, 4213, 3214, 3241, 3142, 2143, 2431, 2413, 1324, 1432 6.5 另一个禁止位置问题 19 n 6.6 莫比乌斯反演 20 n 6.6 莫比乌斯反演 21 n 6.6 莫比乌斯反演 22

12、n 6.6 莫比乌斯反演 23 n 6.6 莫比乌斯反演 24 n 6.6 莫比乌斯反演 25 n 6.6 莫比乌斯反演 26 n 6.6 莫比乌斯反演 27 n例子例子 使用莫比乌斯反演得到把n个非攻击型车放到带 有禁止位置的nn棋盘上的放置方法数的计算公式 把nn棋盘看成是元素为0和1的nn矩阵A=aij: 1i, jn 0: 禁止放置; 1: 非禁止位置 棋盘上4个非攻击型车 矩阵A中4个1，其中A的每行和每 列恰好含有这4个1中的一个 a14=1, a23=1, a31=1, a42=1 (1, 4), (2, 3), (3, 1), (4, 2) 这4个1对应于1, 2, 3, 4的一个排列4, 3, 1, 2，或等