離散數(shù)學(xué)-8.1-2組合計數(shù)基礎(chǔ).ppt

1、1,第8章 組合計數(shù)基礎(chǔ),2,第8章 組合計數(shù)基礎(chǔ),引言 組合問題的處理技巧 8.1 基本計數(shù)規(guī)則 8.2 排列與組合 8.3 二項式定理與組合恒等式 8.4 多項式定理,3,組合問題的處理技巧,一一對應(yīng) 數(shù)學(xué)歸納法 上下界逼近,4,一一對應(yīng)與上下界逼近,例1 在允許移動被切割的物體的情況下，最少用多少次切割可以將 333 的立方體切成 27個單位邊長的立方體？,中間的小立方體的6個面都是切割產(chǎn)生的面，每次切割至多產(chǎn)生一個面，至少需要6次切割。存在一種切割方法恰好用 6 次切割。,例2 100個選手淘汰賽，為產(chǎn)生冠軍至少需要多少輪比賽？ 方法1：50+25+12+6+3+2+1=99 方法2：

2、比賽次數(shù)與淘汰人數(shù)之間存在一一對應(yīng)，總計淘汰99人，因此至少需要99場比賽.,5,8.1 基本計數(shù)規(guī)則,8.1.1 加法法則 8.1.2 乘法法則 8.1.3 分類處理與分步處理,6,加法法則,加法法則：事件A 有 m 種產(chǎn)生方式，事件 B 有n 種產(chǎn)生方式，則 “事件A或B” 有 m+n 種產(chǎn)生方式. 使用條件：事件 A 與 B 產(chǎn)生方式不重疊 適用問題：分類選取 推廣：事件 A1有 p1種產(chǎn)生方式，事件 A2有 p2 種產(chǎn)生方式，, 事件 Ak 有 pk 種產(chǎn)生的方式，則 “事件A1或 A2或 Ak” 有 p1+p2+pk 種產(chǎn)生的方式.,7,乘法法則,乘法法則：事件A 有 m 種產(chǎn)生方式

3、，事件 B 有n 種產(chǎn)生方式，則 “事件A與B” 有 m n 種產(chǎn)生方式. 使用條件：事件 A 與 B 產(chǎn)生方式彼此獨(dú)立 適用問題：分步選取 推廣：事件 A1有 p1種產(chǎn)生方式，事件 A2有 p2 種產(chǎn)生方式，, 事件 Ak 有 pk 種產(chǎn)生的方式，則 “事件A1與 A2與 Ak” 有 p1 p2 pk 種產(chǎn)生的方式.,8,分類處理與分步處理,分類處理：對產(chǎn)生方式的集合進(jìn)行劃分，分別計數(shù)，然 后使用加法法則 分步處理：一種產(chǎn)生方式分解為若干獨(dú)立步驟，對每步 分別進(jìn)行計數(shù)，然后使用乘法法則 分類與分步結(jié)合使用： 先分類，每類內(nèi)部分步 先分步，每步又分類,9,應(yīng)用實例,例3 設(shè)A, B, C 是3

4、個城市，從A 到 B 有3條道路，從B 到 C 有2條道路，從A 直接到 C 有4條道路，問從 A 到 C 有多少種不同的方式？ 解： N=32+4 = 10 例4 求1400的不同的正因子個數(shù) 1400=23 52 7 解：正因子為：2i 5j 7k，其中 0i3, 0j2, 0k1 N=(3+1)(2+1)(1+1)=24,10,8.2 排列與組合,引言 選取問題 8.2.1 集合的排列與組合 8.2.2 多重集的排列與組合,11,選取問題 -組合計數(shù)模型1,設(shè) n 元集合 S，從 S 中選取 r 個元素. 根據(jù)是否有序，是否允許重復(fù)可以將該問題分為四個子類型,12,集合的排列,定義 從

