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

二、組合 與排列不同，組合是研究無次序的選取問題。 定義：從n個不同元素中無次序地選取k個，叫做從n個元素中選k個的一個組合。記 或 其中 中C是Combination的第一個字母， 而 是Andreas Von Ettingelausen(17961876)發(fā)明的 排列與組合的關(guān)系： （1） 由（1）可推出組合數(shù)的兩個基本恒等式： (i) (ii) 另外，還約定：當(dāng)kn及k<0時，都有 ， ，,例1 印度人早已了解組合規(guī)律，大約在公元前六世紀(jì)的一本書就記載了如下問題：“甜、酸、咸、辣、苦、澀六味可以調(diào)出多少種味道？” 書上所附答案是：“六種單味，十五種雙味，二十種三味，十五種四味，六種五味，一種六味?！?這就是組合數(shù) 例2 公元628年寫的一本書中還有這樣一道題：“一位有經(jīng)驗的建筑師為國王建造一座雄偉的宮殿，這座宮殿有八個門，每次開一個門，或二，三， ，共有多少種不同的開門方式？” 答：255種,*例3 在一平面直角坐標(biāo)系中考慮格點（x，y），其中x，y Z 滿足1x12，1y12。將這144個格點分別染成紅、白、藍三色。證明：存在一個長方形，它的邊平行于坐標(biāo)軸，它的頂點具有相同的顏色。 證：首先這三種顏色的點中，至少有一種不少于144/3=48個，不妨設(shè)為紅 色點。設(shè)這些紅點中，縱坐標(biāo)y=j的點有mj個（1j12），則 。 又由y=j的紅點連得 條不同的線段。于是知由這些紅點至 少可以連得 應(yīng)用二次平均與 算術(shù)平均不等式得 （條）不同的平行于x軸的線段。 這些線段在x軸上投影均落在1x12中。但該區(qū)間中，由坐標(biāo)為整數(shù)的 點所連成的線段一共只有 = x12x11=66條。由此可知，上述平行于x軸的線段的投影中必有一些相互重合，而投影重合的兩線段的四個端點恰構(gòu)成一個長方形的點。它們都是紅色的，且長方形的邊分別平行于二個坐標(biāo)軸。,*例4 在平面上給定5個點，已知連結(jié)這些點的直線互不平行，互不垂直，也不重合。通過每一個點向其余4點的各條連線作垂線，這些垂線的交點最多有幾個？（不包括原來的5個點） 解：由給定的5個點可兩兩連成 =10 條線段，由其中每4點可兩兩連成 =6 條直線。因此，由每個點都應(yīng)引出6條垂線，一共有5x6=30條，如 果這些垂線中每兩條都相交，則一共可交得 =435個交點。但這些垂線是分別向10條連線引出的，每一條連線上都有3條垂線（5點中除自連的兩點外還剩3點，可向這條連線引垂線），這三條垂線互相平行沒有交點，因此要減去10 x3=30條。又由于由給定的5個點可構(gòu)成 =10個三角形，上述30條垂線恰好是這些三角形的全部高，每個三角形中的三條高線相交于同一點，因而還要減去10 x3-10=20。最后，由于經(jīng)過每個原來的點的垂線都有6條，所以還要減去 =75 。因此得這些垂線的交點最多只能有435-30-20-75=310個。 435：是5個點中每點可引6條垂線（ ）共30條垂線，其中每二條交于一點共 30：原來5點兩兩連接共10條線，每條線上有3條平行垂線沒有交點共10 x3=30 20：每個三角形中三條高交于一點，不是一般的3點，所以要 （多出來的） 75：原來從每點向其他4點所成連線的垂線交于該點不算在內(nèi)，故,例5 有兩位高一學(xué)生參加高二年級的象棋比賽，比賽時每二個棋手都要對弈一局，勝者得1分，敗者得0分，平局每人分。現(xiàn)知兩位高一學(xué)生共得8分，每位高二選手得分相等，而且都是整數(shù)。問高二有幾位選手參賽？ 解：設(shè)高二有n位選手參賽，這樣全部選手有n+2個，故賽局有 ，其中8局分數(shù)為高一生所得，其余 為高二生所得，并平分。 故有 =非負整數(shù) 即 =非負整數(shù) 如果n為奇數(shù)，則 應(yīng)為整數(shù)，從而n=7或1。但n=1不合題意，舍去。故取n=7。 如果n為偶數(shù)，則 應(yīng)為整數(shù)，故 應(yīng)為分母為2的約分數(shù)，故知n=14。,重組合 從n個不同的元素中取r個允許重復(fù)的元素而不考慮其次序時，稱為從n 個中取r個允許重復(fù)的組合，簡稱重組合。記H(n,r) or C(n+r-1) 其實這是一類放球入盒的問題。這類占位問題在統(tǒng)計物理和古典概率中 具有特別的興趣，被稱為波瑟愛因斯坦(Bossel-Einstein)統(tǒng)計模型。對 它處理需要一點特別的技巧。 這類統(tǒng)計模型可歸為：“球不可區(qū)分，盒子可區(qū)分，每盒容量不限，也就 是：要將k個相同的球放入n個不同的盒子，每盒所放球數(shù)不限，有多少種 不同的放法？” 下面推導(dǎo)它的計算公式。 既然球是相同的，所以關(guān)鍵的區(qū)別就在各個盒子中所放的球數(shù)上面。即 對不同的放法，各個盒子中所分的球數(shù)不會全部相同的，當(dāng)然，一旦各個 盒子所攤得的球數(shù)確定下來，那么一種放法也就確定下來了。因此，現(xiàn)在 的問題就歸結(jié)為任何把一字排開的k個相同的小球分成n段，然后以各段中 的球數(shù)作為相應(yīng)的盒子可攤得的球數(shù)就可以了。那么怎樣才能把排成一列 的k個小球分開成n段呢？,我們可設(shè)想有n-1塊隔板，只要把它們分別插入到小球的行列中，如圖， O O | O O O | O | | O | O O O O | O O O | O 則小球就自然地被分成n段了。（這些段中可能是空的，就是不放球之盒）于是問題歸結(jié)為：不盡相同的元素的排列k個相同的球和n-1塊相同的隔板的排列所以知這一類占位問題中一共有 種不同的放法。 （吳文虎先生所著書中，將1作為盒子，0作為球，意思是一樣的。）但 上述更直觀一點。該書中有(x+y+z)1986共有幾項？ 例 在(a1+a2+ +an)k 的展開式中有多少類不同的項？ 解：展開式中的每一項都具有 的形式，其中 反之，對于每組符合 的mi ， 均為展開式中的項。 所以有多少種將k折為非負m1，mn 的和的方式，展式中就有多少類不 同的項。這等價于將k個相同的球放入n個不同的容量不限的盒子的放法數(shù) 目，所以有 不同的項。,例 求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)=16 所以原問題化為 u + v + w=16 即 （個） 例 在1與106之間，有多少個整數(shù)的各位數(shù)字之和等于9？ 解：只要將問題設(shè)想為將9個無區(qū)別的球隨意放入6個不同的盒子。即,鴿籠原理或抽屜原理（簡介） 我們在討論重排列時，如將問題化為：設(shè)盒子是有區(qū)別的，每個盒子的容量不限，而且球數(shù)k盒數(shù)n，現(xiàn)計算無空盒出現(xiàn)的情況數(shù)目。 假設(shè)要用n-1塊隔板，將排成一行的k個球隔成n段，但任意兩塊隔板不能相鄰，否則就要出現(xiàn)空盒，同理隔板也不能出現(xiàn)在兩端。所以相當(dāng)于要自k個球之間的k-1個間隔中選出n-1個來放置隔板，如圖。O|OO|O|OOO|O|O|OOO|OO|O 所以是一個組合問題，知有 種不同情況。 例 x + y + z + w=23，有多少正整數(shù)解？ 解：與前面例子相似，但x、y、z、w不能等0。即知 有 個正整數(shù)解。 例 高三有8個班協(xié)商組成年級籃球隊，共需10名隊員，每班至少出1名。問有多少種組成方式？ 解：設(shè)有10個無區(qū)別的球與8個不同的盒子，不能出現(xiàn)空盒，即,補充例子 某市有n所中學(xué)，第i所中學(xué)派出ci名學(xué)生(1 ci 39，1in)來到體育 館看球賽，全部學(xué)生總數(shù)為 ，看臺上每一橫排有199個座位， 要求同一學(xué)校的學(xué)生必須坐在同一橫排，問體育館最少要安排多少橫排才 能保證全部學(xué)生都能坐下？ 解：首先證明，只要安排12個橫排即可滿足。 由于ci只有有限個， ci的有限和也是有限個，選取其中最接近199的有限 和，設(shè)為ci1 + ci2 + ci k ，即使 x1=199-(ci1 + ci2 + ci k) min 讓這 些學(xué)生坐在第一排，則x1便是第一排中的空位數(shù)。于是對j i1， ik 的所有j均應(yīng)有cj x1+1（否則第一排又可排下一個cj）。我們可斷言必然 有x1 32。事實上，反證之，若x1 33，則對所有其余cj，應(yīng)有cj 34， 從中任取5個學(xué)校，不妨設(shè)為c1，c2，c3，c4，c5則有 5x39=195 c1+c2+c3+c4+c5 5x34=170 =199-( c1+c2+c3+c4+c5 ) 199-170=29<32 此與x1的最小性矛盾。,從所有其余的cj中選取 cj1+cj2+cj t 使其最接近199，讓這些學(xué)生坐在第二排。 令x2=199 ( cj1+cj2+cj t ) 同理可證x2 32 對于第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所，則仍有x11 32，這樣前11排至少坐 11 x (199-32)=1837個學(xué)生，余下的學(xué)生不多于162個，自然可坐在第12 排上。,例 將邊長為n的一個正方形分成n x n個個單位正方形，相當(dāng)于畫成一個圍棋盤，棋盤中當(dāng)然能數(shù)出許多矩形來。按慣例，稱矩形的短邊為寬，長邊 為長，并把正方形也算作矩形。證明：棋盤中有23個寬n-1的矩形，33個寬 n-2的矩形，n3個寬1的矩形，并由此導(dǎo)出公式 證：數(shù)軸上以整數(shù)為端點，含于區(qū)間0，n中且長度是n-k的區(qū)間共有 k+1個，它們是0，n-k，1，n-k+1， ，k，n 。 因此，棋盤中以橫向為寬，縱向為長，且寬n-k，長n-l (l k)的矩形有 (k+1)(l+1)個。對 l 求和，即知棋盤中以橫向為寬，縱向為長，且寬n-k的矩形共有 同理，以縱向為寬，橫向為長且寬為n-k的矩形也有 個。注意 到其中長寬均為n-k的正方形有(k+1)2個，它們同時被計了上述兩個數(shù)字， 所以棋盤中寬為n-k的矩形共有(k+1)2(k+2)-(k+1)2=(k+1)3 k=1,2,n-1,另一方面，棋盤中任意兩條橫向直線和任意兩條縱向直線都可以界得一個 矩形。于是由乘法原理知棋盤中共有 個矩形。綜合兩方面得： *例 n個人參加同一會議，其中每兩個互不認識者都恰好有兩個共同的熟 人，每兩個熟人卻都沒有共同的認識者。證明：每一個與會者都有相同數(shù) 目的熟人。 解：設(shè)與會者甲有m位熟人a1，a2，am，由于他們都同甲熟悉，所以 他們互不認識。（為什么？）（因為其中任一個與甲為熟人，故沒有共同 熟人，所以他們互不認識）既然他們都互不認識，所以他們中每兩個人 (ai ，aj)除甲外都還有另一個共同的熟人，這些熟人當(dāng)然都不認識甲（為什 么？因為如果有人認識甲，則甲的熟人為m+1，不是m了）。另外，對于 不同的(ai ，aj)，另一熟人也互不相同。于是,知與會者中不認識甲的人不會少于 。但另一方面，每個不認識甲的人 同甲一道都有兩個共同的熟人，這些人既然都認識甲，所以都在 a1，a2，am之列，而且對于不同的不認識甲的人。這兩個共同的熟人 (ai ，aj)也不會全然相同（為什么？如果有相同，則甲與不認識者就有多于 2個共同熟人）。因此可得，不認識甲的人不會多于 個。綜上所述得， 與會者中恰有 個不認識甲的人。這樣一來，參加的總?cè)藬?shù)n便應(yīng)滿足 等式 考察這個關(guān)于m的正整數(shù)二次方程，發(fā)現(xiàn)它只有唯一的正數(shù)根。所以對于 每個與會者，他的熟人數(shù)目m為常數(shù)。 （負值舍去） 唯一,