離散數(shù)學(xué)ch2-(8)(編輯修改稿)
2025-09-03 11:10 本頁面
【文章內(nèi)容簡介】 n 組，每組 2人，有多少分法？ 23 多重集的排列與組合 定義 多重集 S={n1?a1, n2?a2, …, nk?ak}， n=n1+n2+… nk 表 示 S 中元素的總數(shù) . (1) 從 S 中有序選取的 r個元素稱為多重集 S 的一個 r 排列 . r=n 的排列稱為 S 的 全排列 (2) 從 S 中無序選取的 r 個元素稱作多重集 S 的一個 r 組合 注意： ? 多重集中元素的重復(fù)度， 0 ni ? +∞, 當(dāng) ni＝ +∞，表示 ai重復(fù)選取的次數(shù)沒有限制 ? S的子集 X={x1?a1, x2?a2, …, xk?ak}, 其中 0 ? xi ? +∞ 24 多重集的排列計數(shù) 定理 設(shè) S={n1?a1, n2?a2, …, nk ?ak}為多重集， (1) S 的全排列數(shù)是 (2) 若 r ? ni， i=1,2,…, k，那么 S 的 r 排列數(shù)是 kr !...!!!21 knnnn證明 (1) 有 C(n,n1) 種方法放 a1，有 C(n?n1,n2)種方法放 a2, …, 最后有 C(n?n1?n2?… ?nk?1, nk) 方法放 ak. 根據(jù)乘法法則 , (2) r 個位置中的每個位置都有 k 種選法，由乘法法則得 kr !!!!!0!)!. ..(. ..)!(!)!()!(!!2111212111121211kkkkk. .. nnnnnnnnnnnnnnnnnn),nn. ..nn) . .. C ( n,nn) C ( nC ( n , n????????????????25 多重集的組合 定理 多重集 S={n1?a1, n2?a2, …, nk?ak}， 0ni ?+∞ 當(dāng) r ? ni , S的 r 組合數(shù)為 N = C(k+r?1,r), ),1()!1(! )!1( rrkCkr krN ???????證明 一個 r 組合為 {x1?a1, x2?a2, …, xk?ak}， 其中 x1 + x2 + … + xk = r , xi 為非負(fù)整數(shù) . 這個不定方程的非負(fù)整數(shù)解對應(yīng)于下述排列 1…1 0 1…1 0 1…1 0 …… 0 1…1 x1個 x2個 x3個 xk個 r 個 1， k?1個 0 的全排列數(shù)為 例、考慮 3本書 (計算機，數(shù)學(xué)、歷史 )，每本書圖書館有 6本拷貝，選擇 6本書有多少種可能？ 計算機 | 數(shù)學(xué) |歷史 *** | * * | * 計算機 | 數(shù)學(xué) |歷史 | **** | ** 8個元素中 6個 * 2個 | 的排列數(shù) C(8， 2) 8！ 6！ 2！ 27 解 使用一一對應(yīng)的思想求解這個問題 . a1, a2, …, ak ： k個不相鄰的數(shù) , 屬于集合 {1, 2, …, n} b1, b2, …, bk： k個允許相鄰的數(shù) , 屬于集合 {1, …, n?(k?1)} 對應(yīng)規(guī)則是 bi = ai?(i?1). i =1, 2, …, k 因此 N = C(n?k+1,k) 例 從 S={1, 2, … , n}中選擇 k 個不相鄰的數(shù)，有多少種方法？ 一一對應(yīng)的技巧 28 主要內(nèi)容 ? 二項式定理 ? 組合恒等式 ? 非降路徑問題 二項式定理與組合恒等式 29 二項式定理 定理 設(shè) n 是正整數(shù)，對一切 x 和 y ????????????? nkknkn yxknyx0)(證明方法 : 數(shù)學(xué)歸納法、組合分析法 . 證 當(dāng)乘積被展開時其中的項都是下述形式： xi yn?i, i = 0, 1, 2, …, n. 而構(gòu)成形如 xiyn?i 的項，必須從 n 個 (x+y) 中選 i 個提供 x，其它的 n?i 個提供 y. 因此， xiyn?i 的系數(shù)是 ，定理得證 . ????????in30 二項式定理的應(yīng)用 解 由二項式定理 令 i =13 得到展開式中 x12y13的系數(shù)，即 ??? ???????????? 2502525 )3()2(25))3(2(iii yxiyx13121312 32!12!13!25)3(21325 ???????????例 6 求在 (2x－ 3y)25的展開式中 x12y13的系數(shù) . 31 組合恒等式：遞推式 ??????????????????? ???????????????????????????????????????????????111.311.2.1knknknknknknknnkn證明方法：公式代入、組合分析 應(yīng)用： 1式用于化簡 2式用于求和時消去變系數(shù) 3
規(guī)章制度相關(guān)推薦
鄂ICP備17016276號-1