組合數(shù)學(xué)課件

1、1組合數(shù)學(xué)組合數(shù)學(xué)西北工業(yè)大學(xué)附屬中學(xué)焦和平2一概論一概論 34二、數(shù)學(xué)競(jìng)賽中的主要問(wèn)題二、數(shù)學(xué)競(jìng)賽中的主要問(wèn)題p1組合數(shù)學(xué)中的存在性問(wèn)題組合數(shù)學(xué)中的存在性問(wèn)題p11抽屜原理抽屜原理 抽屜原理是一件簡(jiǎn)單明了的事實(shí)：n+1個(gè)物品放入n個(gè)抽屜中，則至少有一個(gè)抽屜，其中有兩個(gè)或更多的物品。 一般地：m個(gè)物品放入n個(gè)抽屜中，則至少有一個(gè)抽屜不少于a個(gè)，其中,|1,|mn mnamnnm5抽屜原理抽屜原理p一般地：m個(gè)物品放入n個(gè)抽屜中，則至少有一個(gè)抽屜不少于a個(gè)，其中,|1,|mn mnamnnm67?O?A8 2 29 152 152232766 11992 19932005S ,BA CA BC

2、BC ,BBCCBC1011 利用討論“極端”對(duì)象來(lái)實(shí)現(xiàn)問(wèn)題解決的解題方法稱為用極端原理解題，常用的極端原理基于下述簡(jiǎn)單的事實(shí)： 1）由實(shí)數(shù)組成的有限集合，必有一個(gè)最大數(shù)，也有一個(gè)最小數(shù)。 2）由自然數(shù)組成的任何非空集合中，必有一個(gè)最小的自然數(shù)。 為了肯定或否定組合數(shù)學(xué)問(wèn)題的存在性，極端原理有著重大的作用。考察極端情況，討論極端對(duì)象，無(wú)形中給問(wèn)題的討論增加了一個(gè)條件，所以更有利于問(wèn)題的解決；用反證法時(shí)，討論極端情況，使矛盾更容易暴露。12 ?m?P?C?A?B1314 .?B?D?C?A?E151.3 構(gòu)造法和不變性原理構(gòu)造法和不變性原理16 ?R?G?B?G?B?G?B?G1718p證明：充

3、分性：可用構(gòu)造法作出，如圖，正方形可剖分成6個(gè)鈍角三角形，又任一鈍角三角形總可分成兩個(gè)鈍角三角形。 必要性：先找出任意鈍角三角形剖分中不變的關(guān)系。 對(duì)剖分法的剖分點(diǎn)進(jìn)行分類(lèi)：在正方形邊界上的剖分點(diǎn)或在某一剖分三角形邊上但不是該三角形頂點(diǎn)的內(nèi)剖分點(diǎn)稱為第一類(lèi)剖分點(diǎn)；不在三角形邊上的內(nèi)剖分點(diǎn)稱為第二類(lèi)剖分點(diǎn)。如圖中F，G，H為第一類(lèi)剖分點(diǎn)，E為第二類(lèi)剖分點(diǎn)。?B?C?A?D?E?F?G?H1920（2）任意凸四邊形（各種情形）可剖分成鈍角三角形（銳角三角形）的充要條件又各是什么？ 212組合數(shù)學(xué)中的計(jì)數(shù)問(wèn)題組合數(shù)學(xué)中的計(jì)數(shù)問(wèn)題p21 加法原理和乘法原理加法原理和乘法原理p加法原理：設(shè)事件加法原理：

4、設(shè)事件A有有m種選取方式，事件種選取方式，事件B有有n種選取種選取方式，事件方式，事件A和事件和事件B沒(méi)有共同選取方式，則選沒(méi)有共同選取方式，則選A或選或選B有有m+n種方式。種方式。p乘法原理：設(shè)事件乘法原理：設(shè)事件A有有m種選取方式，事件種選取方式，事件B有有n種選取種選取方式，則選取方式，則選取A以后再選以后再選B共有共有mn種方式。種方式。p 2223242.2 映射與計(jì)數(shù)映射與計(jì)數(shù)25 26 ?A4?A2?A5?A3?A1?A6?A4?A1?A3?A2?A52728 2912kxxxn12( ,)kx xx12kxxxn111knn kn kCC 111knn kn kCC 3023

