【正文】 個巢中至少有 mi個鴿子， i = 1 , 2 , … , n ． 上一小節(jié)的鴿巢原理一是這一原理的特殊 情況，即 m1 = m2 = … = m n= 2， m1 + m2 +… +m n－ n + 1 = n + 1 如若不然，則對任一 i， 都有第 i 個巢中的 鴿子數(shù) ≤mi－ 1 則 鴿巢原理之二 鴿子總數(shù) ≤ m1 + m2 +… +m n－ n ， 與假設相矛盾． 推論１ m只鴿子進 n個巢 ， 至少有一個巢 里有 「 － |只鴿子 ． n m 推論２ n(m－ 1) + 1只鴿子進 n個巢，至少 有一個巢內(nèi)至少有 m只鴿子． 推論３ 若 m1 , m2 , … , m n是正整數(shù)，且 r－ 1,則 m1,… , m n至少有一個 不小于 r m1 + … +m n n 遞歸關系和生成函數(shù) 定義： 對于序列 構造一函數(shù)： 母函數(shù) , 210 ?aaa,)( 2210 ????? xaxaaxG?, 210 aaa稱函數(shù) G(x)是序列 的母函數(shù) 遞推關系 利用遞推關系進行計數(shù)這個方法在算法分析中經(jīng)常用到，舉例說明如下： 例一 .Hanoi問題：這是個組合數(shù)學中的著名問題。給定了序列，對應的母函數(shù)也確定了。 }{ na }{ nb}{ na )(xA }{ nb)(xB???????????????????????22122123212321)( )99)(9 )( )( xbxbxxBxaxaxxAxbxbbxBxaxaaxA即： _ _ _ _ _ _ _ _ _ __ _ _ _ _ _ _ _ _ __ _ _ _ _ _ _ _ _ _8)()()91( ??? xxBxAx遞推關系 承前頁： ??????? )9 : 9 : 9 : 33432232112???????baaxbaaxbaax___ _ _ _ _ _ _ _ _ __ _ _ _ _ _ _ _ _ _)()(98)( xxBxxAxA ???8)()()91( ???? xxBxAx遞推關系 又： ___ _ _ _ _ _ _ _ _ __ _ _ _ _ _ _ _ _ _1)()()91( ??? xxAxBx故得關于母函數(shù) 和 得連立方程組： )(xA )(xB1)()91()(8)()()91(???????xBxxxAxxBxAx{??????????????????2212212321)( )99)(9)(xaxaxxAxbxbxxBxbxbxbxB遞推關系 xxxxD91 91 ?????? xx ??? )91( 280181 xx ???)101)(81( xx ???)101)(81(87191 18801811)(2 xxxxxxxxA??????????)101)(81(118 91)101)(81(1)(xxxxxxxxB?????????遞推關系 ????????????0)10987(21)101 981 7(21)( kkkk xxxxA11 1029827 ?? ??? kkka遞推關系 解法二： n1位的十進制數(shù)的全體共 從中去掉含有偶數(shù)個 5的數(shù)，余下的便是 n1位中含有奇數(shù)個 5的數(shù)。 5。b=b ? 有限群 G的元素個數(shù)叫做群的階 ,記做 |G|。 ? 一般而言，對 [1,n]上的 n階置換， i[1,n]要寫成(i)P1P2，而不是 P1P2(i). (i)P有時寫成 i 在上面例中，1→3→2,2→1→4,3→2→3,4→4→1. 也可寫 (1)P1P2=2,(2)P1P2=4,(3)P1P2=3,(4)P1P2=1. P2P1=( )( )=( )≠P1P2. 1 2 3 4 3 1 2 4 1 2 3 4 3 1 2 4 1 2 3 4 4 3 2 1 3 1 2 4 2 4 3 1 1 2 3 4 2 4 3 1 P1 P1 P2 P1 P1 P2 P2 P2 1 2 3 4 4 3 2 1 4 3 2 1 4 2 1 3 1 2 3 4 4 2 3 1 置換群 ? (1)置換群 [1,n]上的所有 n階置換在上面的乘法定義下是一個群。[1,n]目標集。 a=a (共 n個 a相乘 ). 1 n 群的概念 (2) 簡單例子 例 G={1,1}在普通乘法下是群。b)如果在上一步?jīng)]有新的標記加到 x的頂點上，則停，否則 ，轉(zhuǎn) 3 3。 na n ?nb n ? 故有： 119 ?? ?? nnn baa119 ?? ?? nnn abb{? 1 ,8 11 ?? ba)222( ??