acm-組合數(shù)學(xué)的藝術(shù)1

1、CHAPTER 1（1）Introduction to Combinatorics,By Yuhong Zhang (HAUT) , 186-2371-8860 （O）, 159-3629-0516（H）,ACM-Association for Computing Machinery ICPC-International Collegiate Programming Contest,2020/9/15,2,前言,據(jù)說很早以前，夏禹治水時，河南洛陽附近的大河里浮出了一只烏龜，背上有一個很奇怪的圖形，古人認(rèn)為是一種祥瑞，預(yù)示著洪水將被夏禹王徹底制服。 后人稱之為洛書或河圖。,黃蓉：“九宮之義，法以

2、靈龜，二四為肩，六八為足，左三右七，戴九履一，五居中央”,易經(jīng) 系辭中曰：“河出圖，洛出書，圣人則之”。,2020/9/15,4,洛書構(gòu)造 （楊輝1275） 九子斜排 上下對易 左右相更 四維挺出,原型,洛書,7,前言,幻方可以看作是一個3階方陣，其元素是1到9的正整數(shù)，每行、每列以及兩條對角線的和都是15。 （斜排法）,2020/9/15,8,其它幻方。,1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16,1 15 14 4 12 6 7 9 8 10 11 5 13 3 2 16,【對調(diào)法】,2020/9/15,9,丟勒作品憂郁中的四階幻方,Objective,C

3、ombinatorics, is an important part of discrete mathematics. Techniques for counting are important in computer science, especially in the analysis of algorithm.,組合數(shù)學(xué)的研究對象,組合數(shù)學(xué)研究的主要內(nèi)容是依據(jù)一定的規(guī)則來安排某些事物的有關(guān)數(shù)學(xué)問題。 這些問題包括如下4個方面： 1.這些安排是否存在，即存在性問題。 2.如果這些安排是存在的，那么符合要求的安排又有多少？即計數(shù)問題。 3.怎樣構(gòu)造這樣的安排？即算法構(gòu)造問題 4.如果給出了最

4、優(yōu)化標(biāo)準(zhǔn)，如何從眾多安排中得到最優(yōu)解？,1.存在性問題,實(shí)際生活中的各種問題，有些可以立即得出問題有解還是無解，但也有不少問題難以一時判斷。 例如，n個籠子方n+1個鴿子，至少一個籠子放2個以上鴿子。 競賽中不太可能專門出現(xiàn)判定某個問題是否有解的試題，但往往會在測試數(shù)據(jù)中加入無解的干擾項(xiàng)。,2.計數(shù)問題,如果一個組合的解是存在的，那么很自然地會問有多少不同的解。 例如，將8個“車（皇后）”放在8*8的國際象棋棋盤上，如果它們兩兩不能互吃，那么稱這個8“車”處于一個安全的狀態(tài)。這種狀態(tài)是存在的，問題是有多少種這類狀態(tài)。 這就是一個典型的計數(shù)問題。,3.構(gòu)造性問題,一個組合問題已經(jīng)判定它的解是存在

5、的，甚至也推知有多少個解，但關(guān)鍵問題還在于如果把解（呈現(xiàn)）構(gòu)造出來，有的解哪怕給出一個也好。 如前面提到的魔方問題、正交拉丁方問題。,4.優(yōu)化問題,如果構(gòu)造算法不止一個，自然面臨如何擇優(yōu)，如果改進(jìn)，使得答案盡早地解出來。 如動態(tài)規(guī)劃和線性規(guī)劃問題的解決方法。,Outline,Counting（計數(shù)）: Product rule, sum rule, Permutations namely the number of ways m mutually events can occur n1 + n2 + + nm-1 + nm We can give another formulation in

