山東理工大學(xué)-離散數(shù)學(xué)課件-第12章

1、1,組合數(shù)學(xué)的研究?jī)?nèi)容 組合存在性 組合計(jì)數(shù) 組合枚舉 組合優(yōu)化 本書的內(nèi)容 基本的組合計(jì)數(shù)公式 遞推方程與生成函數(shù),第四部分 組合數(shù)學(xué),2,第十二章 基本的組合計(jì)數(shù)公式,主要內(nèi)容 加法法則與乘法法則 排列與組合 二項(xiàng)式定理與組合恒等式 多項(xiàng)式定理,3,12.1 加法法則與乘法法則,加法法則 乘法法則 分類處理與分步處理,4,加法法則,加法法則：事件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 有

2、 pk 種產(chǎn)生的方式，則 “事件A1或 A2或 Ak” 有 p1+p2+pk 種產(chǎn)生的方式.,5,乘法法則,乘法法則：事件A 有 m 種產(chǎn)生方式，事件 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)生的方式.,6,分類處理與分步處理,分類處理：對(duì)產(chǎn)生方式的集合進(jìn)行劃分，分別計(jì)數(shù)，然后使用加法法則 分步處理：一種產(chǎn)生方式分解為若干獨(dú)立步驟，對(duì)每

3、步分別進(jìn)行計(jì)數(shù)，然后使用乘法法則 分類與分步結(jié)合使用 先分類，每類內(nèi)部分步 先分步，每步又分類,7,實(shí)例：關(guān)系計(jì)數(shù),例1 設(shè)A為 n 元集，問 (1) A上的自反關(guān)系有多少個(gè)？ (2) A上的對(duì)稱關(guān)系有多少個(gè)？ (3) A上的反對(duì)稱關(guān)系有多少個(gè)？ (4) A上的函數(shù)有多少個(gè)？其中雙射函數(shù)有多少個(gè)？,.,(2) 考慮對(duì)稱關(guān)系的矩陣. i 行 j 列(ij)的元素 rij = rji. 能夠獨(dú)立 選擇0或1的位置有(n2n)/2個(gè). 加上主對(duì)角線的n個(gè)位置，總計(jì) (n2+n)/2個(gè)位置，每個(gè)位置2種選擇，根據(jù)乘法法則，構(gòu)成矩 陣的方法數(shù)是,(1) 在自反關(guān)系矩陣中，主對(duì)角線元素都是1，其他位置的元

4、 素可以是1，也可以是0，有2種選擇. 這種位置有n2n個(gè)，根 據(jù)乘法法則，自反關(guān)系的個(gè)數(shù),8,解答,(3) 非主對(duì)角線位置分成 (n2n)/2組，每組包含元素rij和rji. 根 據(jù)反對(duì)稱的性質(zhì)，rij與rji的取值有以下3種可能： rij=1, rji=0； rij=0, rji=1； rij=rji=0. 所有這些位置元素的選擇方法數(shù)為 . 再考慮到主對(duì)角 線元素的選取，由乘法法則總方法數(shù)為,(4) 設(shè)A=x1,x2,xn，任何A上的函數(shù) f:AA具有下述形式： f=, 其中每個(gè)yi（i=1,2,n）有n種可能的選擇，根據(jù)乘法法則， 有nn個(gè)不同的函數(shù). 若 f 是雙射的，那么y1確定以

5、后，y2只有 n1種可能的取值 , yn只有1種取值. 構(gòu)成雙射函數(shù)的方法數(shù) 是n(n1)(n2)1 = n!.,9,例2：Ipv4網(wǎng)址計(jì)數(shù),32位地址 網(wǎng)絡(luò)標(biāo)識(shí)+主機(jī)標(biāo)識(shí) (1) A類：最大網(wǎng)絡(luò)； B類：中等網(wǎng)絡(luò)； C：小網(wǎng)絡(luò)； D：多路廣播； E：備用 (2) 限制條件： 1111111在A類中的netid部分無效 hostid部分不允許全0或全1,10,netid hostid A類： 0+7位， 24位 B類： 10+14位， 16位 C類： 110+21位， 8位 限制條件：1111111在A類中的netid部分無效 hostid部分不允許全0或全1 A類：netid 271, ho

