組合數(shù)學(xué)補(bǔ)充內(nèi)容

1、組合數(shù)學(xué)補(bǔ)充內(nèi)容1容斥原理在說到加法原理時強(qiáng)調(diào)過要求事件的獨立性當(dāng)多個事件不再獨立時例如：在某一個學(xué)校，教A班的老師有10人，教B班的老師有10人，問教A，B兩班老師有多少人？答案不一定是20人。因為可能有一個老師同時教兩個班的情況，這就是不獨立的情況加上條件：同時教A，B兩班的老師有5人容斥原理：2容斥原理例題2：1100內(nèi)，能被3，5兩個數(shù)之一整除的數(shù)有多少個？能被3整除的數(shù)有100/3 = 33個，能被5整除的數(shù)有100/5 = 20個，所以能被3，5之一整除的數(shù)有33+20 = 53個？上述說法是錯誤的。例如15既能被3整除又能被5整除，再上述算法中被計算了2次所以應(yīng)該減去能同時被3，

2、5即能被15整除的數(shù)的個數(shù)6個，正確答案應(yīng)為33+20-6 = 47個獨立不獨立3容斥原理例題3：前面我們接觸到的都是2個事件的情況，現(xiàn)在來看一個當(dāng)事件數(shù)為3的情況。1100內(nèi)，能被2，3，5三個數(shù)之一整除的數(shù)有多少個？能被2，3，5整除的數(shù)分別有50，33，20個。能被2，3同時整除的數(shù)有16個；能被2，5同時整除的數(shù)有10個；能被3，5同時整除的數(shù)有6個所以答案為50 + 33 + 20 16 10 6 = 71個？考慮能同時被2，3，5整除的數(shù)，在計算能被一個數(shù)整除的數(shù)時被加了3次，而在計算能被兩個數(shù)整除的數(shù)時被減了3次，也就是說最后答案71漏算了這些數(shù)！所以，答案應(yīng)為71 + 3 =

3、74個！4容斥原理有了前幾題的基礎(chǔ)，來看一題比較具有普遍意義的題：給出n個數(shù)a1, a2, , an，問1, m區(qū)間內(nèi)的整數(shù)有多少個能被這些數(shù)之一整除能同時被a1, a2, , ak整除等價于能被lcm (a1, a2, , ak)整除，即能被他們的最小公倍數(shù)整除利用容斥原理：對于這n個數(shù)中的每一個數(shù)，答案加上能被這個數(shù)整除的數(shù)個數(shù)對于每兩個數(shù)，答案減去能被這兩個數(shù)整除的數(shù)的個數(shù)對于每三個數(shù)，答案加上能被這三個數(shù)整除的數(shù)的個數(shù)對于每四個數(shù)，答案減去能被這四個數(shù)整除的數(shù)的個數(shù)5容斥原理上述例題該如何用程序?qū)崿F(xiàn)？主要要實現(xiàn)枚舉子集方法1：利用回溯法枚舉計算方法2：利用位運算，直接For循環(huán)得到方法

4、1比較基礎(chǔ)，不在這里討論。接下來要說的是比較容易實現(xiàn)的方法26容斥原理上述例題該如何用程序?qū)崿F(xiàn)？枚舉子集S無非就是看第i個數(shù)是否在集合S中，那么即枚舉12n 1，在二進(jìn)制下即為0000111111，右數(shù)第i位對應(yīng)了第i個數(shù)是否在所枚舉到的集合S中例如，n = 4時：十進(jìn)制5對應(yīng)了二進(jìn)制0101，表示了a1與a3在集合中。對應(yīng)到原題，當(dāng)枚舉到這個數(shù)時你需要計算能同時被a1, a3整除的數(shù)有多少個，由于有2個數(shù)（1的個數(shù)為2），則在答案中減去所求結(jié)果十進(jìn)制11對應(yīng)了二進(jìn)制1011，表示了a1, a2與a4在集合中。對應(yīng)到原題，當(dāng)枚舉到這個數(shù)時，你需要計算能同時被a1, a2, a4整除的數(shù)有多少個

5、，由于有3個數(shù)（1的個數(shù)為3），則在答案中加上所求結(jié)果7容斥原理for(inti=1;i(1n);i+)ints=1,c=0;for(intj=0;j j) & 1) /如果i的第j+1位是1c+;s= lcm (s, ai); /那么求lcmif(c % 2 = 1) /如果當(dāng)前計算數(shù)個數(shù)是奇數(shù)ans+=m / s;elseans-=m / s;8容斥原理fori := 1 to 1 shl n do begins:=1;c:=0;for j:= 0 to n 1 doif(ishr j) and 1 = 1 then begininc (c);s:= lcm (s, ai); end;if