6、terms of sets. Let A1, A2, , Am be pairwise disjoint sets. Then |A1 A2 Am | = |A1| |A2| |Am| (In fact, this is a special case of the general Principal of Inclusion-Exclusion (PIE),例1,有一所學(xué)校給一名物理競賽優(yōu)勝者發(fā)獎，獎品有三類： 第一類是三種不同版本的法漢詞典； 第二類是四種不同類型的物理參考書； 第三類是兩種不同的獎杯。這位優(yōu)勝者只能挑選一樣獎品。那么，這位優(yōu)勝者挑選獎品的方法有多少？,解：設(shè)S是所有這些獎品

7、的集合，Si是第i類獎品的集合(i=1,2,3)。顯然SiSj=(ij)，于是由加法規(guī)則有,也就是說這位優(yōu)勝者挑選獎品的方法共有9種。,Product Rule（乘法規(guī)則）,If two events are not mutually exclusive (that is we do them separately), then we apply the product rule Theorem: Product Rule Suppose a procedure can be accomplished with two disjoint subtasks. If there are n1 wa

8、ys of doing the first task and n2 ways of doing the second task, then there are n1.n2 ways of doing the overall procedure,example 2,How many different license plates can be made by a state, if each plate is to display three letters followed by three numbers? We divide the procedure of labeling a pla

9、te into six steps - we choose a first letter, a second, and a third, and then a first number, a second, and a third. There are 26 ways to choose a letter of the English alphabet, and there are 10 ways to choose a number from the digits 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Thus the number of possible licens

10、e plates is,26 26 26 10 10 10 = 17,576,000,example 3,某種樣式的運(yùn)動服的著色由底色和裝飾條紋的顏色配成。底色可選紅、藍(lán)、橙、黃，條紋色可選黑、白，則共有多少種著色方案？ 42 = 8 若此例改成底色和條紋都用紅、藍(lán)、橙、黃四種顏色的話，則方案數(shù)是多少？ 4 4 = 16， 而只有 4 3 = 12 種。(必須能區(qū)分條紋色),在乘法法則中要注意事件 A 和 事件 B 的相互獨(dú)立性。,Classification of Permutations,研究排列問題的主要目的是求出根據(jù)已知的條件所能作出的不同排列的種數(shù)。 分類,線排列 圓排列 重排列,P

11、ermutations（排列）,A permutation of a set of distinct objects is an ordered arrangement of these objects. An ordered arrangement of r elements of a set of n elements is called an r-permutation Theorem: The number of r permutations of a set of n distinct elements is It follows that In particular Note he

12、re that the order is important. It is necessary to distinguish when the order matters and it does not,Proof.,In constructing an r-permutation of an n-element set, we can choose the first item in n ways, the second item in n - 1 ways, whatever the choice of the first item, . ,and the rth item in n -

13、(r - 1) ways, whatever the choice of the first r - 1 items. By the multiplication principle the r items can be chosen in n x (n - 1) x . x (n - r + 1)ways.,線排列 線排列是把一些元素排成一條直線,A= r是正整數(shù)，從這n個不同的元素中取r個按照一定的次序排列起來(rn)，稱為集合A的r-排列。 記為P(n,r)。 注意：A的r-排列為A的r有序子集。,例：集合A=a,b,c 集合A有6個2排列：ab,ac,ba,ca, bc，cb 即P(3

14、,2)=6 A有6個3排列：abc,acb,bac,bca,cab,cba, 即P(3,3)=6,例4：由數(shù)字1，2，3，4，5，6可以構(gòu)成多少個數(shù)字互不相同的四位數(shù)。 解：很顯然 這是一個排列P（6，4）360 。 例5：將具有9個字母的單詞FRAGMENTS進(jìn)行排列，要求字母A總是緊跟在字母R的右邊，問有多少種這樣的排法? 解：A和R可以算一個元素，所以這是一個P（8，8） 答案為P(8,8)=8!=40320,Programming Exercise 1,Are you excited when you see the title AC ? If the answer is YES ,

15、AC it ;You must learn these two combination formulas in the school . If you have forgotten it , see the picture.,Now I will give you n and m , and your task is to calculate the answer .,Input & output,In the first line , there is a integer T indicates the number of test cases.Then T cases follows in

16、 the T lines.Each case contains a character A or C, two integers represent n and m. (1=n,m=10),Sample Input 2 A 10 10 C 4 2,Sample Output 3628800 6,二、圓排列 一些元素排成一個圓圈的排列,從集合A=a1,a2,an的n個不同元素中取出r個元素按照某種順序(如逆時針)排成一個圓圈，稱這樣的排列為圓排列(或稱循環(huán)排列)。,圓排列 一些元素排成一個圓圈的排列,注意：把一個圓排列旋轉(zhuǎn)所得到的另一個圓排列視為相同的圓排列。即排列 a1a2ar, a2a3ar

17、a1, a3ara1a2 , ara1a2ar-1 在圓排列中是同一個. 所以圓排列的個數(shù)為 P(n,r)/r=n!/(r(n-r)!) （記下重要結(jié)論）,例6：有8人圍圓桌就餐，問有多少種就座方式?如果有兩人不愿坐在一起，又有多少種就座方式?,解：由圓排列公式知，8人圍圓桌就座一共有8!8=7!種就座方式。 又由于兩人不愿坐在一起，設(shè)這兩個人為甲和乙，當(dāng)甲和乙坐在一起時，相當(dāng)于7個人圍圓桌而坐，其就座方式為7!7=6! 而甲和乙坐在一起時，又有兩種情況，或者甲坐在乙的右面，或者甲坐在乙的左面，這樣一來，甲和乙坐在一起時共有26!種就座方式 ，,有8人圍圓桌就餐，問有多少種就座方式?如果有兩人

18、不愿坐在一起，又有多少種就座方式?,甲和乙不坐在一起時共有就座方式的種數(shù)為 7!26!=56!=3600,Example 6-2,例7 4男4女圍圓桌交替就座有多少種方式?,首先這是一個圓排列 先讓四個男（女）的圍圓桌而坐，有4!/4種就座方式。 加入一個女（男）的進(jìn)去就座就有4種方式 加入第二個女（男）的又有3種方式 。 由乘法規(guī)則知，4男4女圍圓桌交替就座的方式數(shù)為(4!/4)4321=144,Exe2. Lolihunters Birthday Bracelet,In Lolihunters birthday, she received a bracelet which consists

19、 of n (n10) different colors of beads . One day, Lohihunter accidentally broke the bracelet, she didnt remember the order of it. How many different bracelets can she make using the n beads？ Language：C/C+/Java Time limit: within 5mins,參考答案,三、重排列,上面我們討論了從集合A(A中的元素是互不相同的)中選r個元素進(jìn)行排列，在每種排列中每個元素至多只出現(xiàn)一次的情況

20、 現(xiàn)在考慮元素允許重復(fù)出現(xiàn)的情況，即考慮在重集 B=k1a1,k2a2,knan中選r個元素進(jìn)行的排列。,定義1-3 從重集B=k1b1,k2b2,knbn中選取r個元素按照一定的順序排列起來，稱這種r排列為重排列。,定理1-3 重集B=b1,b2,bn的r排列的個數(shù)為 。,證明：選擇r-排列的第一項(xiàng)，可以從n個元素中任選一個 。有n種選法 第二項(xiàng)，由于可以重復(fù)選取，仍有n種選法。 。 由乘法規(guī)則可求得r排列的數(shù)目為 。,例8 由1，2，3，4，5，6這六個數(shù)字能組成多少個五位數(shù)?又可組成多少大于34500的五位數(shù)?,一個五位數(shù)，數(shù)字可以重復(fù)出現(xiàn)，這是一個重排列問題。 由定理1.3知，這六個數(shù)

21、字可以組成 65個五位數(shù) 。,解：,萬位：可選4，5，6。其余四位任選,所以個數(shù)為364,萬位選3， 千位選5，6 后三位任選， 個數(shù)為263,萬位和千位上的數(shù)字分別是3和4，百位上的數(shù)字是5，6 。個數(shù)為262,由加法規(guī)則知，大于34500的 五位數(shù)的個數(shù)為364+263+262=4392,重集B=n1b1,n2b2,nkbk的全排列個數(shù)為n!/n1!n2!nk!,將B中的ni個bi分別賦予上標(biāo)1，2，ni，即 B=A=b11,b12,b1n1, bk1,bk2,bknk 。A中元素個數(shù)為nn1+n2+nk 顯然，集合A的全排列個數(shù)為n!。,定理1.4,證明：,Proof(Con.),又由于

22、ni個bi賦予上標(biāo)1，2，ni的辦法有ni!種， 對于重集B的任一個全排列，都可以產(chǎn)生集合A的n1!n2!nk!個排列(由乘法規(guī)則) 故重集B的全排列個數(shù)為n!n1!n2!nk! 證畢。,四面紅旗、三面藍(lán)旗、二面黃旗、五面綠旗可以組成多少由14面旗子組成的一排彩旗?,解：這是一個重排列問題，它是求重集4紅旗，3藍(lán)旗，2黃旗，5綠旗的全排列的個數(shù) 由定理1.4知，組成一排彩旗的種數(shù)為14!4!3!2!5!,例9,用字母A、B、C組成五個字母的符號，要求在每個符號里，A至多出現(xiàn)2次，B至多出現(xiàn)1次，C至多出現(xiàn)3次，求此類符號的個數(shù)。,這也是一個重排列問題。根據(jù)分析，符合題目要求的符號只有三種情況：

23、2A，0B，3C，1A，1B，3C和2A，1B，2C。,例10,解：,由定理1.4和加法規(guī)則知：此類符號的個數(shù)為 5!/2!0!3! + 5!/1!1!3! + 5!/2!1!2! =60,46,組合恒等式,如圖，求從(0, 0)點(diǎn)到 (m, n)點(diǎn)、沿格子線走 的最短路徑數(shù)N。,一條到達(dá)點(diǎn)(m, n)的路徑對應(yīng) 一個由m個x，n個y組成的排列,x x x y y x y x x y y x x y y x x x y,重集B=n1b1,n2b2,nkbk的全排列個數(shù)為n!/n1!n2!nk!,Combinations (1),Whereas permutations consider ord

24、er, combinations are used when order does not matter Definition: A k-combination of elements of a set is an unordered selection of k elements from the set. (A combination is imply a subset of cardinality k),Combinations (2),Theorem: The number of k-combinations of a set of cardinality n with 0 k n i

25、s is read n choose k.,Combinations (3),A useful fact about combinations is that they are symmetric Corollary: Let n, k be nonnegative integers with k n, then,Combinations: Example,In a sequence of 10 coin tosses, how many ways can 3 heads and 7 tails come up?,The number of ways of choosing 3 heads o

26、ut of 10 coin tosses is,It is the same as choosing 7 tails out of 10 coin tosses, which illustrates the corollary,Combinations: Example C,How many committees of 5 people can be chosen from 20 men and 12 women If exactly 3men must be on each committee? If at least 4 women must be on each committee?,I

27、f exactly three men must be on each committee? We must choose 3 men and 2 women. The choices are not mutually exclusive, we use the product rule,If at least 4 women must be on each committee? We consider 2 cases: 4 women are chosen and 5 women are chosen. Theses choices are mutually exclusive, we us

28、e the addition rule:,Combinations: Example C,How many committees of 5 people can be chosen from 20 men and 12 women If exactly 3men must be on each committee? If at least 4 women must be on each committee?,If exactly three men must be on each committee? We must choose 3 men and 2 women. The choices

29、are not mutually exclusive, we use the product rule,If at least 4 women must be on each committee? We consider 2 cases: 4 women are chosen and 5 women are chosen. Theses choices are mutually exclusive, we use the addition rule:,(Pascal公式) C(n,r)=C(n-1,r)+C(n-1,r-1) (1.9),證明： C(n,r)= n!/r!(n-r)! =C(n

30、-1,r)+C(n-1,r-1),推論2,也可用組合分析的方法論證：,推論2,在集合A的n個元素中固定一個元素，不妨設(shè)為a1， 于是，從n個元素中取r個元素的組合,(1) r個元素中包含a1。這可以從除去a1的n-1個元素中取r-1個元素的組合，然后將a1加入而得到，其組合個數(shù)為C(n-1,r-1)。,2)r個元素中不包含a1。這可以從除去a1的n-1 個元素中取r個元素的組合而得到， 其組合個數(shù)為C(n-1,r)。,由加法規(guī)則即得 C(n,r)=C(n-1,r)+C(n-1,r-1),利用式(1-9)和初始值C(n,0)=C(n,n)=1，對所有非負(fù)整數(shù)可計算出表1-1的三角形陣列，通常稱這

