組合數(shù)學第六章-資料下載頁
2025-08-05 20:27本頁面
【正文】 33) 定理 : 對任意正整數(shù) n, 有 ?d|n ?(d)/d = ?(n)/n. 證明 : n=1, 定理成立 . 若 n1, 設 . , 21121 21 kakaa pppnpppn k ?? ???? ?1||/)(/)(ndnddddd ??kkkji jijiki iipppppppppp??1111)(...)()()1( ???? ????? ???????nnppppp kkkji jiki i)()1(...11)1(111?? ??????? ??????? ?多重集的圓排列數(shù) (p135) 設 {??1,…, ??k}的長為 n的圓排列數(shù)為 h(n), 周期是 d的線排列數(shù)為 f(d), 則有 nndkdf ??|)(? ? ???????nddkdnnf|)( ??? ????????nddndkdnndfdnh||1)(1)( ?應用二 : 魔法手鐲 (補充 ) 設有 m種魔法珠 , B=(bij)m?m為其鄰接矩陣 h^(n) : 滿足 B, 且長為 n的圓排列數(shù) . f^(d) : 滿足 B, 且 周期 是 d的線排列數(shù) . g(n)=tr Bn : B的長為 n的回路的條數(shù) )(tr)(|^ nndBdf ??? ??nddBdnf|^ ][ t r )()( ??? ??ndddnndd Bndhnh||^1^ ][ t r )(1)()( ?樣例分析 (補充 ) 1 4 4 6 1 1 2 2 4 4 1 3 1 4 2 4 輸出 8 ?????????????0100111001010010B?????????????11101311200112B?????????????354151264466114124BtrB=1, tr B2=7, tr B4=23 觀察各周期排列數(shù)與 B4的關系 周期 1: 3, 周期 2: 12, 34, 23 周期 4: 1232, 4323, 4333, 2333 (?(4)?1 + ?(2)?7 + ?(1)?23) / 4 = 8. 本章小結(jié)與作業(yè) ? 容斥原理及其簡單應用 ? 錯排問題 帶禁止位置的排列 ? 莫比烏斯反演 兩者可以統(tǒng)一為偏序集上的莫比烏斯反演 作業(yè) : 第六章 , 從以下 7題中任選 3題 ex3, ex5, ex13, ex16, ex17, ex26, ex30 編程題 : 魔法手鐲 .
職業(yè)教育相關推薦
鄂ICP備17016276號-1