acm組合數(shù)學(xué)知識(shí)

1、ACM組合數(shù)學(xué)知識(shí),——我的一些總結(jié),目錄,基本組合計(jì)數(shù)容斥原理置換群Polya定理,基本組合計(jì)數(shù),加法原理設(shè)事件A有m種選取方式，事件B有n種選取方式，則選A或B共有m+n種選取方式.乘法原理設(shè)事件A有m種選取方式，事件B有n種選取方式，那么選取A以后再選取B共有m*n種方式.,基本組合計(jì)數(shù),排列問(wèn)題n個(gè)不同物品中選取r個(gè)進(jìn)行排列的方案數(shù)。 記組合問(wèn)題n個(gè)不同物品中選取r個(gè)的方案數(shù)。 記,組合數(shù)恒等式

2、,組合數(shù)的計(jì)算,預(yù)處理組合數(shù) O(n^2)預(yù)處理排列 O(n)直接求 O(m),大組合數(shù)取模(*),n,m為大數(shù),p<=10^5,p為質(zhì)數(shù),Lucas定理,C(n,m)%p的值等于將n,m化為p進(jìn)制數(shù)后，各對(duì)應(yīng)數(shù)對(duì)的組合數(shù)的連乘積%p。,Lucas定理,大組合數(shù)取模(*),問(wèn)題轉(zhuǎn)化為：,排列數(shù)的計(jì)算,預(yù)處理排列 O(n)Stirling逼近(見(jiàn)附件),,正整數(shù)的分拆,粗略的說(shuō)，正整數(shù)的分拆就是將一個(gè)正整數(shù)分成幾個(gè)正

3、整數(shù)的和。n = n1 + n2 + …… + nk (k ≥ 1, ni ≥ 0, 1 ≤ i ≤ k)是正整數(shù)n的一個(gè)k分拆.分拆分為有序和無(wú)序有序: 3 = 2 + 1 與 3 = 1 + 2 是不一樣的無(wú)序: 則一樣,正整數(shù)的有序分拆,正整數(shù)n的有序k分拆的個(gè)數(shù)為跟多重集合組合相似，只是每個(gè)元素至少出現(xiàn)一次,正整數(shù)的無(wú)序分拆,我們用B(n, k)來(lái)表示n的k分拆的個(gè)數(shù)，用B(n)表示n的所有分拆的

4、個(gè)數(shù)，則顯然有(1) B(n, k) = 0 (k > n);(2) B(n) = 定理: B(n+k, k) = B(n, 1) + B(n, 2) + … + B(n, k)及 B(n, 1) = B(n, n) = 1;同樣這定理也很容易證明(可用Ferrers圖證明),Ferrers圖像,圖像概念一個(gè)從上而下的n層格子，mi 為第i層的格子數(shù)，當(dāng)mi>=mi+1(i=1,2,,n-1

5、) ，即上層的格子數(shù)不少于下層的格子數(shù)時(shí)，稱之為Ferrers圖像。圖像性質(zhì)（1）每一層至少有一個(gè)格子；（2）第一行與第一列互換，第二行與第二列互換，…，所得到的圖象仍然是Ferrers圖象，這兩個(gè) Ferrers圖象稱為是一對(duì)共軛的Ferrers圖象。,Ferrers圖像證明正整數(shù)的無(wú)序分拆,整數(shù)n拆分成k個(gè)數(shù)的和的拆分?jǐn)?shù)，和數(shù)n拆分成最大數(shù)為k的拆分?jǐn)?shù)相等。因整數(shù)n拆分成k個(gè)數(shù)的和的拆分可用一k行的圖像表示。所得的Ferre

6、rs圖像的共軛圖像最上面一行有k個(gè)格子。,Fibonacci數(shù)列,F0=0，F(xiàn)1=1，F(xiàn)n=F(n-1)+F(n-2)（n>=2，n∈N*）,Catalan數(shù)列,h(n)= h(0)*h(n-1)+h(1)*h(n-2) + ... + h(n-1)h(0) (n>=2)h(n)=h(n-1)*(4*n-2)/(n+1);h(n)=C(2n,n)/(n+1)入棧出棧序列,第一類(lèi)Stirling數(shù),第一類(lèi)Stirlin

7、g數(shù)是有正負(fù)的，其絕對(duì)值是包含n個(gè)元素的集合分作k個(gè)環(huán)排列的方法數(shù)目。S(n,0) = 0, S(1,1) = 1.S(n+1,k) = S(n,k-1) + nS(n,k),第二類(lèi)Stirling數(shù),第二類(lèi)Stirling數(shù)是把包含n個(gè)元素的集合劃分為正好k個(gè)非空子集的方法的數(shù)目。S(n,k)=0; (n<k||k=0)S(n,n) = S(n,1) = 1,S(n,k) = S(n-1,k-1) + kS(n-1,k

8、),母函數(shù),對(duì)于任意數(shù)列a0,a1,a2...an 即用如下方法與一個(gè)函數(shù)聯(lián)系起來(lái)：G(x) = a0 + a1x + a2x*2 + a3x^3 +....+ anx^n則稱G(x)是數(shù)列的生成函數(shù)(generating function)x+x^2+x^3+…=1/(1-x),母函數(shù)求fibonacci數(shù)列的通項(xiàng)公式,g(x)=x+x^2+2x^3+3x^4+5x^5+8x^6+13x^7+...x*g(x)=x^2+x^

