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

《《組合數(shù)學(xué)算法二》PPT課件.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《《組合數(shù)學(xué)算法二》PPT課件.ppt（14頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、二、組合 與排列不同，組合是研究無次序的選取問題。 定義：從n個(gè)不同元素中無次序地選取k個(gè)，叫做從n個(gè)元素中選k個(gè)的一個(gè)組合。記 或 其中 中C是Combination的第一個(gè)字母， 而 是Andreas Von Ettingelausen(17961876)發(fā)明的 排列與組合的關(guān)系： （1） 由（1）可推出組合數(shù)的兩個(gè)基本恒等式： (i) (ii) 另外，還約定：當(dāng)kn及k<0時(shí)，都有 ， ，,例1 印度人早已了解組合規(guī)律，大約在公元前六世紀(jì)的一本書就記載了如下問題：“甜、酸、咸、辣、苦、澀六味可以調(diào)出多少種味道？” 書上所附

2、答案是：“六種單味，十五種雙味，二十種三味，十五種四味，六種五味，一種六味?！?這就是組合數(shù) 例2 公元628年寫的一本書中還有這樣一道題：“一位有經(jīng)驗(yàn)的建筑師為國(guó)王建造一座雄偉的宮殿，這座宮殿有八個(gè)門，每次開一個(gè)門，或二，三， ，共有多少種不同的開門方式？” 答：255種,*例3 在一平面直角坐標(biāo)系中考慮格點(diǎn)（x，y），其中x，y Z 滿足1x12，1y12。將這144個(gè)格點(diǎn)分別染成紅、白、藍(lán)三色。證明：存在一個(gè)長(zhǎng)方形，它的邊平行于坐標(biāo)軸，它的頂點(diǎn)具有相同的顏色。 證：首先這三種顏色的點(diǎn)中，至少有一種不少于144/3=48個(gè)，不妨設(shè)為紅 色點(diǎn)。設(shè)這些紅點(diǎn)中，縱坐標(biāo)y=j的點(diǎn)有mj個(gè)（

3、1j12），則 。 又由y=j的紅點(diǎn)連得 條不同的線段。于是知由這些紅點(diǎn)至 少可以連得 應(yīng)用二次平均與 算術(shù)平均不等式得 （條）不同的平行于x軸的線段。 這些線段在x軸上投影均落在1x12中。但該區(qū)間中，由坐標(biāo)為整數(shù)的 點(diǎn)所連成的線段一共只有 = x12x11=66條。由此可知，上述平行于x軸的線段的投影中必有一些相互重合，而投影重合的兩線段的四個(gè)端點(diǎn)恰構(gòu)成一個(gè)長(zhǎng)方形的點(diǎn)。它們都是紅色的，且長(zhǎng)方形的邊分別平行于二個(gè)坐標(biāo)軸。,*例4 在平面上給定5個(gè)點(diǎn)，已知連結(jié)這些點(diǎn)的直線互不平行，互不垂直，也不重合。通過每一個(gè)點(diǎn)向其余4點(diǎn)的各

4、條連線作垂線，這些垂線的交點(diǎn)最多有幾個(gè)？（不包括原來的5個(gè)點(diǎn)） 解：由給定的5個(gè)點(diǎn)可兩兩連成 =10 條線段，由其中每4點(diǎn)可兩兩連成 =6 條直線。因此，由每個(gè)點(diǎn)都應(yīng)引出6條垂線，一共有5x6=30條，如 果這些垂線中每?jī)蓷l都相交，則一共可交得 =435個(gè)交點(diǎn)。但這些垂線是分別向10條連線引出的，每一條連線上都有3條垂線（5點(diǎn)中除自連的兩點(diǎn)外還剩3點(diǎn)，可向這條連線引垂線），這三條垂線互相平行沒有交點(diǎn)，因此要減去10 x3=30條。又由于由給定的5個(gè)點(diǎn)可構(gòu)成 =10個(gè)三角形，上述30條垂線恰好是這些三角形的全部高，每個(gè)三角形中的三條高線相交于同一點(diǎn)，因而還要減去10 x3-10=20。最

