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

二、組合 與排列不同，組合是研究無次序的選取問題。 定義：從 n個不同元素中無次序地選取 k個，叫做從 n個元素中選 k個的一個 組合。記 或 其中 中 C是 Combination的第一個字母， 而 是 Andreas Von Ettingelausen(17961876)發(fā)明的 排列與組合的關系： （ 1） 由（ 1）可推出組合數(shù)的兩個基本恒等式： (i) (ii) 另外，還約定： 當 kn及 k-6,y-6,z-6也就是相當于 x+50, y+50, z+50. 即原方程化為 (x+5)+(y+5)+(z+5)=16 所以原問題化為 u + v + w=16 即 （個） 例 在 1與 106之間，有多少個整數(shù)的各位數(shù)字之和等于 9？ 解： 只要將問題設想為將 9個無區(qū)別的球隨意放入 6個不同的 盒子。即 3CC 131 113 1 53CCC 218161816 1163 2 0 0 2CC 5149 1-69 鴿籠原理或抽屜原理 （ 簡介 ） 我們在討論重排列時 ， 如將問題化為：設盒子是有區(qū)別的 ， 每個盒子的容量不限 ， 而且球數(shù) k盒數(shù) n， 現(xiàn)計算無空盒出現(xiàn) 的情況數(shù)目 。 假設要用 n-1塊隔板 ， 將排成一行的 k個球隔成 n段 ， 但任意 兩塊隔板不能相鄰 ， 否則就要出現(xiàn)空盒 ， 同理隔板也不能出現(xiàn) 在兩端 。 所以相當于要自 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名 。 問有多少種組成方式 ？ 解：設有 10個無區(qū)別的球與 8個不同的盒子 ， 不能出現(xiàn)空盒 ， 即 1n 1kC 1540CC 32214 123 36CCC 297918 110 補充例子 某市有 n所中學，第 i所中學派出 ci名學生 (1 ci 39， 1in)來到體育 館看球賽，全部學生總數(shù)為 ，看臺上每一橫排有 199個座位， 要求同一學校的學生必須坐在同一橫排，問體育館最少要安排多少橫排才 能保證全部學生都能坐下？ 解：首先證明，只要安排 12個橫排即可滿足。 由于 ci只有有限個， ci的有限和也是有限個，選取其中最接近 199的有限 和，設為 ci1 + ci2 + + ci k ，即使 x1=199-(ci1 + ci2 + + ci k) min 讓這 些學生坐在第一排，則 x1便是第一排中的空位數(shù)。于是對 j i1， ， ik 的所有 j均應有 cj x1+1（否則第一排又可排下一個 cj）。我們可斷言必然 有 x1 32。事實上，反證之，若 x1 33，則對所有其余 cj，應有 cj 34， 從中任取 5個學校，不妨設為 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的最小性矛盾。 1 9 9 9cn 1i i 從所有其余的 cj中選取 cj1+cj2+ +cj t 使其最接近 199，讓這些學生坐在 第二排。 令 x2=199 ( cj1+cj2+ +cj t ) 同理可證 x2 32 對于第 3排、第 4排、 、第 i排依次如此去做。 當安排好第 i 排后，令 x i 表示第 i 排的空位數(shù)，則只要剩下的學校不少 于 5所，便一定有 x i 32，推理同前。 如果在安排完 11排后，學生已坐完，則問題得證。 如果還未坐完，則可分為兩種情況： 一是余下學校不足 5所，由于 4x39<199，則其余學生可坐第 12排； 如果余下的學校不少于 5所，則仍有 x11 32，這樣前 11排至少坐 11 x (199-32)=1837個學生，余下的學生不多于 162個，自然可坐在第 12 排上。 例 將邊長為 n的一個正方形分成 n x n個個單位正方形，相當于畫成一個圍 棋盤，棋盤中當然能數(shù)出許多矩形來。按慣例，稱矩形的短邊為寬，長邊 為長，并把正方形也算作矩形。證明：棋盤中有 23個寬 n-1的矩形， 33個寬 n-2的矩形， ， n3個寬 1的矩形，并由此導出公式 證： 數(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 22333 1)(nn 4 1n21 2)(k1)(k 2 1 1 ) )(kk21 ) ( 1(k 1)1 ) ( l(k 2 k 0l 2)(k1)(k21 2 另一方面，棋盤中任意兩條橫向直線和任意兩條縱向直線都可以界得一個 矩形。于是由乘法原理知棋盤中共有 個矩形。綜合兩方面得： *例 n個人參加同一會議，其中每兩個互不認識者都恰好有兩個共同的熟 人，每兩個熟人卻都沒有共同的認識者。證明：每一個與會者都有相同數(shù) 目的熟人。 解：設與會者甲有 m位熟人 a1， a2， ， am，由于他們都同甲熟悉，所以 他們互不認識。（ 為什么？）（因為其中任一個與甲為熟人，故沒有共同 熟人，所以他們互不認識） 既然他們都互不認識，所以他們中每兩個人 (ai ， aj)除甲外都還有另一個共同的熟人，這些熟人當然都不認識甲 （為什 么？因為如果有人認識甲，則甲的熟人為 m+1，不是 m了） 。另外，對于 不同的 (ai ， aj)，另一熟人也互不相同。于是 2 1n2 1n CC 22 2 2 1n 2 1n 333 1)(nn 4 1 2 1) n(nCCn21 知與會者中不認識甲的人不會少于 。但另一方面，每個不認識甲的人 同甲一道都有兩個共同的熟人，這些人既然都認識甲，所以都在 a1， a2， ， am之列，而且對于不同的不認識甲的人。這兩個共同的熟人 (ai ， aj)也不會全然相同 （為什么？如果有相同，則甲與不認識者就有多于 2個共同熟人） 。因此可得，不認識甲的人不會多于 個。綜上所述得， 與會者中恰有 個不認識甲的人。這樣一來，參加的總?cè)藬?shù) n便應滿足 等式 考察這個關于 m的正整數(shù)二次方程，發(fā)現(xiàn)它只有唯一的正數(shù)根。所以對于 每個與會者，他的熟人數(shù)目 m為常數(shù)。 （負值舍去） 唯一 2mC 2mC 2mC 1)m ( m21m1Cm1n 2m 2 11)(n81 m 2 1)8( n11 m 01)2( nmm01)(n 2 m 2 m 22