基本的組合計數(shù)公式-文庫吧資料
2025-06-21 18:06本頁面
【正文】 .311.2.1knknknknknknknnkn證明方法：公式代入、組合分析 應(yīng)用： 1式用于化簡 2式用于求和時消去變系數(shù) 3式用于求和時拆項（兩項之和或者差），然后合并 8354 2022/7/13 組合恒等式 —— 變下項求和 NnknNnknnkknnk????????????????????? ????0)1(.5,00證明公式 4. 方法：二項式定理或者組合分析 . 設(shè) S={1,2,…, n}，下面計數(shù) S 的所有子集 . 一種方法就是分類處理， n元集合的 k子集個數(shù)是 ????????kn?? ????????nk kn0根據(jù)加法法則，子集總數(shù)是 另一種方法是分步處理，為構(gòu)成 S 的子集 A，每個元素有 2 種選擇，根據(jù)乘法法則，子集總數(shù)是 2n. 8355 2022/7/13 恒等式求和 —— 變系數(shù)和 202102)1(.7?????????????????????????nnknnknnknknknk證明方法： 二項式定理、級數(shù)求導(dǎo) 其他組合恒等式代入 8356 2022/7/13 ??????????????????????????????????????????????????????????????nknknnkknnkknkknknkxknknxknkxnxknxknx0111111012)1(1)1(令求導(dǎo) 證明公式 6 (二項式定理 +求導(dǎo) ) 8357 2022/7/13 2121101 11112022)1(22)1(211111)1(11]1)1[(1111??????? ??????????????????? ?????????????????????????????????????????????????????????????????????? ?????nnnnnknknknknknknknnnnnnknknknnknknknknknknknknkknk變限常量外提消去變系數(shù) 證明公式 7 (已知恒等式代入 ) 8358 2022/7/13 恒等式 —— 變上項求和 Nknknklnl??????????????????????,0證明 組合分析 . 令 S={a1, a2, … , an+1}為 n+1元集合 . 等式右邊是 S 的 k+1子集數(shù) . 考慮另一種分類計數(shù)的方 法 . 將所有的 k+1元子集分成如下 n+1類： 第 1類：含 a1, 剩下 k個元素取自 {a2,…, an+1} ????????kn???????? ?kn 1 第 2類：不含 a1,含 a2, 剩下 k個元素取自 { a3, … , an+1} ????????k0 …… 不含 a1, a2, …, an, 含 an+1,剩下 k個元素取自空集 由加法法則公式得證 8359 2022/7/13 恒等式 —— 乘積轉(zhuǎn)換式 ???????????????????????????????????krknknkrr證明方法：組合分析 . n 元集中選取 r 個元素，然后在這 r 個元素中再選 k個 元素 . 不同的 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，求和時提到和號外面 . ???????? ??kr kn8360 2022/7/13 恒等式 —— 積之和 NnmmnmknkmnmrNrnmrnmkrnkmnkrk????????? ???????????????????????????? ???????????????????????,.11),m i n (,.1000???????? ??????????????????????????? ??????????????????? ???? mnmknkmnnmknnkm nknk 00關(guān)系 證 明思路：考慮集合 A={a1,a2,…, am}， B={b1,b2,…, bn}. 等 式右邊計數(shù)了從這兩個集合中選出 r個元素的方法 . 將這 些選法按照含有 A中元素的個數(shù) k 進行分類， k=0,1,…, r. 然后使用加法法則 . 8361 2022/7/13 組合恒等式解題方法小結(jié) 證明方法： 已知恒等式帶入 二項式定理 冪級數(shù)的求導(dǎo)、積分 歸納法 組合分析 求和方法： Pascal公式 級數(shù)求和 觀察和的結(jié)果，然后使用歸納法證明 利用已知的公式 8362 2022/7/13 非降路徑問題 基本計數(shù)模型 限制條件下的非降路徑數(shù) 非降路徑模型的應(yīng)用 證明恒等式 單調(diào)函數(shù)計數(shù) 棧的輸出 8363 2022/7/13 基本計數(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ù)：乘法法則 8364 2022/7/13 限制條件的非降路徑數(shù) 從 (0,0)到 (n,n)不接觸對角線的非降路徑數(shù) N N1： 從 (0,0) 到 (n,n) 下不接觸對角 線非降路徑數(shù) N2： 從 (1,0)到 (n,n?1) 下不接觸對角 線非降路徑數(shù) N0: 從 (1,0)到 (n,n?1) 的非降路徑數(shù) N3: 從 (1,0)到 (n,n?1) 接觸對角線的 非降路徑數(shù) 關(guān)系 : N=2N1=2N2=2[N0 ? N3] 8365 2022/7/13 ????????????????????????? ?????????????????122222122][2][24030nnnnnnnNNNNN一一對應(yīng) N3: 從 (1,0)到 (n,n?1) 接觸對角線的 非降路徑數(shù) N4: 從 (0,1)到 (n,n?1) 無限制條件的 非降路徑數(shù) 關(guān)系 : N3=N4 8366 2022/7/13 應(yīng)用 —— 證明恒等式 例 2 證明 證： 計數(shù) (0,0)到 (m+n?r,r) 的非降路徑數(shù) 按照
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號-1