31、個三角陣列為楊輝三角形或Pascal三角形。,0 1 1 1 1 2 1 2 1 3 1 3 3 1 4 1 4 6 4 1 5 1 5 10 10 5 1 6 1 6 15 20 15 6 1 7 1 7 21 35 35 21 7 1 8 1 8 28 56 70 56 28 8 1 ,數(shù)510510能被多少個不同的奇數(shù)整除?,解：510510=2357111317除2是偶數(shù)外都是奇數(shù)，于是要整除510510的奇數(shù)只能是除2以外的奇素數(shù)之積或者1，而且在一個積中一個奇數(shù)至多出現(xiàn)一次 。 奇素數(shù)之積分下面幾種情況討論： 一個奇素數(shù)，一共有C(6，1)=6個 。 六個奇素數(shù)，一共有C(6，6)

32、=1個 被1整除，1個 由加法規(guī)則知總共有6+15+20+15+6+1+1=64個。,例2,從1，2，1000中選出三個整數(shù)，有多少種選法使得所選的三個整數(shù)的和能被3整除?,解：把集合A=1,2,1000分成三個子集合， A1=1,4,7,1000A1= 1000/3+1 =334, A2=2,5,8,998A2= 998/3 +1=333, A3=3,6,9,999 A3 = 999/3 =333 a1+a2+a3能被3整除 ,則只有下面兩種情形： (1)a1，a2和a3取自同一子集Ai(i=1,2,3)中。 選法的種數(shù)為C(334,3)+2C(333,3) (2) a1，a2和a3分別取自

