ACM培訓(xùn)第十二講-組合數(shù)學(xué)

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

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

3、(1-1/1!+1/2!-1/3!+1/4!-1/5!)=44錯(cuò)排問題例 題例2、在8個(gè)字母A,B,C,D,E,F,G,H的全排列中，求使A,C,E,G四個(gè)字母不在原來位置上的錯(cuò)排數(shù)目。 解：令S為的8個(gè)字母的全排列的集合，有|S|=8!。令A(yù)i(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個(gè)字母A,B,C,D,E,F,G,H的全排列中只有4個(gè)元素不在原來位置上的排列數(shù)。 解：8個(gè)字母中只有4個(gè)不在原來的位置上，其余4個(gè)不動(dòng)，相當(dāng)于4個(gè)數(shù)字的錯(cuò)排，首先在8個(gè)字母中選出4個(gè)不動(dòng)的數(shù)字，再作其他4個(gè)數(shù)字的錯(cuò)排。根據(jù)乘法法則，所求的排列數(shù)為C(8,4)D4=630例 題例4、求1,2,n的全排列中，正好只有r(0rn)個(gè)元素在原來位置上的排列個(gè)數(shù)。 解：從1,2,n中取r個(gè)數(shù)有C(n,r)種方式，選定r個(gè)數(shù)后，剩下的n-r個(gè)數(shù)不在原來的位置上，相當(dāng)于n-r個(gè)數(shù)字的錯(cuò)排，根據(jù)乘法法則，所求的排列數(shù)為C(n,r)

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

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

7、容斥原理12111112.( 1).nnnniijiiinnjjkAAAAAAAAAAAA nii=1 ji kj A+ 容斥原理兩個(gè)基本公式容斥原理兩個(gè)基本公式121211112.( 1).nnnnniijiijjkninAAANAAAANAAAAAAAAnii=1 ji kj A- 容斥原理指的就是以上兩個(gè)基本公式。容斥原理兩個(gè)基本公式容斥原理兩個(gè)基本公式 例例 求不超過120的素?cái)?shù)個(gè)數(shù)。 因不超過120的合數(shù)必然是2、3、5、7的倍數(shù)，而且不超過120的合數(shù)的因子不可能都超過11。 設(shè) Ai 為不超過120的數(shù) i 的倍數(shù)集，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的素?cái)?shù)個(gè)數(shù)，因?yàn)檫@里排除了2，3，5，7這四個(gè)數(shù)，又包含了1這個(gè)非素?cái)?shù)。2，3，5，7本

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

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

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

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

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

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