5、后，由于經(jīng)過每個(gè)原來的點(diǎn)的垂線都有6條，所以還要減去 =75 。因此得這些垂線的交點(diǎn)最多只能有435-30-20-75=310個(gè)。 435：是5個(gè)點(diǎn)中每點(diǎn)可引6條垂線（ ）共30條垂線，其中每二條交于一點(diǎn)共 30：原來5點(diǎn)兩兩連接共10條線，每條線上有3條平行垂線沒有交點(diǎn)共10 x3=30 20：每個(gè)三角形中三條高交于一點(diǎn)，不是一般的3點(diǎn)，所以要 （多出來的） 75：原來從每點(diǎn)向其他4點(diǎn)所成連線的垂線交于該點(diǎn)不算在內(nèi)，故,例5 有兩位高一學(xué)生參加高二年級(jí)的象棋比賽，比賽時(shí)每二個(gè)棋手都要對(duì)弈一局，勝者得1分，敗者得0分，平局每人分?，F(xiàn)知兩位高一學(xué)生共得8分，每位高二選手得分

6、相等，而且都是整數(shù)。問高二有幾位選手參賽？ 解：設(shè)高二有n位選手參賽，這樣全部選手有n+2個(gè)，故賽局有 ，其中8局分?jǐn)?shù)為高一生所得，其余 為高二生所得，并平分。 故有 =非負(fù)整數(shù) 即 =非負(fù)整數(shù) 如果n為奇數(shù)，則 應(yīng)為整數(shù)，從而n=7或1。但n=1不合題意，舍去。故取n=7。 如果n為偶數(shù)，則 應(yīng)為整數(shù)，故 應(yīng)為分母為2的約分?jǐn)?shù)，故知n=14。,重組合 從n個(gè)不同的元素中取r個(gè)允許重復(fù)的元素而不考慮其次序時(shí)，稱為從n 個(gè)中取r個(gè)允許重復(fù)的組合，簡(jiǎn)稱重組合。記H(n,r) or C(n+r-1) 其實(shí)這是一類放球入盒的問題。這類占位問題在統(tǒng)計(jì)物理和

7、古典概率中 具有特別的興趣，被稱為波瑟愛因斯坦(Bossel-Einstein)統(tǒng)計(jì)模型。對(duì) 它處理需要一點(diǎn)特別的技巧。 這類統(tǒng)計(jì)模型可歸為：“球不可區(qū)分，盒子可區(qū)分，每盒容量不限，也就 是：要將k個(gè)相同的球放入n個(gè)不同的盒子，每盒所放球數(shù)不限，有多少種 不同的放法？” 下面推導(dǎo)它的計(jì)算公式。 既然球是相同的，所以關(guān)鍵的區(qū)別就在各個(gè)盒子中所放的球數(shù)上面。即 對(duì)不同的放法，各個(gè)盒子中所分的球數(shù)不會(huì)全部相同的，當(dāng)然，一旦各個(gè) 盒子所攤得的球數(shù)確定下來，那么一種放法也就確定下來了。因此，現(xiàn)在 的問題就歸結(jié)為任何把一字排開的k個(gè)相同的小球分成n段，然后以各段中 的球數(shù)作為相應(yīng)的盒子可攤得的球數(shù)就

8、可以了。那么怎樣才能把排成一列 的k個(gè)小球分開成n段呢？,我們可設(shè)想有n-1塊隔板，只要把它們分別插入到小球的行列中，如圖， O O | O O O | O | | O | O O O O | O O O | O 則小球就自然地被分成n段了。（這些段中可能是空的，就是不放球之盒）于是問題歸結(jié)為：不盡相同的元素的排列k個(gè)相同的球和n-1塊相同的隔板的排列所以知這一類占位問題中一共有 種不同的放法。 （吳文虎先生所著書中，將1作為盒子，0作為球，意思是一樣的。）但 上述更直觀一點(diǎn)。該書中有(x+y+z)1986共有幾項(xiàng)？ 例 在(a1+a2+ +an)k 的展開式中有多少類不同的項(xiàng)？

