離散數(shù)學(xué)ch2-(8)(參考版)
2025-08-10 11:10本頁面
【正文】 令課程編號(hào)為 c1,c2, . . . ,c151 考慮上述編號(hào)和 c1+1, . . . ,c151 + 1 共 302個(gè)數(shù) 值 1 300+1共 301個(gè) 必有 ci = cj +1 。 組合計(jì)數(shù)的應(yīng)用 9 如果不允許重復(fù)，用 ABCDE可以組成多少種長度為 4的字符串？ 5 * 4 * 3 * 2 = 120 如果不允許重復(fù)，用 ABCDE可以組成多少長度為 4的字符串？其中有多少是以 B開頭的？ 1* 4 * 3 * 2 =24 如果不允許重復(fù)，用 ABCDE可以組成多少長度為 4的字符串？其中有多少 不是 以 B開頭的？ 4 * 4 * 3 *2 = 96 120 24 10 例、 5本不同的計(jì)算機(jī)書 3本不同的數(shù)學(xué)書 2本不同的美術(shù)書 選擇 2本不同類的書有多少方法？ 11 實(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è)？ nn?222/)( 22 nn?. (2) 考慮對(duì)稱關(guān)系的矩陣 . i 行 j 列 (i≠j)的元素 rij = rji. 能夠獨(dú)立 選擇 0或 1的位置有 (n2?n)/2個(gè) . 加上主對(duì)角線的 n個(gè)位置，總計(jì) (n2+n)/2個(gè)位置，每個(gè)位置 2種選擇，根據(jù)乘法法則，構(gòu)成矩 陣的方法數(shù)是 2/)( 22 nn ?(1) 在自反關(guān)系矩陣中，主對(duì)角線元素都是 1，其他位置的元 素可以是 1，也可以是 0，有 2種選擇 . 這種位置有 n2?n個(gè)，根 據(jù)乘法法則，自反關(guān)系的個(gè)數(shù) nn ?2212 解答 (3) 非主對(duì)角線位置分成 (n2?n)/2組，每組包含元素 rij和 rji. 根 據(jù)反對(duì)稱的性質(zhì)， rij與 rji的取值有以下 3種可能： rij=1, rji=0； rij=0, rji=1； rij=rji=0. 所有這些位置元素的選擇方法數(shù)為 . 再考慮到主對(duì)角 線元素的選取，由乘法法則總方法數(shù)為 2/)( 23 nn ?2/)( 232 nnn ?(4) 設(shè) A={x1,x2,…, xn}，任何 A上的函數(shù) f:A?A具有下述形式： f={x1,y1,x2,y2,…, xn,yn} 其中每個(gè) yi（ i=1,2,…, n）有 n種可能的選擇，根據(jù)乘法法則， 有 nn個(gè)不同的函數(shù) . 若 f 是雙射的，那么 y1確定以后， y2只有 n?1種可能的取值 ,…, yn只有 1種取值 . 構(gòu)成雙射函數(shù)的方法數(shù) 是 n(n?1)(n?2)…1 = n!. 13 A 0 id (7位 ) hosted (24位 ) B 1 0 id (14位 ) hostid (16位 ) C 1 1 0 id (21位 ) hostid (8位 ) D 1 1 1 0 (28位 ) E 1 1 1 1 0 (27位 ) 例 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類中的 id部分無效 hostid部分不允許全 0或全 1 14 id hostid A類： 0+7位， 24位 B類： 10+14位， 16位 C類： 110+21位， 8位 限制條件： 1111111在 A類中的 id部分無效 hostid部分不允許全 0或全 1 A類： id 27?1, hosted 224?2， NA＝ 127?16777214＝ 2130706178 B類： id 214, hosted 216?2， NB＝ 16384?65534＝ 1073709056 C類： id 221, hosted 28?2, NC＝ 2097152?254＝ 532676608 N＝ NA+NB+NC＝ 3737091842 解答 15 選取問題：設(shè) n 元集合 S，從 S 中選取 r 個(gè)元素 . 根據(jù)是否有序 , 是否允許重復(fù) , 將該問題分為四個(gè)子類型 不重復(fù)選取 重復(fù)選取 有序選取 集合的排列 多重集的排列 無序選取 集合的組合 多重集的組合 排列與組合 16 定義 設(shè) S為 n元集， (1) 從 S 中有序選取的 r 個(gè)元素稱為 S 的一個(gè) r 排列 ， S 的不同 r 排列總數(shù)記作 P(n,r), r=n的排列是 S的全排列 . (2) 從 S 中無序選取的 r 個(gè)元素稱為 S 的一個(gè) r 組合， S 的不同 r 組合總數(shù)記作 C(n,r) 集合的排列 ?????????rnrnrnnrnP0)!(!),()1(??????????rnrnrnrnrrnPrnC0)!(!!!),(),()2(定理 設(shè) n, r為自然數(shù)，規(guī)定 0!=1，則 17 下面考慮 n ? r 的情況 . (1) 排列的第一個(gè)元素有 n 種選擇的方式 . 排列的第
規(guī)章制度相關(guān)推薦
鄂ICP備17016276號(hào)-1