6、sted 2242， NA127167772142130706178 B類：netid 214, hosted 2162， NB16384655341073709056 C類：netid 221, hosted 282, NC2097152254532676608 NNA+NB+NC3737091842,解答,11,選取問題：設(shè) n 元集合 S，從 S 中選取 r 個(gè)元素. 根據(jù)是否有序 , 是否允許重復(fù), 將該問題分為四個(gè)子類型,12.2 排列與組合,12,定義12.1 設(shè)S為n元集， (1) 從 S 中有序選取的 r 個(gè)元素稱為 S 的一個(gè) r 排列，S 的不同 r 排列總數(shù)記作 P(n,

7、r), r=n的排列是S的全排列. (2) 從 S 中無序選取的 r 個(gè)元素稱為 S 的一個(gè) r 組合，S 的不同 r 組合總數(shù)記作 C(n,r),集合的排列,定理1.1 設(shè)n, r為自然數(shù)，規(guī)定0!=1，則,13,下面考慮 n r 的情況. (1) 排列的第一個(gè)元素有 n 種選擇的方式. 排列的第二個(gè)元素有n1種選法, , 第 r 個(gè)元素的方式數(shù) n r+1. 根據(jù)乘法法則，總的選法數(shù)為 n(n 1)( n2)(n r+1) = (2) 分兩步構(gòu)成 r 排列. 首先無序地選出r個(gè)元素，然后再構(gòu)造這r個(gè)元素的全排列. 無序選擇r個(gè)元素的方法數(shù)是C(n,r)；針對(duì)每種選法，能構(gòu)造 r!個(gè)不同的全

8、排列. 根據(jù)乘法法則，不同的 r 排列數(shù)滿足 P(n, r)=C(n,r) r! 組合數(shù)C(n,r)也稱為二項(xiàng)式系數(shù)，記作,證明,14,推論 設(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),推論,例3 證明 C(n,r) = C(n,nr) 證 設(shè) S =1, 2, , n是n元集合，對(duì)于S 的任意 r 組合 A=a1, a2, , ar，都存在一個(gè)S 的 nr 組合SA與之對(duì)應(yīng). 顯然不同的 r 組合對(duì)應(yīng)了不同的 nr 組合，反之也對(duì)，因此 S 的 r 組合數(shù)恰好與 S 的 nr 組合數(shù)相等.

9、 公式(3) 稱為 Pascal公式，也對(duì)應(yīng)了楊輝三角形,證明方法：公式代入并化簡(jiǎn)，組合證明,15,楊輝三角,16,多重集的排列與組合,定義12.2 多重集 S=n1a1, n2a2, , nkak，n=n1+n2+nk 表 示 S 中元素的總數(shù). (1) 從S 中有序選取的r個(gè)元素稱為多重集 S 的一個(gè) r 排列. r=n 的排列稱為 S 的全排列 (2) 從 S 中無序選取的 r 個(gè)元素稱作多重集 S 的一個(gè)r 組合 注意： 多重集中元素的重復(fù)度，0 ni +, 當(dāng)ni+，表示ai重復(fù)選取的次數(shù)沒有限制 S的子集 X=x1a1, x2a2, , xkak, 其中0 xi +,17,多重集的

10、排列計(jì)數(shù),定理12.2 設(shè)S=n1a1, n2a2, , nk ak為多重集， (1) S 的全排列數(shù)是 (2) 若r ni，i=1,2,k，那么S 的 r 排列數(shù)是 kr,證明 (1) 有C(n,n1) 種方法放a1，有C(nn1,n2)種方法放a2, , 最后有C(nn1n2nk1, nk) 方法放ak. 根據(jù)乘法法則, (2) r 個(gè)位置中的每個(gè)位置都有 k 種選法，由乘法法則得 kr,18,多重集的組合,定理12.3 多重集 S=n1a1, n2a2, , nkak，0ni + 當(dāng) r ni , S的r 組合數(shù)為 N = C(k+r1,r),證明 一個(gè) r 組合為 x1a1, x2a2

11、, , xkak， 其中 x1 + x2 + + xk = r , xi 為非負(fù)整數(shù). 這個(gè)不定方程的非負(fù)整數(shù)解對(duì)應(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ù)為,19,例3 排列26個(gè)字母，使得 a 與 b 之間恰有7個(gè)字母，求方法數(shù).,解 固定a 和 b, 中間選7個(gè)字母，有2 P(24,7)種方法， 將它看作大字母與其余17個(gè)字母全排列有18！種，共 N = 2 P(24,7) 18!,組合計(jì)數(shù)的應(yīng)用,解 相當(dāng)于2n 不同的球放到 n 個(gè)相同的盒子，每個(gè)盒子2個(gè)，放法為,例4 把 2n 個(gè)人分成 n 組，每組2人，有