5、n 元集 S 中有序、不重復(fù)選取的 r 個元素稱為 S 的一個 r 排列，S 的所有 r 排列的數(shù)目記作 P(n,r) 定理8.1 證明 使用乘法法則 推論 S 的環(huán)排列數(shù) =,13,集合的組合,定義 從 n 元集 S 中無序、不重復(fù)選取的 r 個元素稱為 S 的一個 r 組合，S 的所有 r 組合的數(shù)目記作 C(n,r) 定理8.2,推論 設(shè)n, r為正整數(shù)，則 (1) C(n, r)= (2) C(n, r) = C(n, nr) (3) C(n, r)=C(n1,r1)+C(n1,r),14,證明方法,方法1：公式代入并化簡 方法2：組合證明 實例：證明 C(n, r) = C(n, n

6、r) 證 設(shè) S =1, 2, , n是n元集合，對于S 的任意 r-組合 A=a1, a2, , ar，都存在一個S 的 nr 組合SA與之對應(yīng). 顯然不同的 r 組合對應(yīng)了不同的 nr 組合，反之也對，因 此 S 的 r 組合數(shù)恰好與 S 的(nr)組合數(shù)相等. C(n, r)=C(n1,r1)+C(n1,r) 稱為 Pascal公式，也對應(yīng)了楊 輝三角形， 兩種證明方法都適用.,15,楊輝三角,16,基本計數(shù)公式的應(yīng)用,解 分類選取 A = 1, 4, ,298 B = 2, 5, ,299 C = 3, 6, , 300 分別取自 A, B, C: 各 C(100,3) A, B, C

7、 各取 1 個（分步處理）： C(100,1)3 N= C(100,3) + 1003 = 1485100,例1 從1300中任取3個數(shù)使得其和能被3整除有多少種方法？,17,基本計數(shù)公式的應(yīng)用(續(xù)),解: 1000!=1000 999 998 21 將上面的每個因子分解，若分解式中共有i 個5, j 個2， 那么min(i, j)就是0的個數(shù). 1, ,1000中有 500個是 2 的倍數(shù)，j 500; 200個是 5 的倍數(shù)， 40個是 25 的倍數(shù)（多加 40 個 5）， 8個是 125 的倍數(shù)（再多加 8 個 5）， 1個是 625 的倍數(shù)（再多加 1 個 5） i = 200+40+

8、8+1 = 249. min(i, j)=249.,例2 求1000！的末尾有多少個0？,18,基本計數(shù)公式的應(yīng)用(續(xù)),例3 設(shè)A為 n 元集，問 (1) A上的自反關(guān)系有多少個？ (2) A上的反自反關(guān)系有多少個？ (3) A上的對稱關(guān)系有多少個？ (4) A上的反對稱關(guān)系有多少個？ (5) A上既不對稱也不是反對稱 的關(guān)系有多少個？,19,多重集的排列,定理8.3 多重集S=n1a1, n2a2, , nkak，0 ni + (1) 全排列 r = n, n1 + n2 + + nk = n 證明：分步選取. 先放a1, 有C(n,n1) 種方法；再放a2, 有 C(n n1,n2)種方

9、法, . , 放ak,有C(nn1n2 nk1,nk) 種方法 (2) 若r ni 時，每個位置都有 k 種選法，得 kr.,20,多重集的組合,定理8.4 多重集 S=n1a1, n2a2, , nkak，0ni + 當(dāng) r ni , S的r 組合數(shù)為 N = C(k+r1,r), 證明 一個 r 組合為 x1a1, x2a2, , xkak， 其中 x1 + x2 + + xk = r , xi 為非負(fù)整數(shù). 這個不定方程的非負(fù)整數(shù)解對應(yīng)于下述排列 11 0 11 0 11 0 0 11 x1個 x2個 x3個 xk個 r 個1，k1個 0 的全排列數(shù)為,21,實例,例5 排列26個字母，

10、使得 a 與 b 之間恰有7個字母，求方法數(shù).,解： 設(shè)盒子的球數(shù)依次記為 x1, x2, , xn, 則滿足 x1 + x2 + + xn = r， x1, x2, , xn 為非負(fù)整數(shù) N = C(n+r1, r),例4 r 個相同的球放到 n 個不同的盒子里，每個盒子球數(shù)不限，求放球方法數(shù).,解： 固定a 和 b, 中間選7個字母，有2 P(24,7)種方法， 將它看作大字母與其余17個字母全排列有18！種，共 N = 2 P(24,7) 18!,22,實例(續(xù)),例6 (1) 10個男孩，5個女孩站成一排，若沒有女孩相鄰， 有多少種方法？ (2) 如果站成一個圓圈，有多少種方法？,解: (1) P(10,10) P(11,5) (2) P(10,10) P(10,5)/10,解：相當(dāng)于2n 不同的球放到 n 個相同的盒子，每個盒子2個，放法為,例7 把 2n 個人分成 n 組，每組2人，有多少分法？,23,實例(續(xù)),解 使用一一對應(yīng)的思想求解這個