ACM培訓第十二講-組合數學

1、ACM程序設計第十二講-組合數學湖南工學院 張新玉組合數學簡介組合數學起源于古老的數學娛樂和游戲。而在當今社會中同樣發(fā)揮著重要的作用。組合數學研究一個集合的物體進行滿足一些規(guī)則的排列。具體的說，組合數學研究的是這些排列的存在性、計數和分類。在ACM/ICPC中用到的組合數學知識有： 加法乘法原理、多重集排列和組合、遞推關加法乘法原理、多重集排列和組合、遞推關系、母函數、鴿巢原理、容斥原理、系、母函數、鴿巢原理、容斥原理、加法乘法原理 加法原理 把事情分成N類，每類有Ci種做法，則該事情共有C1+C2+CN種做法 乘法原理 把事情分成N步，每步有Ci種做法，則該事情共有C1*C2*CN種做法 例

2、 某班選修企業(yè)管理的有 18 人，不選的有 10 人，則該班共有 18 + 10 = 28 人。 例 北京每天直達上海的客車有 5 次，客機有 3 次， 則每天由北京直達上海的旅行方式有 5 + 3 = 8 種。例 某種字符串由兩個字符組成，第一個字符可選自a，b，c，d，e，第二個字符可選自1，2，3，則這種字符串共有5 3 = 15 個。例 從A到B有三條道路，從B到C有兩條道路，則從A經B到C有32=6 條道路。例 題例1、數1,2,3,9的全排列中，求偶數在原來位置上，其余都不在原來位置上的錯排數目。 解：偶數位置不動，相當于求1,3,5,7,9五個數字的錯排，所求的排列數為D5=5!

3、(1-1/1!+1/2!-1/3!+1/4!-1/5!)=44錯排問題例 題例2、在8個字母A,B,C,D,E,F,G,H的全排列中，求使A,C,E,G四個字母不在原來位置上的錯排數目。 解：令S為的8個字母的全排列的集合，有|S|=8!。令Ai(i=1,2, 3,4)分別表示A,C,E,G在原位置的排列的集合。顯然，|Ai|=7!, (i=1,2,3,4)，|AiAj |=6!,(i,j=1,2,3,4;ij)，（參照定理3.5的證明過程）。由乘法法則和容斥原理得 iijiijijlij l|AAAA |S|A |AA |AAA | |AAAA |412341122444448!7!6!5!

4、4!1234403202016043204802424024 例 題例3、求8個字母A,B,C,D,E,F,G,H的全排列中只有4個元素不在原來位置上的排列數。 解：8個字母中只有4個不在原來的位置上，其余4個不動，相當于4個數字的錯排，首先在8個字母中選出4個不動的數字，再作其他4個數字的錯排。根據乘法法則，所求的排列數為C(8,4)D4=630例 題例4、求1,2,n的全排列中，正好只有r(0rn)個元素在原來位置上的排列個數。 解：從1,2,n中取r個數有C(n,r)種方式，選定r個數后，剩下的n-r個數不在原來的位置上，相當于n-r個數字的錯排，根據乘法法則，所求的排列數為C(n,r)

5、Dn-r例 題例5、設有n冊書分給n個學生，之后又將這n冊書收回重新分給這n個學生。問有多少方式分配這n冊書使得沒有一個學生兩次得到同一冊書? 解： n冊書可以用n!種方式第一次分給n個學生。對第二次分配，據題意，這是一個n冊書的錯排。由乘法法則，所求的方式數為n!Dn兩個推論推論3.5.1：nnDne1lim!證明： 由于e-1可以表成下列的無窮級數：故即nnnnnnnnnDnnenDennnDennDen111211111! 1.( 1)1!2!11111.( 1).1!2!3!11( 1)( 1).!(1)!(2)!1!(1)!lim! 兩個推論推論3.5.2：Dn=(n-1)(Dn-1

6、+Dn-2) 推論3.5.1：nnDne1lim!證明： 1,2,n的錯排可以分為兩種互不相容的類型。對于k2,3,n，令a1=k,ak=1。由于a11，故選取a1的方法有n-1種。而a1=k,ak=1的值已定，故將剩下的n-2個數進行錯排，由乘法法則，這種類型的錯排列數為(n-1)Dn-2 。對于k2,3,n，令a1=k,ak1 。選取a1的方法仍有n-1種。由于a1=k已定，且ak1 ，故將剩下的n-1個數2,3,k-1,1, k+1,n進行錯排（此時將1看作k），由乘法法則，這種類型的錯排數為(n-1)Dn-1 。由于這兩種類型互不相容，由加法法則有Dn=(n-1)(Dn-1+Dn-2)

7、容斥原理12111112.( 1).nnnniijiiinnjjkAAAAAAAAAAAA nii=1 ji kj A+ 容斥原理兩個基本公式容斥原理兩個基本公式121211112.( 1).nnnnniijiijjkninAAANAAAANAAAAAAAAnii=1 ji kj A- 容斥原理指的就是以上兩個基本公式。容斥原理兩個基本公式容斥原理兩個基本公式 例例 求不超過120的素數個數。 因不超過120的合數必然是2、3、5、7的倍數，而且不超過120的合數的因子不可能都超過11。 設 Ai 為不超過120的數 i 的倍數集，i =2，3，5，7。23572325273512012060

