《《組合數(shù)學(xué)算法》PPT課件.ppt》由會員分享，可在線閱讀，更多相關(guān)《《組合數(shù)學(xué)算法》PPT課件.ppt（14頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。
1、二、組合 與排列不同，組合是研究無次序的選取問題。 定義：從 n個不同元素中無次序地選取 k個，叫做從 n個元素中選 k個的一個 組合。記 或 其中 中 C是 Combination的第一個字母， 而 是 Andreas Von Ettingelausen(17961876)發(fā)明的 排列與組合的關(guān)系： （ 1） 由（ 1）可推出組合數(shù)的兩個基本恒等式： (i) (ii) 另外，還約定： 當(dāng) kn及 k-6,y-6,z-6也就是相當(dāng)于 x+50, y+50, z+5
2、0. 即原方程化為 (x+5)+(y+5)+(z+5)=16 所以原問題化為 u + v + w=16 即 （個） 例 在 1與 106之間，有多少個整數(shù)的各位數(shù)字之和等于 9？ 解： 只要將問題設(shè)想為將 9個無區(qū)別的球隨意放入 6個不同的 盒子。即 3CC 131 113 1 53CCC 218161816 1163 2 0 0 2CC 5149 1-69 鴿籠原理或抽屜原理 （ 簡介 ） 我們在討論重排列時 ， 如將問題化為：設(shè)盒子是有區(qū)別的 ， 每個盒子的容量不限 ， 而且球數(shù) k盒數(shù) n， 現(xiàn)計(jì)算無空盒出現(xiàn) 的情況數(shù)目 。
3、 假設(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é)商組成年級籃球隊(duì) ， 共需 10名
4、隊(duì)員 ， 每班 至少出 1名 。 問有多少種組成方式 ？ 解：設(shè)有 10個無區(qū)別的球與 8個不同的盒子 ， 不能出現(xiàn)空盒 ， 即 1n 1kC 1540CC 32214 123 36CCC 297918 110 補(bǔ)充例子 某市有 n所中學(xué)，第 i所中學(xué)派出 ci名學(xué)生 (1 ci 39， 1in)來到體育 館看球賽，全部學(xué)生總數(shù)為 ，看臺上每一橫排有 199個座位， 要求同一學(xué)校的學(xué)生必須坐在同一橫排，問體育館最少要安排多少橫排才 能保證全部學(xué)生都能坐下？ 解：首先證明，只要安排 12個橫排即可滿足。 由于 ci只有有限個， ci的有限和也是有
5、限個，選取其中最接近 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。事實(shí)上，反證之，若 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
6、-( c1+c2+c3+c4+c5 ) 199-170=29<32 此與 x1的最小性矛盾。 1 9 9 9cn 1i i 從所有其余的 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é)生已坐完，則問題得證。 如果還未坐完，則可
7、分為兩種情況： 一是余下學(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ù)為端點(diǎn)
8、，含于區(qū)間 0， n中且長度是 n-k的區(qū)間共有 k+1個，它們是 0， n-k， 1， n-k+1， ， k， n 。 因此，棋盤中以橫向?yàn)閷?，縱向?yàn)殚L，且寬 n-k，長 n-l (l k)的矩形有 (k+1)(l+1)個。對 l 求和，即知棋盤中以橫向?yàn)閷挘v向?yàn)殚L，且寬 n-k的 矩形共有 同理，以縱向?yàn)閷挘瑱M向?yàn)殚L且寬為 n-k的矩形也有 個。注意 到其中長寬均為 n-k的正方形有 (k+1)2個，它們同時被計(jì)了上述兩個數(shù)字， 所以棋盤中寬為 n-k的矩 形共有 (k+1)2(k+2)-(k+1)2=(k+1)3 k=1,2, ,n
9、-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個人參加同一會議，其中每兩個互不認(rèn)識者都恰好有兩個共同的熟 人，每兩個熟人卻都沒有共同的認(rèn)識者。證明：每一個與會者都有相同數(shù) 目的熟人。 解：設(shè)與會者甲有 m位熟人 a1， a2， ， am，由于他們都同甲熟悉，所以 他們互不認(rèn)識。（ 為什么
10、？）（因?yàn)槠渲腥我粋€與甲為熟人，故沒有共同 熟人，所以他們互不認(rèn)識） 既然他們都互不認(rèn)識，所以他們中每兩個人 (ai ， aj)除甲外都還有另一個共同的熟人，這些熟人當(dāng)然都不認(rèn)識甲 （為什 么？因?yàn)槿绻腥苏J(rèn)識甲，則甲的熟人為 m+1，不是 m了） 。另外，對于 不同的 (ai ， aj)，另一熟人也互不相同。于是 2 1n2 1n CC 22 2 2 1n 2 1n 333 1)(nn 4 1 2 1) n(nCCn21 知與會者中不認(rèn)識甲的人不會少于 。但另一方面，每個不認(rèn)識甲的人 同甲一道都有兩個共同的熟人，這些人既然都認(rèn)識甲，所以都在 a1， a
11、2， ， am之列，而且對于不同的不認(rèn)識甲的人。這兩個共同的熟人 (ai ， aj)也不會全然相同 （為什么？如果有相同，則甲與不認(rèn)識者就有多于 2個共同熟人） 。因此可得，不認(rèn)識甲的人不會多于 個。綜上所述得， 與會者中恰有 個不認(rèn)識甲的人。這樣一來，參加的總?cè)藬?shù) n便應(yīng)滿足 等式 考察這個關(guān)于 m的正整數(shù)二次方程，發(fā)現(xiàn)它只有唯一的正數(shù)根。所以對于 每個與會者，他的熟人數(shù)目 m為常數(shù)。 （負(fù)值舍去） 唯一 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
《組合數(shù)學(xué)算法》PPT課件.ppt
