離散數(shù)學(xué)ch2-(8)-在線瀏覽
2024-09-17 11:10本頁面
【正文】 ?????????????????,.9),min(,.800???????? ??????????????????????????? ??????????????????? ???? mnmknkmnnmknnkm nknk 00關(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. 然后使用加法法則 . 36 恒等式求和 :變系數(shù)和 202102)1(.11?????????????????????????nnknnknnknknknk證明方法： 二項(xiàng)式定理、級(jí)數(shù)求導(dǎo) 其他組合恒等式代入 37 證明公式 10 ??????????????????????????????????????????????????????????????nknknnkknnkknkknknkxknknxknkxnxknxknx0111111012)1(1)1(令求導(dǎo)38 證明公式 11 2121101 11112022)1(22)1(211111)1(11]1)1[(1111??????? ??????????????????? ?????????????????????????????????????????????????????????????????????? ?????nnnnnknknknknknknknnnnnnknknknnknknknknknknknknkknk變限常量外提消去變系數(shù)39 組合恒等式解題方法小結(jié) 證明方法： ? 已知恒等式帶入 ? 二項(xiàng)式定理 ? 冪級(jí)數(shù)的求導(dǎo)、積分 ? 歸納法 ? 組合分析 求和方法： ? Pascal公式 ? 級(jí)數(shù)求和 ? 觀察和的結(jié)果，然后使用歸納法證明 ? 利用已知的公式 40 非降路徑的計(jì)數(shù) (0,0) 到 (m,n) 的非降路徑數(shù)： C(m+n, m) (a,b) 到 (m,n)的非降路徑數(shù)： 等于 (0,0) 到 (m?a,n?b) 的非降路徑數(shù) (a,b) 經(jīng)過 (c,d) 到 (m,n) 的非降路徑數(shù)：乘法法則 (m,n) (0,0) 41 棧輸出的計(jì)數(shù) 例 將 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ù) 42 輸入： 1, 2, 3, 4, 5, 輸出 ： 3, 2, 4, 1, 5 進(jìn) ,進(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ù) 43 棧輸出的計(jì)數(shù) ?????????????????????????????????nnnnnnnnnnnnnN 211)!1()!1()!2(!!)!2(122從 (0,0)到 (n,n) 的穿 過對(duì)角線的非降路徑 ?從 (1,1) 到 (n,n) 的 非降路徑 從 (0,0)到 (n,n) 的非降 路徑總數(shù)為 C(2n,n) 條， 從 (1,1) 到 (n,n) 的非降 路徑數(shù)為 C(2n,n1) 條， (n,n) (0,0) (1,0) (1,1) 44 第十二章 習(xí)題課 主要內(nèi)容 基本計(jì)數(shù) ? 計(jì)數(shù)法則：加法法則、乘法法則 ? 計(jì)數(shù)模型：選取問題、非降路徑問題、方程的非負(fù)整數(shù) 解問題 ? 處理方法：分類處理、分步處理、一一對(duì)應(yīng)思想 計(jì)數(shù)符號(hào) ? 組合數(shù)或二項(xiàng)式系數(shù) C(m,n)：組合恒等式 ? 排列數(shù) P(m,n) ?二項(xiàng)式定理 45 基本要求 ? 能夠熟練使用加法法則與乘法法則 ? 熟悉和應(yīng)用基本的組合計(jì)數(shù)模型： 選取問題 非降路徑 ? 熟悉二項(xiàng)式定理 ? 能證明組合恒等式并對(duì)二項(xiàng)式系數(shù)進(jìn)行求和 46 練習(xí) 1： 基本的組合計(jì)數(shù) 1. 求 1400的不同的正
規(guī)章制度相關(guān)推薦
鄂ICP備17016276號(hào)-1