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

1、ACM程序設(shè)計第十二講-組合數(shù)學(xué)湖南工學(xué)院 張新玉組合數(shù)學(xué)簡介組合數(shù)學(xué)起源于古老的數(shù)學(xué)娛樂和游戲。而在當今社會中同樣發(fā)揮著重要的作用。組合數(shù)學(xué)研究一個集合的物體進行滿足一些規(guī)則的排列。具體的說，組合數(shù)學(xué)研究的是這些排列的存在性、計數(shù)和分類。在ACM/ICPC中用到的組合數(shù)學(xué)知識有： 加法乘法原理、多重集排列和組合、遞推關(guān)加法乘法原理、多重集排列和組合、遞推關(guān)系、母函數(shù)、鴿巢原理、容斥原理、系、母函數(shù)、鴿巢原理、容斥原理、加法乘法原理 加法原理 把事情分成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經(jīng)B到C有32=6 條道路。例 題例1、數(shù)1,2,3,9的全排列中，求偶數(shù)在原來位置上，其余都不在原來位置上的錯排數(shù)目。 解：偶數(shù)位置不動，相當于求1,3,5,7,9五個數(shù)字的錯排，所求的排列數(shù)為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四個字母不在原來位置上的錯排數(shù)目。 解：令S為的8個字母的全排列的集合，有|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個字母A,B,C,D,E,F,G,H的全排列中只有4個元素不在原來位置上的排列數(shù)。 解：8個字母中只有4個不在原來的位置上，其余4個不動，相當于4個數(shù)字的錯排，首先在8個字母中選出4個不動的數(shù)字，再作其他4個數(shù)字的錯排。根據(jù)乘法法則，所求的排列數(shù)為C(8,4)D4=630例 題例4、求1,2,n的全排列中，正好只有r(0rn)個元素在原來位置上的排列個數(shù)。 解：從1,2,n中取r個數(shù)有C(n,r)種方式，選定r個數(shù)后，剩下的n-r個數(shù)不在原來的位置上，相當于n-r個數(shù)字的錯排，根據(jù)乘法法則，所求的排列數(shù)為C(n,r)

5、Dn-r例 題例5、設(shè)有n冊書分給n個學(xué)生，之后又將這n冊書收回重新分給這n個學(xué)生。問有多少方式分配這n冊書使得沒有一個學(xué)生兩次得到同一冊書? 解： n冊書可以用n!種方式第一次分給n個學(xué)生。對第二次分配，據(jù)題意，這是一個n冊書的錯排。由乘法法則，所求的方式數(shù)為n!Dn兩個推論推論3.5.1：nnDne1lim!證明： 由于e-1可以表成下列的無窮級數(shù)：故即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個數(shù)進行錯排，由乘法法則，這種類型的錯排列數(shù)為(n-1)Dn-2 。對于k2,3,n，令a1=k,ak1 。選取a1的方法仍有n-1種。由于a1=k已定，且ak1 ，故將剩下的n-1個數(shù)2,3,k-1,1, k+1,n進行錯排（此時將1看作k），由乘法法則，這種類型的錯排數(shù)為(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的素數(shù)個數(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的素數(shù)個數(shù)，因為這里排除了2，3，5，7這四個數(shù)，又包含了1這個非素數(shù)。2，3，5，7本

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

10、個巢，至少有一個巢里有 只鴿子nm推論推論n(m1) + 1只鴿子進n個巢，至少有一個巢內(nèi)至少有m只鴿子推論推論若m1 , m2 , , mn是正整數(shù)，且 r1,則 m1, , mn至少有一個不小于rm1 + +mn n例例 題題例例5、將將1, 2, , 10隨機地擺成一圓，隨機地擺成一圓，則必有某相鄰三數(shù)之和至少是則必有某相鄰三數(shù)之和至少是17。 證明：證明：設(shè)設(shè)表示該圓上相鄰三個數(shù)之和（表示該圓上相鄰三個數(shù)之和（i居中）。居中）。這樣的和共有這樣的和共有10個。而個。而1,2,10中的每一個都出現(xiàn)在這十個和的中的每一個都出現(xiàn)在這十個和的三個之中，故三個之中，故由推論由推論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個人彼此不相識，則結(jié)論成立。如果個人彼此不相識，則結(jié)論成立。如果F中有中有2人相識，則由于這兩個人都與人相識，則由于這兩個人都與p相識，因此有相識，因此有3人彼此相識，故人彼此相識，故定理結(jié)論成立。定理結(jié)論成立。類似的，如果類似的，如果S包含包含3個人，則這個人，則這3個人或者彼此相識，或者有兩個人或者彼此相識，或者有兩個人彼此不相識。如果這個人彼此不相識。如果這3個人彼此相識，則結(jié)論成立。如果有個人彼此相識，則結(jié)論成立。如果有

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

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