6、c mod 2 = 1 thenans:=ans + m div s;elseans:=ans + m div s;end;9組合數(shù)的枚舉組合數(shù)的枚舉比全排列的枚舉容易一些枚舉從1, n整數(shù)中取出r個元素由于組合數(shù)是無序的，所以為了枚舉方便，我們不妨將枚舉出來的r個元素從小到大定序例如枚舉從1, 4整數(shù)中取出3個數(shù)，應(yīng)該有以下4種情況：1 2 31 3 41 2 42 3 4通過遞歸很容易實現(xiàn)這一枚舉，下面我們通過程序來說明10組合數(shù)的枚舉void recu (int k, int st) /還有k個數(shù)要枚舉，開始枚舉的最小數(shù)為st if (k = 0) output (); return;

7、for (int i = st; i a2-a3，B=b1-b2-b3-b4-b5。在任何時候，小陳只能專心做某個任務(wù)的一個步驟。但是如果愿意，他可以在做完手中任務(wù)的當(dāng)前步驟后，切換至另一個任務(wù)，從上次此任務(wù)第一個未做的步驟繼續(xù)。每個任務(wù)的步驟順序不能打亂，例如a2-b2-a3-b3是合法的，而a2-b3-a3-b2是不合法的。小陳從B任務(wù)的b1步驟開始做，當(dāng)恰做完某個任務(wù)的某個步驟后，就停工回家吃飯了。當(dāng)他回來時，只記得自己已經(jīng)完成了整個任務(wù)A，其他的都忘了。試計算小陳飯前已做的可能的任務(wù)步驟序列共有 種。14來自初賽的例題例題2解答：由于A，B任務(wù)都是定好序的，假設(shè)做完了k個B任務(wù)（不包括

8、b1因為b1位置已經(jīng)定死，則0 = k = 4)，那么問題等價于將3個a與k個B排成一排，問有多少種方案。那么如何求將3個a與k個B排成一排的方案數(shù)呢？等價于有3+k個位置，給這3個a安排3個位置，那么有C(3 + k, 3)種方案枚舉k，得到答案為C(3, 3) + C(4, 3) + C(5, 3) + C(6, 3) + C(7, 3) = C(8， 4) = 7015來自初賽的例題例題3(NOIP2004提高組)：由3個a，5個b和2個c構(gòu)成的所有字符串中，包含子串“abc”的共有（ ）個。例題3解答：包含至少一個“abc”的子串：即對1個“abc”，2個“a”，4個“b”，1個“c”

9、進(jìn)行排列，有C(8, 1)C(7, 2)C(5, 4) C(1, 1)= 840種方案但是包含兩個“abc”的子串的字符串被計算了兩次，所以需要減去對2個“abc”，1個“a”，3個“b” 進(jìn)行排列，有C(6, 2)C(4, 1)C(3, 3) = 60種方案所以答案為840 60 = 78016來自初賽的例題例題4(NOIP2008提高組)：書架上有21本書，編號從1到21，從其中選4本，其中每兩本的編號都不相鄰的選法一共有_種。例題4解答：這題有多種方法，這里給出一種利用容斥原理解的方法首先從21本書中取4本有C(21, 4) = 5985種方案（取4本書）有（至少）一對書編號相鄰有20C

10、(21 2, 2) = 3420種情況有兩對書編號相鄰有兩種類型：一種是連著3本書，有19(21 3) = 342種情況；一種是分開著兩對書，有C(19, 2) = 171種情況4個書編號相連情況有18種所以答案為5985 3420 + (342 + 171) 18 = 306017來自初賽的例題例題4解答2：建立與18本書取4本的一一映射關(guān)系18本書取出4本，再編號前3小的書之后插入一個編號，并將新的21本書從小到大編號，即成21本書取出4本不相鄰編號的書21本書取出4本不相鄰編號的書，刪除前3本書編號之后的那個編號，并將新的18本書從小到大編號，即成18本書取出任意4本編號的書答案為C(1

11、8, 4) = 306018概率初步古典概型：P(A) = #A/#例題1：硬幣拋出正面的概率是多少？硬幣拋出后的結(jié)果有兩種情況（等可能），而正面是這兩種情況之一，所以概率為1/2例題2：扔一枚骰子，扔出的點數(shù)小等于2的概率是多少？扔出后結(jié)果有6種情況，而小等于2占了其中兩種，所以概率為2/619概率初步例題3：同時扔兩枚骰子，點數(shù)之和為6的概率是多少？錯誤的解法：扔出點數(shù)和結(jié)果可能為212，有11種情況，所以概率為1/11正確的解法：由乘法原理可以得到兩個骰子投出點數(shù)的情況數(shù)為66 = 36種，而點數(shù)和得到6的情況有 (1, 5), (2, 4), (3, 3), (4, 2), (5, 1)。所以正確答案應(yīng)為5/3620概率初步例題4：扔一枚骰子n次，所得點數(shù)最大值為5最小值為2的概率結(jié)合容斥原理答案為(4n 23n + 2n) / 6n為什么？