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