acm組合數(shù)學知識

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

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

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

4、個數(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圖像,圖像概念一個從上而下的n層格子，mi 為第i層的格子數(shù)，當mi>=mi+1(i=1,2,,n-1

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

6、rs圖像的共軛圖像最上面一行有k個格子。,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)入棧出棧序列,第一類Stirling數(shù),第一類Stirlin

7、g數(shù)是有正負的，其絕對值是包含n個元素的集合分作k個環(huán)排列的方法數(shù)目。S(n,0) = 0, S(1,1) = 1.S(n+1,k) = S(n,k-1) + nS(n,k),第二類Stirling數(shù),第二類Stirling數(shù)是把包含n個元素的集合劃分為正好k個非空子集的方法的數(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ù),對于任意數(shù)列a0,a1,a2...an 即用如下方法與一個函數(shù)聯(lián)系起來：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ù)列的通項公式,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),冪級數(shù)展開的唯一性,鴿巢原理,（狄利克雷）抽屜原理若有n個籠子和n+1只鴿子，所有的鴿子都被關在鴿籠里，那么至少有一個籠子有至少2只鴿子。Ramsey定理在一個K6的完全圖內(nèi)，每邊涂上紅或藍色，必然有一個紅色的三角形或藍色的三

10、角形。,,,,,容斥原理,ZOJ 2836 Number Puzzle,題目大意：求m以下，能被集合A中任意元素整除的自然數(shù)有多少個？數(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={a,b,c,…}和集合G上的二元運算，并滿足:(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在運算＊之下是一個群，簡稱G是群。一般a＊b簡寫為ab。,置換,置換：n個元素1,2,…,n之間的一個置換 表示1被1到n中的某個數(shù)a1取代，2被1到n中的某個數(shù)a2取代，直到n被1到n中的某個數(shù)an取代，且a1,a2,…,an互不相同。,置換,轉(zhuǎn)0? a1=轉(zhuǎn)90? a2= 轉(zhuǎn)18

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

14、a2, a3, a4}；對于方案3，只有置換a1使其不變，所以Z3={a1}；對于方案11，置換a1和a3使方案其保持不變，所以Z11={a1, a3}。,等價類,Ek(等價類)：設G是1…n的置換群。若K是1…n中某個元素，K在G作用下的軌跡，記作Ek。即K在G的作用下所能變化成的所有元素的集合。,方案1在四個置換作用下都是方案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)的個數(shù)。D(aj) 表示在置換aj下不變的元素的個數(shù),循環(huán),稱為n階循環(huán)。每個置換都可以寫若干互不相交的循環(huán)的乘積，兩個循環(huán)(a1a2…an)和(b1b2…bn)互不相交是指ai?bj, i,j=1,2,…,n。例如： 這樣的表示是唯一的。置換的循環(huán)節(jié)數(shù)是上述表示中循環(huán)的

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