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 6.1 容斥原理 4 6.1 容斥原理 5 6.1 容斥原理 6 6.1 容斥原理 7 6.1 容斥原理 8 6.2 帶重復的組合 9 6.2 帶重復的組合 10 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個錯位排列: 21 n=3，有2個錯位排列:

4、 231, 312 n=4，有9個錯位排列: 2143, 3142, 4123, 2341, 3412, 4312, 2413, 3421, 4321 6.3 錯位排列 12 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-1 nDn=nDn-1+(-1)n

5、 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 帶有禁止位置的排列 14 n設X1, X2, Xn是1,

6、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 =2, Xn=n。則集合P(X1,

7、 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個非攻 擊型車的放置，對于這些非攻擊型車來說在這個棋盤上有 某些方格禁止放車 n例子例子 設n=5,

8、 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|(n-1)!, |Ai|=|Xi|(n

9、-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): 2; F1(1), F2(1): 3

10、4 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，第一天隊列為12345678 要求確定

11、集合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 6.6 莫比烏斯反演 20 6.6 莫比烏斯反演 21 6.6 莫比烏斯反演 22 6.6 莫比烏斯反演 23 6.6 莫比烏斯反演 24 6.6 莫比烏斯反演 25 6.6 莫比烏斯反演 26 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,