5、容斥原理容斥原理31例例18.18.一個(gè)學(xué)校只有3門(mén)課程：數(shù)學(xué)、物理、化學(xué)，已知修這3門(mén)課程的學(xué)生分別有170、130、120人；同時(shí)修數(shù)學(xué)、物理兩門(mén)課的學(xué)生有45人；同時(shí)修數(shù)學(xué)、化學(xué)兩門(mén)課的學(xué)生有20人；同時(shí)修物理、化學(xué)兩門(mén)課的學(xué)生有22人；同時(shí)修三門(mén)課的學(xué)生有3人。問(wèn)這個(gè)學(xué)校共有多少學(xué)生？32例例19. 求a，b，c，d，e，f這六個(gè)字母的全排列中不允許出現(xiàn)ace和df圖像的排列數(shù)。33343536 21,nijMMrijr 12121,kniiikMMMrkiiir同理3738練習(xí)題1給定2003個(gè)集合，每個(gè)集合都恰含有44個(gè)元素，并且每?jī)蓚€(gè)集合都恰有一個(gè)公共元素，試求這2003個(gè)集合的

6、并集中有多少個(gè)元素？2平面內(nèi)給定200個(gè)不同的點(diǎn)，證明：其中距離為單位長(zhǎng)的點(diǎn)對(duì)數(shù)小于2050。3以正n邊形的頂點(diǎn)為頂點(diǎn)的梯形共有多少個(gè)？39雜雜 題題40 例例1 1 運(yùn)動(dòng)會(huì)開(kāi)了n天（n1）,共發(fā)出m個(gè)獎(jiǎng)牌,第一天發(fā)出1個(gè)加余下獎(jiǎng)牌的,第二天發(fā)出2個(gè)加余下獎(jiǎng)牌的,如此繼續(xù)下去,最后,第n天發(fā)出n個(gè)獎(jiǎng)牌恰無(wú)剩余.問(wèn)運(yùn)動(dòng)會(huì)共開(kāi)了幾天?共發(fā)出多少個(gè)獎(jiǎng)牌?414243例例2 4445p例例4. 甲乙兩人在畫(huà)有個(gè)方格的正方形場(chǎng)地上做游戲:甲先在場(chǎng)地中央畫(huà)一個(gè)星號(hào),乙則在放有星號(hào)的格子周?chē)?個(gè)格子中任選1個(gè)方格畫(huà)一個(gè)圓圈.然后甲再在某個(gè)與已畫(huà)有標(biāo)記的格子挨著的空格中畫(huà)一個(gè)星號(hào),并一直繼續(xù)下去.如果甲成功

7、地將星號(hào)畫(huà)入場(chǎng)地四角的任何一個(gè)角上的方格中,就算他獲勝.求證:不論乙怎么做,甲總可以獲勝.46例例5.5.在33的正方形表格中填上如圖所示的9個(gè)數(shù)字,將該表進(jìn)行如下操作:每次操作是對(duì)表中相鄰兩數(shù)同時(shí)加上一個(gè)數(shù)(相鄰是指有公共邊的兩小格),問(wèn)能否經(jīng)過(guò)若干次操作使得（1）表格中各數(shù)均為0；（2）表格中四個(gè)角的數(shù)為1,其余均為0.03267049547解答:(1) 能夠得到.事實(shí)上經(jīng)過(guò)5次操作即可.03267049501067049501067005501067000001001000000000000048(2) 考慮這種操作的一般形式:abcdefghk為此,設(shè)表格中第一行的數(shù)從左到右為a,b,

