it技術(shù)《南開大學(xué)acm暑期集訓(xùn)之組合數(shù)學(xué)》-預(yù)覽頁
【正文】 )()21(2)21)(1()(xxxxH??? 這兩種做法得到的結(jié)果是一樣的。 121 ?nppp ?1?np121 ?nppp ?5?np nn pppp 121 ??遞推關(guān)系 解法 1： 令 位十進(jìn)制數(shù)中出現(xiàn)偶數(shù)個(gè) 5的數(shù)的個(gè)數(shù)， 位十進(jìn)制數(shù)中出現(xiàn)奇數(shù)個(gè) 5的數(shù) 的個(gè)數(shù)。 項(xiàng)表示當(dāng) 是含有奇數(shù)個(gè) 5的 n1位十進(jìn)制數(shù)，令 而得 是含偶數(shù)個(gè) 5的 n位十進(jìn)制數(shù)。故有： 2109 ?? n121111099??????????nnnnnnabbaa8 ,1098 121 ????? ?? aaa nnn遞推關(guān)系 令 ????????????221232188)(8 ))(xaxaxxAxaxaaxA___ _ _ _ _ _ _ _ _ __ _ _ _ _ _ _ _ _ _???????? 22312 )8()8(8)()81( xaaxaaxAx遞推關(guān)系 xxxxxxxAx10171810198 10998)()81( 2????????????? ?????????????????0)10987(21 )1019817(21)101)(101(718)( kkkkxxxxxxxA11 1029827 ?? ????? kka母函數(shù)和遞推關(guān)系應(yīng)用舉例 例 6： 設(shè)有 n條封閉的曲線，兩兩相交于兩點(diǎn)，任意三條封閉曲線不相交于一點(diǎn)。 二分圖及其最大匹配示意 二分圖最大匹配算法（匈牙利算法） ? 令 g=（ x,*,y）是一個(gè)二分圖，其中 x={x1,x2...},y={y1,y2,....}.令 m為 g中的任意匹配。 2。如果不存在被標(biāo)記但未被掃描的頂點(diǎn)，轉(zhuǎn) 4。當(dāng)存在 y被標(biāo)記但未被掃描的頂點(diǎn)時(shí)。 由于每一個(gè)頂點(diǎn)最多被標(biāo)記一次且由于每一個(gè)頂點(diǎn)最多被掃描一次，本匹配算法在有限步內(nèi)終止。b=c. (b)結(jié)合律成立： 任意 a,b,c∈ G,有 (ac). (c)有單位元： 存在 e∈ G,任意 a∈ a=e. b=a. 由于結(jié)合律成立， (ac)可記做 a… (b)結(jié)合律成立：(TαTβ)Tγ = Tα(TβTγ) = TαTβTγ 。 ? 若群 G的任意二元素 a,b恒滿足 ab=ba。設(shè) a =a ,1≤m＜ l≤g+1, e=a ,1≤lm≤g，令 lm= a =a a= a =a .既然有正整數(shù) r使得 a =e,其中必有最小者，不妨仍設(shè)為 r. r稱為 a的階。 n階置換。例如 p1=( )=( )， n階置換又可看作[1,n]上的一元運(yùn)算，一元函數(shù)。 (a)封閉性 ( )( )=( ) (b)可結(jié)合性 (( )( ))( ) =( )=( )(( )( )) (c) 有單位元 e=( ) (d) ( ) =( ) 1 2 … n a1 a2 … a n a1 a2 … a n b1 b2 … b n 1 2 … n b1 b2 … b n 1 2 … n a1 a2 … a n a1 a2 … a n b1 b2 … b n 1 2 … n a1 a2 … a n a1 a2 … a n b1 b2 … b n 1 2 … n c1 c2 … c n b1 b2 … b n c1 c2 … c n b1 b2 … b n c1 c2 … c n 1 2 … n 1 2 … n 1 2 … n a1 a2 … a n a1 a2 … a n 1 2 … n 1 置換群 ? (2)例 等邊三角形的運(yùn)動(dòng)群。 1 2 3 1 2 3 1 2 3 2 3 1 1 2 3 3 1 2 1 2 3 1 3 2 1 2 3 3 2 1 1 2 3 2 1 3 1 2 3 Polya計(jì)數(shù)原理 ? 參見清華大學(xué)相關(guān)學(xué)習(xí)資料（在公共郵箱中） ? 相關(guān)練習(xí)： ? 1135: Let it Bead 組合數(shù)學(xué)相關(guān)練習(xí) ? 1038: Lotto ? 1046: 正整數(shù)劃分問題 ? 1052: 圓的重疊問題 ? 1060: Tian Ji The Horse Racing ? 1070: 信與信封問題 ? 1108: Binomial Showdown ? 1135: Let it Bead
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1