8、40231201202417,571201202012,2 310120120881415AAAAAAAAAAAA，375723523725712012053213512042 3 512022 3 712012 5 7AAAAAAAAAAAAA ，235723572325273537572352372573572357120AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA 120(604024 17)(20 128853)(42 1 1)27. 注意：注意：27并非就是不超過120的素數個數，因為這里排除了2，3，5，7這四個數，又包含了1這個非素數。2，3，5，7本

9、身是素數。故所求的不超過120的素數個數為： 27+4-1=30鴿巢原理鴿巢原理 鴿巢原理是組合數學中最簡單也是最基本的原理，也叫抽屜原理。即“若有n個鴿子巢，n+1個鴿子，則至少有一個巢內有兩個或兩個以上鴿子?！崩?67人中至少有人的生日相同。例例10雙手套中任取11只，其中至少有兩只是完整配對的。鴿巢原理之二鴿巢原理之二鴿巢原理二鴿巢原理二m1 , m2 , , mn都是正整數，并有m1 + m2 + +mnn + 1個鴿子住進n個鴿巢，那么，或者第 1個巢中至少有m1個鴿子，或者第 2個巢中至少有m2個鴿子,或者第 n個巢中至少有mn個鴿子 鴿巢原理之二鴿巢原理之二推論推論m只鴿子進n

10、個巢，至少有一個巢里有 只鴿子nm推論推論n(m1) + 1只鴿子進n個巢，至少有一個巢內至少有m只鴿子推論推論若m1 , m2 , , mn是正整數，且 r1,則 m1, , mn至少有一個不小于rm1 + +mn n例例 題題例例5、將將1, 2, , 10隨機地擺成一圓，隨機地擺成一圓，則必有某相鄰三數之和至少是則必有某相鄰三數之和至少是17。 證明：證明：設設表示該圓上相鄰三個數之和（表示該圓上相鄰三個數之和（i居中）。居中）。這樣的和共有這樣的和共有10個。而個。而1,2,10中的每一個都出現在這十個和的中的每一個都出現在這十個和的三個之中，故三個之中，故由推論由推論2.2.3知，存

11、在一個知，存在一個i ，使，使 。(1,2,.,10)im i 1013(12.10)16.51711010iim (1,2,.,10)i 17im 定理定理6個人中一定有個人中一定有3個人相互認識或相互不認識。個人相互認識或相互不認識。證明：證明：先考慮先考慮6個人中的任意一個人，不妨把這個人稱作個人中的任意一個人，不妨把這個人稱作p。則其。則其他的他的5個人可以分為下面的兩個集合個人可以分為下面的兩個集合F和和S。其中。其中F=與與p相識的人的集合，相識的人的集合，S=與與p不相識的人的集合不相識的人的集合由鴿籠原理知，這兩個集合中至少有一個集合包含有由鴿籠原理知，這兩個集合中至少有一個集

12、合包含有3個人。個人。若若F包含有包含有3個人，則這個人，則這3個人或者彼此不相識，或者有兩個人彼個人或者彼此不相識，或者有兩個人彼此相識。如果此相識。如果F中有中有3個人彼此不相識，則結論成立。如果個人彼此不相識，則結論成立。如果F中有中有2人相識，則由于這兩個人都與人相識，則由于這兩個人都與p相識，因此有相識，因此有3人彼此相識，故人彼此相識，故定理結論成立。定理結論成立。類似的，如果類似的，如果S包含包含3個人，則這個人，則這3個人或者彼此相識，或者有兩個人或者彼此相識，或者有兩個人彼此不相識。如果這個人彼此不相識。如果這3個人彼此相識，則結論成立。如果有個人彼此相識，則結論成立。如果有

13、兩個人彼此不相識，則由于這兩個人都與兩個人彼此不相識，則由于這兩個人都與p也不相識，因此有也不相識，因此有3個個人彼此不相識，故定理結論成立。人彼此不相識，故定理結論成立。Ramsey定理定理定理定理10人中一定有人中一定有4人相互認識或有人相互認識或有3人相互不認識。人相互不認識。 證明：證明：在這在這10個人中任意挑選一個人，不妨把這個人稱作個人中任意挑選一個人，不妨把這個人稱作p。則。則其他的其他的9個人可以分為下面的兩個集合個人可以分為下面的兩個集合F和和S。其中。其中F=與與p相識的人的集合，相識的人的集合，S=與與p不相識的人的集合不相識的人的集合如果如果S中有中有4個（或個（或4

14、個以上）人個以上）人，則或者這，則或者這4個人（或個人（或4個人以上）個人以上）或者彼此認識，或者有兩個人彼此不認識。如果有或者彼此認識，或者有兩個人彼此不認識。如果有4個人彼此認個人彼此認識，則結論成立。如果在識，則結論成立。如果在S中有中有2人彼此不認識，則由于這兩個人人彼此不認識，則由于這兩個人都與都與p不認識，因此有不認識，因此有3人彼此不認識，故定理結論成立。人彼此不認識，故定理結論成立。如果如果S中最多有中最多有3個人，個人，則由鴿籠原理知，則由鴿籠原理知，F中至少有中至少有6個人。由定個人。由定理理2.3知，知，F中一定有中一定有3人相互認識或有人相互認識或有3人相互不認識。如果有人相互不認識。如果有3個人彼此不認識，則定理成立。如果有個人彼此不認識，則定理成立。如果有3個人彼此認識，則把個人彼此認識，則把p加加入，就有入，就