it技術(shù)南開大學acm暑期集訓之組合數(shù)學-資料下載頁
2025-05-21 16:19本頁面
【導讀】《組合數(shù)學》講義。清華大學計算機系。遞推關(guān)系與生成函數(shù)。二分圖的最大匹配。Polya計數(shù)原理的相關(guān)數(shù)學基礎(chǔ)。6位女士和6位先生圍著一張圓桌聚餐，要求。安排女士和先生交替就座。由于已經(jīng)有女士在位，安排先生在六個空位上就。的圓排列是不同的。于是我們得到滿足要求安排方案共計有。如果將整數(shù)n從『1，2。。。，n』的一個排列中。的原理，也叫抽屜原理。一個巢內(nèi)有至少有兩個鴿子。例１367人中至少有２人的生日相同。兩只是完整配對的。的別的參加者的人數(shù)相等。+mn－n+1個鴿子住進n個。例一.Hanoi問題：這是個組合數(shù)學中的著名問題。N個圓盤依其半徑大小，從下而。上套在A柱上，如下圖示。若要求把柱A上的n個盤移到C柱上。現(xiàn)在只有A、B、C三根柱子可用。算法，進而估計它的復雜性，集估計工作量。上述算法是遞歸的運用。后再一次將B上的n-1個盤子轉(zhuǎn)移到C上。給定了序列，對應(yīng)的母函數(shù)也確定了。依次求得，這樣的連鎖反應(yīng)關(guān)系，
【正文】 唯一 aa =a a = e, ab = ba = e , aa = ab , a = b (d)(ab….c) =c …b a . c …b a ab…c = e 1 1 1 1 1 1 1 1 1 1 1 群的概念 (e) G有限， a∈ G，則存在最小正整數(shù) r，使得 a = a = a . 證 設(shè) |G|=g,則 a,a ,…,a ,a ∈ G,由鴿巢原理其中必有相同項。設(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的階。易見 H={a,a ,…a ,a =e} 在原有運算下也是一個群。 r 1 r1 2 g g+1 m l lm r r1 r1 1 r 2 r1 r 置換群 ? 置換群是最重要的有限群，所有的有限群都可以用之表示。 ? 置換： [1,n]到自身的 11變換。 n階置換。[1,n]目標集。 ( ), a1a2… an是 [1,n]中元的一個排列。 n階置換共有 n!個，同一置換用這樣的表示可有 n!個表示法。例如 p1=( )=( )， n階置換又可看作[1,n]上的一元運算，一元函數(shù)。 1 2 … n a1 a2 … a n 1 2 3 4 3 1 2 4 3 1 4 2 2 3 4 1 置換群 ? 置換乘法 P1=( ),P2=( ) P1P2=( )( )=( ) 注意：既然先做 P1的置換，再做 P2的置換就規(guī)定了若作為運算符或函數(shù)符應(yīng)是后置的。這與一般習慣的前置不一樣。 ? 一般而言，對 [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階置換在上面的乘法定義下是一個群。 (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)例 等邊三角形的運動群。 繞中心轉(zhuǎn)動 120，不動， 繞對稱軸翻轉(zhuǎn)。 P1=( ),P2=( ),P3=( ),P4=( ), P5=( ),P6=( )。 [1,n]上的所有置換 (共 n!個 )構(gòu)成一個群，稱為對稱群，記做 Sn. ? 注意：一般說 [1,n]上的一個置換群，不一定是指 Sn的某一個子群。 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計數(shù)原理 ? 參見清華大學相關(guān)學習資料（在公共郵箱中） ? 相關(guān)練習： ? 1135: Let it Bead 組合數(shù)學相關(guān)練習 ? 1038: Lotto ? 1046: 正整數(shù)劃分問題 ? 1052: 圓的重疊問題 ? 1060: Tian Ji The Horse Racing ? 1070: 信與信封問題 ? 1108: Binomial Showdown ? 1135: Let it Bead
教學課件相關(guān)推薦
鄂ICP備17016276號-1