12、多少分法？,20,解 使用一一對(duì)應(yīng)的思想求解這個(gè)問題. a1, a2, , ak ：k個(gè)不相鄰的數(shù), 屬于集合1, 2, , n b1, b2, , bk：k個(gè)允許相鄰的數(shù), 屬于集合1, , n(k1) 對(duì)應(yīng)規(guī)則是 bi = ai(i1). i =1, 2, , k 因此 N = C(nk+1,k),例5 從S=1, 2, , n中選擇 k 個(gè)不相鄰的數(shù)，有多少種方法？,一一對(duì)應(yīng)的技巧,21,主要內(nèi)容 二項(xiàng)式定理 組合恒等式 非降路徑問題,12.3 二項(xiàng)式定理與組合恒等式,22,二項(xiàng)式定理,定理12.4 設(shè) n 是正整數(shù)，對(duì)一切 x 和 y,證明方法: 數(shù)學(xué)歸納法、組合分析法. 證 當(dāng)乘積被

13、展開時(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ù)是 ，定理得證.,23,二項(xiàng)式定理的應(yīng)用,解 由二項(xiàng)式定理 令i =13 得到展開式中x12y13的系數(shù)，即,例6 求在(2x3y)25的展開式中x12y13的系數(shù).,24,組合恒等式：遞推式,證明方法：公式代入、組合分析 應(yīng)用： 1式用于化簡(jiǎn) 2式用于求和時(shí)消去變系數(shù) 3式用于求和時(shí)拆項(xiàng)（兩項(xiàng)之和或者差），然后合并,25,組合恒等式：基本求和式,證明公式4. 方法：二項(xiàng)式定理或者

14、組合分析. 設(shè)S=1,2,n，下面計(jì)數(shù)S 的所有子集. 一種方法就是分類處理，n元集合的 k子集個(gè)數(shù)是,根據(jù)加法法則，子集總數(shù)是,另一種方法是分步處理，為構(gòu)成 S 的子集A，每個(gè)元素有 2 種選擇，根據(jù)乘法法則，子集總數(shù)是2n.,26,恒等式求和:變系數(shù)和,證明方法： 二項(xiàng)式定理、級(jí)數(shù)求導(dǎo) 其他組合恒等式代入,27,證明公式6,28,證明公式7,29,恒等式:變上項(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+

15、1,第2類：不含a1,含a2, 剩下k個(gè)元素取自 a3, , an+1, 不含a1, a2, , an, 含an+1,剩下k個(gè)元素取自空集,由加法法則公式得證,30,恒等式:乘積轉(zhuǎn)換式,證明方法：組合分析. n 元集中選取 r 個(gè)元素，然后在這 r 個(gè)元素中再選 k個(gè) 元素. 不同的 r 元子集可能選出相同的 k子集，例如 a, b, c, d, e a, b, c, d b, c, d b, c, d, e b, c, d 重復(fù)度為： 應(yīng)用：將變下限 r 變成常數(shù) k，求和時(shí)提到和號(hào)外面.,31,恒等式:積之和,關(guān)系,證明思路：考慮集合A=a1,a2,am，B=b1,b2,bn. 等 式右邊

16、計(jì)數(shù)了從這兩個(gè)集合中選出r個(gè)元素的方法. 將這 些選法按照含有A中元素的個(gè)數(shù) k 進(jìn)行分類，k=0,1,r. 然后使用加法法則.,32,組合恒等式解題方法小結(jié),證明方法： 已知恒等式帶入 二項(xiàng)式定理 冪級(jí)數(shù)的求導(dǎo)、積分 歸納法 組合分析 求和方法： Pascal公式 級(jí)數(shù)求和 觀察和的結(jié)果，然后使用歸納法證明 利用已知的公式,33,非降路徑的計(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ù)：乘法法則,34,從(0,0)到(n

17、,n)不接觸對(duì)角線的非降路徑數(shù) N N1：從(0,0) 到 (n,n) 下不接觸對(duì)角 線非降路徑數(shù) N2：從(1,0)到(n,n1) 下不接觸對(duì)角 線非降路徑數(shù) N0: 從(1,0)到(n,n1) 的非降路徑數(shù) N3: 從(1,0)到(n,n1) 接觸對(duì)角線的 非降路徑數(shù) 關(guān)系: N=2N1=2N2=2N0 N3,限制條件的非降路徑數(shù),35,N3: 從(1,0)到(n,n1) 接觸對(duì)角線的 非降路徑數(shù) N4: 從(0,1)到(n,n1) 無限制條件的 非降路徑數(shù) 關(guān)系: N3=N4,一一對(duì)應(yīng),36,例7 A=1,2,m, B=1,2,n， N1:B上單調(diào)遞增函數(shù)個(gè) 數(shù)是(1,1)到 (n+1,

18、n) 的非降路徑數(shù) N: 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ù)數(shù)，N =2N2 嚴(yán)格單調(diào)遞增函數(shù)、遞減函數(shù)個(gè)數(shù)都是C(n,m),應(yīng)用:單調(diào)函數(shù)計(jì)數(shù),37,棧輸出的計(jì)數(shù),例8 將1, 2, , n 按照順序輸入棧，有多少個(gè)不同的輸 出序列？ 分析：將進(jìn)棧、出棧分別記作 x, y, 出棧序列是 n個(gè)x，n個(gè)y 的排列， 排列中任何前綴的 x 個(gè)數(shù)不少于y 的個(gè)數(shù)， 等于從(0,0)到 (n,n) 的不穿過對(duì)角線的非降路徑數(shù),38,輸入： 1, 2, 3, 4, 5, 輸出 ：3, 2, 4, 1, 5 進(jìn)

