離散數(shù)學(xué)第8章.ppt

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

2、比賽次數(shù)與淘汰人數(shù)之間存在一一對應(yīng)，總計(jì)淘汰99人，因此至少需要99場比賽.,5,8.1 基本計(jì)數(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)行劃分，分別計(jì)數(shù)，然 后使用加法法則 分步處理：一種產(chǎn)生方式分解為若干獨(dú)立步驟，對每步 分別進(jìn)行計(jì)數(shù)，然后使用乘法法則 分類與分步結(jié)合使用： 先分類，每類內(nèi)部分步 先分步，每步又分類,9,應(yīng)用實(shí)例,例3 設(shè)A, B, C 是3

4、個(gè)城市，從A 到 B 有3條道路，從B 到 C 有2條道路，從A 直接到 C 有4條道路，問從 A 到 C 有多少種不同的方式？ 解： N=32+4 = 10 例4 求1400的不同的正因子個(gè)數(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,選取問題 -組合計(jì)數(shù)模型1,設(shè) n 元集合 S，從 S 中選取 r 個(gè)元素. 根據(jù)是否有序，是否允許重復(fù)可以將該問題分為四個(gè)子類型,12,集合的排列,定義 從

5、n 元集 S 中有序、不重復(fù)選取的 r 個(gè)元素稱為 S 的一個(gè) r 排列，S 的所有 r 排列的數(shù)目記作 P(n,r) 定理8.1 證明 使用乘法法則 推論 S 的環(huán)排列數(shù) =,13,集合的組合,定義 從 n 元集 S 中無序、不重復(fù)選取的 r 個(gè)元素稱為 S 的一個(gè) 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：組合證明 實(shí)例：證明 C(n, r) = C(n, n

6、r) 證 設(shè) S =1, 2, , n是n元集合，對于S 的任意 r-組合 A=a1, a2, , ar，都存在一個(gè)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,基本計(jì)數(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 個(gè)（分步處理）： C(100,1)3 N= 3C(100,3) + 1003 = 1485100,例8.5 從1300中任取3個(gè)數(shù)使得其和能被3整除有多少種方法？,17,基本計(jì)數(shù)公式的應(yīng)用(續(xù)),解: 1000!=1000 999 998 21 將上面的每個(gè)因子分解，若分解式中共有i 個(gè)5, j 個(gè)2， 那么min(i, j)就是0的個(gè)數(shù). 1, ,1000中有 500個(gè)是 2 的倍數(shù)，j 500; 200個(gè)是 5 的倍數(shù)， 40個(gè)是 25 的倍數(shù)（多加 40 個(gè) 5）， 8個(gè)是 125 的倍數(shù)（再多加 8 個(gè) 5）， 1個(gè)是 625 的倍數(shù)（再多加 1 個(gè) 5） i = 200+

8、40+8+1 = 249. min(i, j)=249.,例2 求1000！的末尾有多少個(gè)0？,18,基本計(jì)數(shù)公式的應(yīng)用(續(xù)),例3 設(shè)A為 n 元集，問 (1) A上的自反關(guān)系有多少個(gè)？ (2) A上的反自反關(guān)系有多少個(gè)？ (3) A上的對稱關(guān)系有多少個(gè)？ (4) A上的反對稱關(guān)系有多少個(gè)？ (5) A上既不對稱也不是反對稱 的關(guān)系有多少個(gè)？,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 時(shí)，每個(gè)位置都有 k 種選法，得 kr.,20,多重集的組合,定理8.4 多重集 S=n1a1, n2a2, , nkak，0ni + 當(dāng) r ni , S的r 組合數(shù)為 N = C(k+r1,r), 證明 一個(gè) r 組合為 x1a1, x2a2, , xkak， 其中 x1 + x2 + + xk = r , xi 為非負(fù)整數(shù). 這個(gè)不定方程的非負(fù)整數(shù)解對應(yīng)于下述排列 11 0 11 0 11 0 0 11 x1個(gè) x2個(gè) x3個(gè) xk個(gè) r 個(gè)1，k1個(gè) 0 的全排列數(shù)為,21,實(shí)例,例5 排列26個(gè)

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

11、,解: (1) P(10,10) P(11,5) (2) P(10,10) P(10,5)/10,解：相當(dāng)于2n 不同的球放到 n 個(gè)相同的盒子，每個(gè)盒子2個(gè)，放法為,例7 把 2n 個(gè)人分成 n 組，每組2人，有多少分法？,23,實(shí)例(續(xù)),解 使用一一對應(yīng)的思想求解這個(gè)問題. a1, a2, , ak ：k個(gè)不相鄰的數(shù), 屬于集合1, 2, , n b1, b2, , bk：k個(gè)允許相鄰的數(shù), 屬于集合1, , n(k1) 對應(yīng)規(guī)則是 bi = ai(i1). i =1, 2, , k 因此 N = C(nk+1,k),例8 從S=1, 2, , n中選擇 k 個(gè)不相鄰的數(shù)，有多少種方法？

12、,24,8.3二項(xiàng)式定理與組合恒等式,8.3.1 二項(xiàng)式定理 8.3.2 組合恒等式 8.3.3 非降路徑問題,25,二項(xiàng)式定理,定理8.5 設(shè) n 是正整數(shù)，對一切 x 和 y 證明方法: 數(shù)學(xué)歸納法、組合分析法. 證 當(dāng)乘積被展開時(shí)其中的項(xiàng)都是下述形式：xi yni, i = 0, 1, 2, , n. 而構(gòu)成形如 xiyni 的項(xiàng)，必須從n 個(gè) 和 (x+y) 中選 i 個(gè)提供 x，其它的 ni 個(gè)提供 y. 因此， xiyni 的系數(shù)是 ，定理得證.,26,二項(xiàng)式定理的應(yīng)用,例1 求在(2x3y)25的展開式中x12y13的系數(shù). 解 由二項(xiàng)式定理 令i =13 得到展開式中x12y1

13、3的系數(shù)，即,27,組合恒等式遞推式,證明方法：公式代入、組合分析 應(yīng)用： 1式用于化簡 2式用于求和時(shí)消去變系數(shù) 3式用于求和時(shí)拆項(xiàng)（兩項(xiàng)之和或者差），然后合并,28,組合恒等式變下項(xiàng)求和,證明公式4. 方法：二項(xiàng)式定理或者組合分析. 設(shè)S=1,2,n，下面計(jì)數(shù)S 的所有子集. 一種方法就是分類處理，n元集合的 k子集個(gè)數(shù)是,根據(jù)加法法則，子集總數(shù)是,另一種方法是分步處理，為構(gòu)成 S 的子集A，每個(gè)元素有 2 種選擇，根據(jù)乘法法則，子集總數(shù)是2n.,29,恒等式求和變系數(shù)和,證明方法： 二項(xiàng)式定理、級數(shù)求導(dǎo) 其他組合恒等式代入,30,證明公式6 (二項(xiàng)式定理+求導(dǎo)),31,證明公式7 (已知

14、恒等式代入),32,恒等式變上項(xiàng)求和,證明 組合分析. 令S=a1, a2, , an+1為n+1元集合. 等式右邊是 S 的 k+1子集數(shù). 考慮另一種分類計(jì)數(shù)的方 法. 將所有的k+1元子集分成如下n+1類： 第1類：含a1, 剩下 k個(gè)元素取自a2,an+1,第2類：不含a1,含a2, 剩下k個(gè)元素取自 a3, , an+1, 不含a1, a2, , an, 含an+1,剩下k個(gè)元素取自空集,由加法法則公式得證,33,恒等式乘積轉(zhuǎn)換式,證明方法：組合分析. n 元集中選取 r 個(gè)元素，然后在這 r 個(gè)元素中再選 k個(gè) 元素. 不同的 r 元子集可能選出相同的 k子集，例如 a, b, c

15、, d, e a, b, c, d b, c, d b, c, d, e b, c, d 重復(fù)度為： 應(yīng)用：將變下限 r 變成常數(shù) k，求和時(shí)提到和號外面.,34,恒等式積之和,關(guān)系,證明思路：考慮集合A=a1,a2,am，B=b1,b2,bn. 等 式右邊計(jì)數(shù)了從這兩個(gè)集合中選出r個(gè)元素的方法. 將這 些選法按照含有A中元素的個(gè)數(shù) k 進(jìn)行分類，k=0,1,r. 然后使用加法法則.,35,組合恒等式解題方法小結(jié),證明方法： 已知恒等式帶入 二項(xiàng)式定理 冪級數(shù)的求導(dǎo)、積分 歸納法 組合分析 求和方法： Pascal公式 級數(shù)求和 觀察和的結(jié)果，然后使用歸納法證明 利用已知的公式,36,非降路徑

16、問題,基本計(jì)數(shù)模型 限制條件下的非降路徑數(shù) 非降路徑模型的應(yīng)用 證明恒等式 單調(diào)函數(shù)計(jì)數(shù) 棧的輸出,37,基本計(jì)數(shù)模型,(0,0) 到 (m,n) 的非降路徑數(shù)：C(m+n, m) (a,b) 到 (m,n)的非降路徑數(shù)： 等于 (0,0) 到 (ma,nb) 的非降路徑數(shù) (a,b) 經(jīng)過 (c,d) 到 (m,n) 的非降路徑數(shù)：乘法法則,38,限制條件的非降路徑數(shù),從(0,0)到(n,n)不接觸對角線的非降路徑數(shù) N N1：從(0,0) 到 (n,n) 下不接觸對角 線非降路徑數(shù) N2：從(1,0)到(n,n1) 下不接觸對角 線非降路徑數(shù) N0: 從(1,0)到(n,n1) 的非降路徑

17、數(shù) N3: 從(1,0)到(n,n1) 接觸對角線的 非降路徑數(shù) 關(guān)系: N=2N1=2N2=2N0 N3,39,一一對應(yīng),N3: 從(1,0)到(n,n1) 接觸對角線的 非降路徑數(shù) N4: 從(0,1)到(n,n1) 無限制條件的 非降路徑數(shù) 關(guān)系: N3=N4,40,應(yīng)用證明恒等式,例2 證明 證： 計(jì)數(shù)(0,0)到(m+nr,r) 的非降路徑數(shù) 按照 k分類，再分步. (0,0)到(mk,k)路徑數(shù)， (mk,k)到(m+nr,r)的路徑數(shù),41,應(yīng)用單調(diào)函數(shù)計(jì)數(shù),例3 A=1,2,m, B=1,2,n， N1:B上單調(diào)遞增函數(shù)個(gè) 數(shù)是(1,1)到 (n+1,n) 的非降路徑數(shù) N:

18、B上單調(diào)函數(shù)個(gè)數(shù) N=2N1 N2: A到B單調(diào)遞增函數(shù)個(gè) 數(shù)是從(1,1)到 (m+1,n) 的非降路徑數(shù) N: A到B的單調(diào)函數(shù)個(gè)數(shù)，N =2N2 嚴(yán)格單調(diào)遞增函數(shù)、遞減函數(shù)個(gè)數(shù)都是C(n,m),42,函數(shù)計(jì)數(shù)小結(jié),A = 1, 2, , m, B = 1, 2, , n f: AB,43,應(yīng)用棧輸出的計(jì)數(shù),例4 將1,2,n按照順序輸入棧,有多少個(gè)不同的輸出序列？ 解：將進(jìn)棧、出棧分別記作 x,y, 出棧序列是n個(gè)x，n個(gè)y的排列，排列中任何前綴的 x 個(gè)數(shù)不少于y 的個(gè)數(shù). 等于從 (0,0) 到 (n,n) 的不穿過對角線的非降路徑數(shù). 實(shí)例：n=5 x, x, x ,y, y, x, y, y, x, y 進(jìn),進(jìn),進(jìn),出,出,進(jìn),出,出,進(jìn),出 3, 2, 4, 1, 5,44,應(yīng)用棧輸出的計(jì)數(shù)(續(xù)),N: 堆棧輸出個(gè)數(shù) N:(0,0)到(n,n)不 穿過對角線的 非降路徑數(shù) N0:(0,0)到(n,n)的 非降路徑總數(shù) N1:(0,0)到(n,n)的 穿過對角線的 非降路徑數(shù) N2:(1,1)到(n,n) 的非降路徑數(shù). 關(guān)系：N=N =N0N1, N1=