《組合數(shù)學(xué)算法一》PPT課件.ppt

一、引言中國(guó)是最早研究排列組合的國(guó)家。周易就被認(rèn)為是世界上最早討論排列組合的書，其中的八卦和六十四卦陣，就屬于重復(fù)排列問(wèn)題。我國(guó)的洛書有“幻方”的最早記載，幻方是組合數(shù)學(xué)中構(gòu)造問(wèn)題之例，據(jù)說(shuō)“河圖”就是一種幻方。歷史走著曲折的道路。一些歷史悠久的學(xué)科，在經(jīng)歷了漫長(zhǎng)的不被人們重視的歲月之后，又會(huì)重新煥發(fā)出青春的活力。組合數(shù)學(xué)的歷史就是如此。它同算術(shù)、代數(shù)、幾何一樣古老，源遠(yuǎn)流長(zhǎng)，但卻沒(méi)有它們那種持續(xù)不斷的發(fā)展歷程。這不能歸咎于它的衰老，而只能解釋成歷史的青睞尚未到來(lái)。歷史是公正的，人類創(chuàng)造的每一項(xiàng)偉績(jī)都不至于被遺忘。近幾十年來(lái)，這門古老的學(xué)科年輕了，活躍起來(lái)了，開(kāi)始以前所未有的速度向前發(fā)展著，不斷取得豐富的成果。促使這種變化出現(xiàn)的最主要?jiǎng)恿κ嵌兰o(jì)的計(jì)算機(jī)科學(xué)的迅速發(fā)展。計(jì)算機(jī)科學(xué)，數(shù)字通訊理論，規(guī)劃論和試驗(yàn)設(shè)計(jì)都要求人們把注意力轉(zhuǎn)向研究離散變量的數(shù)學(xué)學(xué)科，其中之一便是組合數(shù)學(xué)。這種來(lái)自尖端學(xué)科領(lǐng)域的刺激的出現(xiàn)，激起了這門古老學(xué)科領(lǐng)域中從未有過(guò)的發(fā)展勢(shì)頭，使它一反長(zhǎng)期沉睡的狀態(tài)，成為本世紀(jì)最活躍的數(shù)學(xué)學(xué)科之一。,二、排列組合全部組合分析公式的推導(dǎo)基于以下兩原理,（一）加法原理如果完成一件事情有n種方式A1，An，每種方式中又有mi種方法（1in），且AiAj=，則要完成此事共有一年365天劃分為12個(gè)月一個(gè)國(guó)家劃分一些省一個(gè)班分為幾個(gè)小組例1離開(kāi)福州，飛機(jī)有60個(gè)航班，火車有10個(gè)車次，輪船有2個(gè)班次，汽車有100個(gè)班次。離開(kāi)福州的方式有60+10+2+100=172,加法原理的例子補(bǔ)充|A|，|B|分別為集合A，B中元素的個(gè)數(shù)補(bǔ)例1現(xiàn)有長(zhǎng)度分別為1，2，n的細(xì)木棍各一根，可以以它們?yōu)檫厴?gòu)成多少個(gè)不同的三角形？解：記三角形三邊長(zhǎng)度為a，b，c，不妨設(shè)ac。以c的長(zhǎng)度將這些三角形分類，則可分為c=4，c=5，c=n這樣一些不同的類，分別將各類三角形的集合記作B4，B5，Bn，則它們構(gòu)成了所有三角形的集合B的一個(gè)分劃，則有而在Bk中，三角形三邊分別為ak，所以這些點(diǎn)由a=b，a+b=k，b=k三條直線所圍成的三角形區(qū)域內(nèi)部。所以當(dāng)k為偶數(shù)時(shí)，有當(dāng)k為奇數(shù)時(shí)，有所以n為偶數(shù)時(shí)，n為奇數(shù)時(shí)，,補(bǔ)例2設(shè)x表示不超過(guò)實(shí)數(shù)x的最大整數(shù)。求方程x2-x2=(x-x)2在區(qū)間1xn中根的個(gè)數(shù)。解：顯然x=n是方程的一個(gè)根。下面我們?cè)俜謩e求出方程在區(qū)間1x<2，2x<3，n-1x<n中的根的個(gè)數(shù)。為此設(shè)這些區(qū)間中根的個(gè)數(shù)為B1，B2，Bn-1，即以Bk表示方程在區(qū)間kx<k+1中根的全體。在kx<k+1中，有x=k，如果再記p=x-x，就有0p<1。于是原來(lái)方程就可以寫成(k+p)2-(k+p)2=p2即k2+2kp=k2+2kp+p2注意到k2+2kp+p2=k2+2kp+p2知上式即為2kp=2kp+p2該式右端是一個(gè)整數(shù)，所以左端也應(yīng)為整數(shù)，即2kp是整數(shù)由于k為整數(shù)，0p<1，所以只有當(dāng)p=0，1/2k，2/2k，(2k-1)/2k時(shí)，等式才能成立。從而知原方程在此區(qū)間中恰有2k個(gè)根，即|Bk|=2k于是由加法原理知原方程在區(qū)間1xn中共有|B1|+|B2|+|Bn-1|+1=2+4+2(n-1)+1=n2-n+1個(gè)根加法原理用途極多，如將其與其他數(shù)學(xué)原理，例如抽屜原理結(jié)合起來(lái)，就可以推出許多有趣的數(shù)學(xué)命題。,（二）乘法原理如果完成一件事情要分幾個(gè)步驟B1，B2，Bn，而每個(gè)步驟Bi有mi種方法(1in)，那么完成這事共有例2某人在進(jìn)小學(xué)、初中、高中時(shí)都分別有二所學(xué)?？蛇x擇，那么他就有多種不同的方式從小學(xué)到高中。共8種=2x2x2例3多項(xiàng)式乘積(a1+a2+a3)(b1+b2+b3+b4)(c1+c2+c3+c4+c5+c6)(d1+d2)的展開(kāi)式中有多少不同的項(xiàng)。解：展式中每項(xiàng)均形如aibjckdl，其中i1,2,3，j1,2,3,4，k1,2,3,4,5,6，l1,2由乘法原理，展式中共有3x4x6x2=144（項(xiàng)）例4在ABC的三邊上分別取n1，n2，n3個(gè)點(diǎn)（不含A,B,C），在三邊上的點(diǎn)中各取一個(gè)作為三角形的頂點(diǎn)，可以得到多少個(gè)不同的三角形？n1n2n3,*例5每個(gè)完全平方數(shù)都有奇數(shù)個(gè)正約數(shù)證：設(shè)n=m2是一個(gè)完全平方數(shù)而m的素因數(shù)分解式為m=，那么n=記A1=0，1，2r1，A2=0，1，2r2，Ak=0，1，2rk那么n的每一個(gè)正約數(shù)就都具有形式其中j1A1，jkAk，故由乘法原理n一共有|A1|A2|Ak|=(2r1+1)(2r2+1)(2rk+1)個(gè)正約數(shù)共有奇數(shù)個(gè)。例6（結(jié)合程度較高的例子）一種單向行駛的汽車，滿載為25人，全程共設(shè)14個(gè)車站，中途的每一個(gè)車站均可上下乘客。由不同起點(diǎn)到達(dá)不同終點(diǎn)的乘客各應(yīng)購(gòu)買不同的車票。在一次單程行駛中，車上最多可賣出多少種不同的車票？解：車上應(yīng)準(zhǔn)備由每個(gè)車站到達(dá)它后面每一個(gè)車站的車票，所以一共應(yīng)準(zhǔn)備13+12+2+1=91（種）（加法原理之應(yīng)用）,但它們不可能在一次單程行駛中都賣得出去。我們來(lái)考慮其中以前面7個(gè)車站中的某一個(gè)作為起點(diǎn)，而以后面7個(gè)車站中的某一個(gè)作為終點(diǎn)的車票，就應(yīng)當(dāng)為7x7=49（種）之多（最多種）。凡持這種車票的乘客都要乘車通過(guò)7號(hào)車站與8號(hào)車站之間的路程。但由于汽車滿員為25人，所以此類車票中至少會(huì)有49-25=24（種）賣不出去。（即只有25人，最多只能賣出25張此類票）這樣一來(lái)，車上最多只能賣出91-24=67（種）。（三）排列1.線排列2.圓排列3.重排列1.線排列（排列）排列的字面意思是列隊(duì)?！白罨尽崩泳褪牵骸耙獜膎個(gè)不同的物體中選出k件（1kn）來(lái)排成一列，共有多少種不同的排法？”高中數(shù)學(xué)課本中就以此為排列的定義基礎(chǔ)。稱“從n個(gè)不同元素中，任取k（kn）個(gè)元素按照一定的順序排成一列，叫做從n個(gè)不同元素中取出k個(gè)元素的一個(gè)排列?！保淳€排列）,其實(shí)這種定義有一定的局限性，容易使人誤將“排成一列”理解為排列問(wèn)題的本質(zhì)。最早研究排列問(wèn)題的國(guó)家是印度，早年出現(xiàn)在印度書籍中的例子有：濕婆神的十只手拿十件東西：繩子、鉤子、蛇、鼓、豆蓋骨、三叉戟、樂(lè)架、匕首、箭、弓。這十件東西是她的象征物，如果將這十種東西交換，共有多少種不同的方式？正象哈利神四只手交換狼牙棒、鐵餅、蓮與貝殼一樣。這里濕婆神的十只手和哈利神的四只手都不是成一列分布，而是分布在軀干的兩側(cè)的，所以所拿的東西都不是“按一定的順序排成一列”?，F(xiàn)解決一開(kāi)始提出的問(wèn)題。先從n個(gè)物體中任取一個(gè)放在排首，有n種不同選法。再?gòu)挠嘞碌膎-1個(gè)中選出一個(gè)來(lái)放在排二，有n-1種。這樣逐個(gè)選出，直到n-k+1個(gè)物體中選出一個(gè)放在排尾，有n-k+1種不同方法。由乘法原理，有n(n-1)(n-k+1)=為約定符號(hào)人們通常把n(n-1)21記為n！,現(xiàn)代組合學(xué)中對(duì)排列下了一個(gè)更為妥當(dāng)?shù)亩x：從n個(gè)不同元素中有次序地選取k（1kn）個(gè)，叫做從n個(gè)不同元素中取出k個(gè)元素的一個(gè)排列。又當(dāng)k=n時(shí)，就叫做一個(gè)全排列。有人們又規(guī)定0！=1容易的大家都知道了計(jì)算。例把自然數(shù)1，2，k2排成一個(gè)方陣表。從表中任意取一個(gè)數(shù)，然后刪去這個(gè)數(shù)所在的行和列中的全部數(shù)字，再?gòu)氖Ｏ碌?k-1)2個(gè)數(shù)組成的方陣表中任意取出一個(gè)數(shù)，并刪去這個(gè)數(shù)所在的行和列中的所有數(shù)字。這樣一直進(jìn)行下去，一共可取表中k個(gè)不同的數(shù)字，它們構(gòu)成了集合1，2，k2的一個(gè)k階子集。問(wèn)題是：用這樣的方法，共可取得1，2，k2中多少個(gè)不同的由k個(gè)數(shù)字組成的子集？這些子集中的k個(gè)數(shù)字之和各是多少？12kk+1k+22k(k-1)k+1(k-1)k+2k2,解：因?yàn)橐坏┤〉靡粋€(gè)數(shù)字后，這個(gè)數(shù)字所在行與列即劃之，所以所取得的k個(gè)數(shù)字中，不可能有兩個(gè)同行的，也不可能同列。換言之，即k個(gè)數(shù)字都是取自不同行也不同列，故有k！個(gè)。又因?yàn)閍ij=(i-1)k+j，而每個(gè)子集中k個(gè)數(shù)字中都包含每一行，每一列的數(shù)字各一個(gè)，所以每個(gè)子集中k個(gè)數(shù)字之和均為,2.圓排列從集合S=a1，an的n個(gè)不同元素中取出r個(gè)元素，按某種次序（如逆時(shí)針?lè)较颍?，排成一個(gè)圓圈，稱這樣的排列為圓排列。這里相同的順序被視同一排列。如：這種圓排列的個(gè)數(shù)=如果r=n，則例：4對(duì)兄弟站成一圈，要求每對(duì)兄弟相鄰，有多少種不同站法？解：先讓哥哥站一圈，有=3！=6（種）不同排法。然后，讓4位弟弟插入其中，每人均可在其兄左邊亦可右邊，故均有2種方式。所以共有6x2=96（種）*例：用4種不同顏色給小正方形木塊的4條邊著色，每邊各涂一種顏色，能有多少種不同的著色花樣？解：此處不僅只考慮4種顏色的相對(duì)順序，而且木塊可以翻邊，因此沒(méi)有逆時(shí)針順序與順時(shí)針順序的不同區(qū)分。故一共有=3種。,A,B,=,D,C,D,A,B,C,*例：在右圖的圓周上均勻地布列著n個(gè)方框。今有n個(gè)非零實(shí)數(shù)a1，a2，an滿足a1+a2+an=0，要將它們分別填入圓周上的n個(gè)方框。證明：至少有(n-1)！種填法可以使得自某個(gè)方框A開(kāi)始按逆時(shí)針?lè)较?，逐個(gè)累加方框中的數(shù)字，得出的每一步和數(shù)都非負(fù)。證：設(shè)已將n個(gè)數(shù)字填入方框，并且自A開(kāi)始按逆時(shí)針依次填入ai1，ai2，ain?，F(xiàn)來(lái)逐個(gè)累加它們得到S1=ai1，S2=ai1+ai2，Sn=ai1+ai2+ain。如果這些S1，Sn0，則相應(yīng)的填法合乎要求。如果S1，Sn中有負(fù)數(shù)，則只要將所填數(shù)字集體順時(shí)針旋轉(zhuǎn)若干位置，即可得合乎要求的填法?，F(xiàn)證之。設(shè)Sk=min(S1，Sn)，Sk<0,A,ai1,ai2,由于Sk的最小性，知這就是說(shuō)，只要將所填數(shù)字集體順時(shí)針旋轉(zhuǎn)后，使得方框A中的數(shù)字變成aik+1（保持各數(shù)間原來(lái)的相對(duì)順序），即可使得自A中數(shù)字開(kāi)始，按逆時(shí)針?lè)较蛑饌€(gè)累加數(shù)字，所得出的每一步和數(shù)均非負(fù)。以上證明的事實(shí)表明，無(wú)論按什么樣的相對(duì)順序?qū)?shù)填入方框，都可通過(guò)整體旋轉(zhuǎn)這些數(shù)而得到一種合乎要求的填數(shù)方式，且保持?jǐn)?shù)的相對(duì)順序不變。于是可以斷言，合乎要求的填法數(shù)目不會(huì)少于這n個(gè)數(shù)字進(jìn)行圓排列的數(shù)目，即(n-1)！種。,3.重排列重排列即一個(gè)依次進(jìn)行的多重選取過(guò)程，并且每一重選取都在一個(gè)集合中進(jìn)行，已經(jīng)選過(guò)的元素還可再選。（這是對(duì)乘法原理的最直接應(yīng)用）重復(fù)排列的最簡(jiǎn)單例子是電話號(hào)碼，某市的電話號(hào)碼是7位，每位上的數(shù)碼無(wú)非是0，1，9，而且不同位上的數(shù)碼可以是相同的。如7566783，7533338，7818888，共有107種以上是無(wú)限重排列中國(guó)是世界上最早討論重排列的國(guó)家，易經(jīng)中所收集的資料可以追溯到公元前七世紀(jì)。易經(jīng)中有兩個(gè)符號(hào)，叫做“陽(yáng)爻”和“陰爻”，易經(jīng)討論了由這樣兩個(gè)符號(hào)形成的3個(gè)字符和6個(gè)字符的所有可能情況。其中3個(gè)字符是：陽(yáng)陽(yáng)陽(yáng)、陽(yáng)陽(yáng)陰、陽(yáng)陰陽(yáng)、陰陽(yáng)陽(yáng)陽(yáng)陰陰、陰陽(yáng)陰、陰陰陽(yáng)、陰陰陰這剛好是由集合陽(yáng)，陰中依次進(jìn)行的3重選取過(guò)程的所有可能情況?；蛘呓凶鲇申?yáng)、陰二者中每次選取3個(gè)重復(fù)排列的所有情況。由于其數(shù)目共2x2x2=8（個(gè)），故易經(jīng)稱之曰“八卦”。相應(yīng)的六個(gè)字符的共有26=64（種），稱為“六十四卦”。例公元八世紀(jì)，我國(guó)流傳過(guò)一個(gè)問(wèn)題，據(jù)說(shuō)是一個(gè)和尚提出的：圍棋盤上有361個(gè)位置，既可放黑子，或白子，又可空著，共有多少種不同的情況。3361（種）,