19、,進(jìn),進(jìn),出,出,進(jìn),出,出,進(jìn),出 x,x,x,y,y,x,y,y,x,y,1,2,5,3,4,棧輸出的計(jì)數(shù),39,棧輸出的計(jì)數(shù),從 (0,0)到 (n,n) 的穿 過對(duì)角線的非降路徑 從 (-1,1) 到 (n,n) 的 非降路徑 從 (0,0)到 (n,n) 的非降 路徑總數(shù)為 C(2n,n) 條， 從(-1,1) 到 (n,n) 的非降 路徑數(shù)為 C(2n,n-1) 條，,40,A = 1, 2, , m, B = 1, 2, , n f: AB,函數(shù)計(jì)數(shù)小結(jié),41,.,定理12.6 設(shè)n為正整數(shù)，xi為實(shí)數(shù)，i =1, 2, , t.,求和是對(duì)滿足方程n1+n2+nt=n的一切非負(fù)整

20、數(shù)解求,12.4 多項(xiàng)式定理,42,推論,推論1 多項(xiàng)式展開式中不同的項(xiàng)數(shù)為方程 的非負(fù)整數(shù)解的個(gè)數(shù) C(n+ t 1,n) 推論2,例9 求 (2x13x2+5x3)6 中 x13x2x32 的系數(shù). 解 由多項(xiàng)式定理得,43,多項(xiàng)式系數(shù),組合意義 多項(xiàng)式系數(shù) 多重集 S=n1 a1, n2a2, , nt at 的全排列數(shù) n個(gè)不同的球放到 t 個(gè)不同的盒子使得第一個(gè)盒子含n1個(gè)球，第二個(gè)盒子含n2個(gè)球，第 t 個(gè)盒子含 nt 個(gè)球的方案數(shù),符號(hào),44,第十二章 習(xí)題課,主要內(nèi)容 基本計(jì)數(shù) 計(jì)數(shù)法則：加法法則、乘法法則 計(jì)數(shù)模型：選取問題、非降路徑問題、方程的非負(fù)整數(shù) 解問題 處理方法：分

21、類處理、分步處理、一一對(duì)應(yīng)思想 計(jì)數(shù)符號(hào) 組合數(shù)或二項(xiàng)式系數(shù) C(m,n)：組合恒等式 排列數(shù) P(m,n) 多項(xiàng)式系數(shù) 二項(xiàng)式定理與多項(xiàng)式定理,45,基本要求,能夠熟練使用加法法則與乘法法則 熟悉和應(yīng)用基本的組合計(jì)數(shù)模型： 選取問題 不等方程的解 非降路徑 熟悉二項(xiàng)式定理與多項(xiàng)式定理 能證明組合恒等式并對(duì)二項(xiàng)式系數(shù)進(jìn)行求和 了解多項(xiàng)式系數(shù)及其相關(guān)公式,46,練習(xí)1：基本的組合計(jì)數(shù),1. 求1400的不同的正因子個(gè)數(shù).,解 1400的素因子分解式是 1400 = 23 52 7 1400的任何正因子都具有下述形式： 2i5j 7k ，其中 0 i 3, 0 j 2, 0 k 1. 根據(jù)乘法法則，1400的正因子數(shù)是 i, j, k 的選法數(shù) N=(1+3)(1+2)(1+1)=24.,47,練習(xí)2：基本的組合計(jì)數(shù),2把10個(gè)不同的球放到6個(gè)不同的盒子里，允許空盒，且前 2個(gè)盒子球的總數(shù)至多是4，問有多少種方法？,解 根據(jù)前兩個(gè)盒子含球數(shù)k對(duì)放法分類，其中 k=0,1,2,3,4. 對(duì)于給定的 k，再分步處理計(jì)算放球的方法數(shù)： 從10個(gè)球中選放入前兩個(gè)盒子的k個(gè)球，有C(10,k)選法； 把選好的k個(gè)球