8、c.第二行的數(shù)從左到右為d,e,f. 第三行的數(shù)從左到右為g,h,k.按操作規(guī)則,任意相鄰的數(shù)都加同一個(gè)數(shù),因此操作的每一步均不改變S=(a+c+e+g+k)-(b+d+h+f)的值.而表格的初始狀態(tài)S的值為S=(0+2+7+4+5)-(3+6+9+0)=0要達(dá)到的狀態(tài)S的值為S=(1+1+0+1+1)-(0+0+0+0)=4因此不能實(shí)現(xiàn)滿足題目要求的操作.abcdefghk49例例6.凸n邊形的任意3條對(duì)角線不相交于形內(nèi)一點(diǎn)，求這些對(duì)角線將凸n邊形分成的區(qū)域的個(gè)數(shù). 505152解法 3：設(shè)凸 n 邊形被對(duì)角線分成的區(qū)域數(shù)為 S，加上凸 n 邊形外的區(qū)域，共有 F=S+1 個(gè)區(qū)域，相當(dāng)一個(gè)凸

9、 F 面體，它的頂點(diǎn)數(shù)為4nVCn，又設(shè)它的邊數(shù)為 E，則從凸 n 邊形內(nèi)每一交點(diǎn)處出發(fā)有 4條邊，共44nC條邊，另外，從凸 n 邊形每一頂點(diǎn)出發(fā)有 n-3 條對(duì)角線上的線段，故從 n 個(gè)頂點(diǎn)出發(fā)共有3n n條線段，但以上計(jì)算每條線段計(jì)算了 2 次，故對(duì)角線被交點(diǎn)分成的線段數(shù)為 4411432322nnCn nCn n 加上凸 n 邊形的 n 條邊得44212322nnnECn nnCC 代入歐拉（Euler）公式 V+F-E=2 得 4241121nnnSFEVCCCn 211231224nnnn 53解法 4。設(shè)凸 n 邊形被對(duì)角線分成的區(qū)域數(shù)為na于是341,4aa， 在凸 n-1 邊

10、形121nPPP基礎(chǔ)上增加一個(gè)頂點(diǎn)nP得凸 n 邊形12nPPP，則增加了個(gè)區(qū)域11nnPP P，再增加從nP出發(fā)的 n-3 條對(duì)角線，則增加的區(qū)域數(shù)應(yīng)為這 n-3 條對(duì)角線上的交點(diǎn)數(shù)441nnCC加上 n-3。 故得441131nnnnaaCCn 441125nnnaCCnn 如果約定442230,0aCC則上式當(dāng) n=3，4 時(shí)也成立，所以 442113302nnnkkkkkkaaaaCCk 42111212312224nCnnnnnn 54例例7.已知平面上有4條直線,其中任何兩條都相交,任何三條都不交于一點(diǎn),于是在每條直線上都交得3個(gè)交點(diǎn),它們從直線上截出兩條線段,共得到8條線段.問(wèn)這

11、8條線段的長(zhǎng)度能否分別為 (1) 1,2,3,4,5,6,7,8? (2) 互不相同的自然數(shù)? ?E?A?C?F?D?B55（2）8條線段的長(zhǎng)度可以是互不相同的自然數(shù)，見(jiàn)圖。?27?24?10?6?21?8?30?1856例例8.一袋花生共1988顆,一只猴子第一天拿走一顆花生,從第二天起,每天拿走的都是以前各天的總和.如果到某天袋里的花生少于已拿走的總數(shù)時(shí),這一天它又從拿走一顆開(kāi)始,按原定的規(guī)律進(jìn)行新的一輪.如此繼續(xù)下去,那么這袋花生被猴子拿光時(shí)是第幾天?57練習(xí)題18個(gè)小圓片分別涂有4種顏色：紅、藍(lán)、白、黑各兩個(gè)。甲乙兩人輪流把圓片放到正方體的頂點(diǎn)上，在所有的圓片都放完之后，如果正方體上存在一條棱，其兩個(gè)端點(diǎn)所放的圓片同色，則甲