組合數(shù)學(xué)第一講ppt課件-資料下載頁
2025-05-03 01:34本頁面
【正文】 n nr l r r lr ? 4. ( ) ( ) = ( )( ) () 第一章 排列與組合 m k mk m m k k=0 證 1(x+y) =∑ ( )x y , 令 x=y=1,得 () ? 5. ( )+( )+…+( )=2 , m ≥0, () m m m m 0 1 m 組合證 [1,m]的所有方案 .每一元素都可取或不取兩種狀態(tài)，由乘法原理可知所有狀態(tài)數(shù)為 2m. 而這些可分解為從 m個(gè)元素中分別取 0個(gè) ,1個(gè)， 2個(gè)， … ， m個(gè)組合的總和。 第一章 排列與組合 ? 例 某保密裝置須同時(shí)使用若干把不同的鑰匙才能打開?，F(xiàn)有７人，每人持若干鑰匙。須４人到場，所備鑰匙才能開鎖。問 ? ①至少有多少把不同的鑰匙？ ? ②每人至少持幾把鑰匙？ ? 解 ①每３人至少缺１把鑰匙，且每３人所缺鑰匙不同。故至少共有 ( )=35把不同的鑰匙。 7 3 ? 任一人對于其他６人中的每３人，都至少有１把鑰匙與之相配才能開鎖。故每人至少持 ( )＝ 20把不同的鑰匙。 ６ ３ 一般地 某保密裝置安裝了一個(gè)電子鎖 . 須同時(shí)使用若干把不同的鑰匙才能打開?，F(xiàn)有 n人，每人有一把鑰匙。必須 m人 (mn)到場，才能用鑰匙開鎖。問怎么分配鎖的特征和每個(gè)的鑰匙上的特征 ? 既然鎖比任意 m1把鑰匙多一個(gè)特征，而任意兩個(gè) m1把鑰匙組合缺少的特征不同，所以鎖的特征至少為 C(n,m1)個(gè)。 同樣道理，對于 m把鑰匙中的一把 a，加入任意m1把鑰匙必能打開鎖，也即剩下的 n1把鑰匙中任意 m1把鑰匙必然缺少 a中的某項(xiàng)特征，所以每把鑰匙的特征數(shù)至少為 C(n1, m1)個(gè)。 111 1( 1 ) ! ( 1 ) !( 1 ) ! ( ) ! ( 1 ) ! ( 1 ) ! ( 1 1)) (nmnnmnn n n m nnCm n m m n mn m C n Cm?????? ? ???? ? ? ? ?? ? ? ? ??1( 1 ) nmnCnm????每個(gè)鎖的特征在鑰匙中出現(xiàn)的次數(shù) 鎖的特征數(shù) 111( 1 ) nmm nnn m CCn???????上式實(shí)際說明了一個(gè)構(gòu)造鎖及磁卡的方法。 鑰匙特征滿足最低要求 11n m mnnCC? ? ??? 鎖的特征數(shù)以 n=5, m=3為為例，在 MATLAB輸入以下指令： n=5。m=3。 v=nchoosek(1:5,nm+1)? v = 1 1 1 1 1 1 2 2 2 3 2 2 2 3 3 4 3 3 4 4 3 4 5 4 5 5 4 5 5 5 10 10 10 9 9 9 8 8 8 7 7 7 6 6 6 5 5 5 4 4 4 3 3 3 2 2 2 1 1 1 鑰匙 5 鑰匙 4 鑰匙 3 鑰匙 2 鑰匙 1 10 9 8 7 6 5 4 3 2 1 特征 鑰匙 1 2 3 1 2 4 1 2 5 1 3 4 1 3 5 1 4 5 2 3 5 2 3 4 2 4 5 3 4 5 第一章 排列與組合 [例 ]設(shè) n位長能糾 r個(gè)錯(cuò)的碼字的個(gè)數(shù)為 M，則 n位長的 01字符串共有 2n個(gè)。但不能每個(gè)串都設(shè)為碼字，否則失去糾錯(cuò)能力。 ??????????????????????rknrknknMkn02022第一章 排列與組合 Hamming距離 :設(shè) a=a1a2…a n， b=b1b2…b n是 n位串。則 a,b的 Hamming距離為 即對應(yīng)位不同的位的個(gè)數(shù)。它有如下性質(zhì)： d(a,b) ≥0 (當(dāng)且僅當(dāng) a=b時(shí)，等號(hào)成立 )； d(a,b)=d(b,a)。 d(a,b)+d(b,c) ≥ d(a,c) ????niii babad1||),(第一章 排列與組合 右圖表示以 a為球心 ,r位半徑的球體中的 串都作為 a處理。若規(guī)定 a是碼字，收到 a?有 d(a,a?)≤r 即將 a?當(dāng)作 a發(fā)生最多 r個(gè)錯(cuò)誤。此時(shí)兩個(gè)碼字 a,b應(yīng)滿足 d(a,b)≥2r+1。當(dāng)作 a處理的串的個(gè)數(shù)為 故 nrk knM 20???????????a r a’ ???????????????????????????rnnn?10第一章 排列與組合 另一方面任一串與最近的碼字的距離不大于 2r，否則此串本身可作為一新的碼字，即以 2r位半徑的各碼字為球心，應(yīng)當(dāng)使任一串落入某球內(nèi)，故 nrk knM 220???????????故所以結(jié)論成立。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1