33、不同的子集A1，A2和A3中。 選法的種數(shù)為C(334,1)C(333,1)C(333,1) 由加法規(guī)則知，符合題意的選法種數(shù)為 C(334,3)+2C(333,3)+334*333 *333,例3,定義1.5 從重集B=k1b1,k2b2,knbn中選取r個元素不考慮次序組合起來，稱為從B中取r個元素的重復(fù)組合。 F(n,r),定理1.6 B=b1,b2,bn的r組合數(shù)為 F(n,r)= C(n+r-1,r ) (1.11) 證明 ：設(shè)n個元素b1，b2，bn和自然數(shù)1，2，n一一對應(yīng) 于是所考慮的任何組合便可看成是一個r個數(shù)的組合c1,c2,cr?？烧J(rèn)為各ci是按大小次序排列的，相同的ci

34、 連續(xù)地排在一起。如按c1c2cr排列。,重復(fù)組合,令di=ci+i-1(i=1,2,r)即 d1=c1, d2=c2, ,dr=cr+r-1。 由于ci最大可取n，故di最大可取n+r-1，這樣就得到一個集合1,2,n+r-1的r組合d1, d2, dr (d1d2dr) 易見有一種c1,c2,cr的取法便有一種d1,d2,dr的取法。而這兩種取法有一一對應(yīng)關(guān)系，從而這兩個組合計數(shù)問題是等價的。,這樣一來，允許重復(fù)的從n個不同元素中取r個元素的組合數(shù)和不允許重復(fù)的從n+r-1個不同元素中取r個元素的組合數(shù)是相同的。故有 F(n,r)=C(n+r-1,r) 注意：在定理1.6中，如果B的不同元素的重復(fù)數(shù)至少是r，則結(jié)論仍成立。,某餐廳有7種不同的菜，為了招待朋友，一