9、 解：展開式中的每一項(xiàng)都具有 的形式，其中 反之，對(duì)于每組符合 的mi ， 均為展開式中的項(xiàng)。 所以有多少種將k折為非負(fù)m1，，mn 的和的方式，展式中就有多少類不 同的項(xiàng)。這等價(jià)于將k個(gè)相同的球放入n個(gè)不同的容量不限的盒子的放法數(shù) 目，所以有 不同的項(xiàng)。,例 求x + y + z=1的整數(shù)解的數(shù)目，要求x，y，z都大于-6。 如無后面條件限制，則其解之?dāng)?shù)為 （1 0 0），（0 1 0），（0 0 1） 但加上條件后怎么辦？ 要求x-6,y-6,z-6也就是相當(dāng)于x+50, y+50, z+50. 即原方程化為 (x+5)+(y+5)+(z+5)

10、=16 所以原問題化為 u + v + w=16 即 （個(gè)） 例 在1與106之間，有多少個(gè)整數(shù)的各位數(shù)字之和等于9？ 解：只要將問題設(shè)想為將9個(gè)無區(qū)別的球隨意放入6個(gè)不同的盒子。即,鴿籠原理或抽屜原理（簡(jiǎn)介） 我們?cè)谟懻撝嘏帕袝r(shí)，如將問題化為：設(shè)盒子是有區(qū)別的，每個(gè)盒子的容量不限，而且球數(shù)k盒數(shù)n，現(xiàn)計(jì)算無空盒出現(xiàn)的情況數(shù)目。 假設(shè)要用n-1塊隔板，將排成一行的k個(gè)球隔成n段，但任意兩塊隔板不能相鄰，否則就要出現(xiàn)空盒，同理隔板也不能出現(xiàn)在兩端。所以相當(dāng)于要自k個(gè)球之間的k-1個(gè)間隔中選出n-1個(gè)來放置隔板，如圖。O|OO|O|OOO|O|O|OOO|OO|O 所以是一

11、個(gè)組合問題，知有 種不同情況。 例 x + y + z + w=23，有多少正整數(shù)解？ 解：與前面例子相似，但x、y、z、w不能等0。即知 有 個(gè)正整數(shù)解。 例 高三有8個(gè)班協(xié)商組成年級(jí)籃球隊(duì)，共需10名隊(duì)員，每班至少出1名。問有多少種組成方式？ 解：設(shè)有10個(gè)無區(qū)別的球與8個(gè)不同的盒子，不能出現(xiàn)空盒，即,補(bǔ)充例子 某市有n所中學(xué)，第i所中學(xué)派出ci名學(xué)生(1 ci 39，1in)來到體育 館看球賽，全部學(xué)生總數(shù)為 ，看臺(tái)上每一橫排有199個(gè)座位， 要求同一學(xué)校的學(xué)生必須坐在同一橫排，問體育館最少要安排多少橫排才 能保證全部學(xué)生都能坐下？ 解：首先證明，只要安排1

12、2個(gè)橫排即可滿足。 由于ci只有有限個(gè)， ci的有限和也是有限個(gè)，選取其中最接近199的有限 和，設(shè)為ci1 + ci2 ++ ci k ，即使 x1=199-(ci1 + ci2 ++ ci k) min 讓這 些學(xué)生坐在第一排，則x1便是第一排中的空位數(shù)。于是對(duì)j i1，， ik 的所有j均應(yīng)有cj x1+1（否則第一排又可排下一個(gè)cj）。我們可斷言必然 有x1 32。事實(shí)上，反證之，若x1 33，則對(duì)所有其余cj，應(yīng)有cj 34， 從中任取5個(gè)學(xué)校，不妨設(shè)為c1，c2，c3，c4，c5則有 5x39=195 c1+c2+c3+c4+c5 5x34=170 =199-( c1+c2

13、+c3+c4+c5 ) 199-170=29<32 此與x1的最小性矛盾。,從所有其余的cj中選取 cj1+cj2++cj t 使其最接近199，讓這些學(xué)生坐在第二排。 令x2=199 ( cj1+cj2++cj t ) 同理可證x2 32 對(duì)于第3排、第4排、、第i排依次如此去做。 當(dāng)安排好第 i 排后，令 x i 表示第 i 排的空位數(shù)，則只要剩下的學(xué)校不少于5所，便一定有x i 32，推理同前。 如果在安排完11排后，學(xué)生已坐完，則問題得證。 如果還未坐完，則可分為兩種情況： 一是余下學(xué)校不足5所，由于4x39<199，則其余學(xué)生可坐第12排； 如果余下的學(xué)校不少于5所，