9、3+2x^4+3x^5+5x^6+8x^7+...g(x)+x*g(x)=x+2x^2+3x^3+5x^4+8x^5+...g(x)+x*g(x)=g(x)/x-1g(x)=x/(1-x-x^2),冪級(jí)數(shù)展開(kāi)的唯一性,鴿巢原理,（狄利克雷）抽屜原理若有n個(gè)籠子和n+1只鴿子，所有的鴿子都被關(guān)在鴿籠里，那么至少有一個(gè)籠子有至少2只鴿子。Ramsey定理在一個(gè)K6的完全圖內(nèi)，每邊涂上紅或藍(lán)色，必然有一個(gè)紅色的三角形或藍(lán)色的三

10、角形。,,,,,容斥原理,ZOJ 2836 Number Puzzle,題目大意：求m以下，能被集合A中任意元素整除的自然數(shù)有多少個(gè)？數(shù)據(jù)范圍：n=|A|<=10, m<=2*10^9,Sample Input3 22 3 73 62 3 7,Sample Output14,容斥原理,sum=n;dfs(n,-1,0);void dfs(int n, int num, int pos) {

11、 sum += n /num; for ( i = pos;i < k;i ++ ) dfs(n , -num*a[i] , i+1); },群,群：給定一個(gè)集合G={a,b,c,…}和集合G上的二元運(yùn)算，并滿足:(a) 封閉性：?a,b?G, ?c?G, a＊b=c。(b) 結(jié)合律：?a,b,c?G, (a＊b)＊c=a＊(b＊c)。(c) 單

12、位元：?e?G, ?a?G, a＊e=e＊a=a。(d) 逆元：?a?G, ?b?G, a＊b=b＊a=e，記b=a-1。則稱集合G在運(yùn)算＊之下是一個(gè)群，簡(jiǎn)稱G是群。一般a＊b簡(jiǎn)寫(xiě)為ab。,置換,置換：n個(gè)元素1,2,…,n之間的一個(gè)置換 表示1被1到n中的某個(gè)數(shù)a1取代，2被1到n中的某個(gè)數(shù)a2取代，直到n被1到n中的某個(gè)數(shù)an取代，且a1,a2,…,an互不相同。,置換,轉(zhuǎn)0? a1=轉(zhuǎn)90? a2= 轉(zhuǎn)18

13、0? a3= 轉(zhuǎn)270? a4=,,,置換群,置換群：置換群的元素是置換，運(yùn)算是置換的連接。例如：可以驗(yàn)證置換群滿足群的四個(gè)條件。上頁(yè)中置換群G={轉(zhuǎn)0?、轉(zhuǎn)90?、轉(zhuǎn)180?、轉(zhuǎn)270?},,不動(dòng)置換類(lèi),Zk (K不動(dòng)置換類(lèi))：設(shè)G是1…n的置換群。若K是1…n中某個(gè)元素，G中使K保持不變的置換的全體，記以Zk，叫做G中使K保持不動(dòng)的置換類(lèi)，簡(jiǎn)稱K不動(dòng)置換類(lèi)。,對(duì)于方案1，四個(gè)置換都使方案1保持不變，所以Z1={a1,

14、a2, a3, a4}；對(duì)于方案3，只有置換a1使其不變，所以Z3={a1}；對(duì)于方案11，置換a1和a3使方案其保持不變，所以Z11={a1, a3}。,等價(jià)類(lèi),Ek(等價(jià)類(lèi))：設(shè)G是1…n的置換群。若K是1…n中某個(gè)元素，K在G作用下的軌跡，記作Ek。即K在G的作用下所能變化成的所有元素的集合。,方案1在四個(gè)置換作用下都是方案1，所以E1={1}；方案3，在a1下是3，在a2下變成6，在a3下變成5，在a4下變成4，所以E3={3,

15、4,5,6}；方案11，在a1、a3下是11，在a2、a4下變成12，所以E11={11,12}。,Burnside引理,這里的L就是我們要求的互異的組合狀態(tài)的個(gè)數(shù)。D(aj) 表示在置換aj下不變的元素的個(gè)數(shù),循環(huán),稱為n階循環(huán)。每個(gè)置換都可以寫(xiě)若干互不相交的循環(huán)的乘積，兩個(gè)循環(huán)(a1a2…an)和(b1b2…bn)互不相交是指ai?bj, i,j=1,2,…,n。例如： 這樣的表示是唯一的。置換的循環(huán)節(jié)數(shù)是上述表示中循環(huán)的

16、個(gè)數(shù)。例如(13)(25)(4)的循環(huán)節(jié)數(shù)為3。,,,Polya定理,設(shè)G是p個(gè)對(duì)象的一個(gè)置換群，用m種顏色涂染p個(gè)對(duì)象，則不同染色方案為： 其中G={g1 ,…gs} c(gi )為置換gi的循環(huán)節(jié)數(shù)(i=1…s),Polya定理的應(yīng)用,求用t種顏色的n顆珠子制作成的項(xiàng)鏈和手鐲的個(gè)數(shù)。旋轉(zhuǎn)：a= 1 𝑛 𝑡 gcd?(𝑛,𝑖) 翻轉(zhuǎn)：⻔