14、則仍有x11 32，這樣前11排至少坐 11 x (199-32)=1837個(gè)學(xué)生，余下的學(xué)生不多于162個(gè)，自然可坐在第12 排上。,例 將邊長(zhǎng)為n的一個(gè)正方形分成n x n個(gè)個(gè)單位正方形，相當(dāng)于畫成一個(gè)圍棋盤，棋盤中當(dāng)然能數(shù)出許多矩形來。按慣例，稱矩形的短邊為寬，長(zhǎng)邊 為長(zhǎng)，并把正方形也算作矩形。證明：棋盤中有23個(gè)寬n-1的矩形，33個(gè)寬 n-2的矩形，，n3個(gè)寬1的矩形，并由此導(dǎo)出公式 證：數(shù)軸上以整數(shù)為端點(diǎn)，含于區(qū)間0，n中且長(zhǎng)度是n-k的區(qū)間共有 k+1個(gè)，它們是0，n-k，1，n-k+1， ，k，n 。 因此，棋盤中以橫向?yàn)閷?，縱向?yàn)殚L(zhǎng)，且寬n-k，長(zhǎng)n-l (l k)的矩形有

15、(k+1)(l+1)個(gè)。對(duì) l 求和，即知棋盤中以橫向?yàn)閷挘v向?yàn)殚L(zhǎng)，且寬n-k的矩形共有 同理，以縱向?yàn)閷?，橫向?yàn)殚L(zhǎng)且寬為n-k的矩形也有 個(gè)。注意 到其中長(zhǎng)寬均為n-k的正方形有(k+1)2個(gè)，它們同時(shí)被計(jì)了上述兩個(gè)數(shù)字， 所以棋盤中寬為n-k的矩形共有(k+1)2(k+2)-(k+1)2=(k+1)3 k=1,2,,n-1,另一方面，棋盤中任意兩條橫向直線和任意兩條縱向直線都可以界得一個(gè) 矩形。于是由乘法原理知棋盤中共有 個(gè)矩形。綜合兩方面得： *例 n個(gè)人參加同一會(huì)議，其中每?jī)蓚€(gè)互不認(rèn)識(shí)者都恰好有兩個(gè)共同的熟 人，每?jī)蓚€(gè)熟人卻都沒有共同的認(rèn)識(shí)者。證明：每一個(gè)與會(huì)者

16、都有相同數(shù) 目的熟人。 解：設(shè)與會(huì)者甲有m位熟人a1，a2，，am，由于他們都同甲熟悉，所以 他們互不認(rèn)識(shí)。（為什么？）（因?yàn)槠渲腥我粋€(gè)與甲為熟人，故沒有共同 熟人，所以他們互不認(rèn)識(shí)）既然他們都互不認(rèn)識(shí)，所以他們中每?jī)蓚€(gè)人 (ai ，aj)除甲外都還有另一個(gè)共同的熟人，這些熟人當(dāng)然都不認(rèn)識(shí)甲（為什 么？因?yàn)槿绻腥苏J(rèn)識(shí)甲，則甲的熟人為m+1，不是m了）。另外，對(duì)于 不同的(ai ，aj)，另一熟人也互不相同。于是,知與會(huì)者中不認(rèn)識(shí)甲的人不會(huì)少于 。但另一方面，每個(gè)不認(rèn)識(shí)甲的人 同甲一道都有兩個(gè)共同的熟人，這些人既然都認(rèn)識(shí)甲，所以都在 a1，a2，，am之列，而且對(duì)于不同的不認(rèn)識(shí)甲的人。這兩個(gè)共同的熟人 (ai ，aj)也不會(huì)全然相同（為什么？如果有相同，則甲與不認(rèn)識(shí)者就有多于 2個(gè)共同熟人）。因此可得，不認(rèn)識(shí)甲的人不會(huì)多于 個(gè)。綜上所述得， 與會(huì)者中恰有 個(gè)不認(rèn)識(shí)甲的人。這樣一來，參加的總?cè)藬?shù)n便應(yīng)滿足 等式 考察這個(gè)關(guān)于m的正整數(shù)二次方程，發(fā)現(xiàn)它只有唯一的正數(shù)根。所以對(duì)于 每個(gè)與會(huì)者，他的熟人數(shù)目m為常數(shù)。 （負(fù)值舍去） 唯一,