acm之組合數(shù)學(xué)

1、組合數(shù)學(xué),湖南師范大學(xué)羅迅,排列,集合中有n個元素，從該集合中有順序的無重復(fù)取r個，稱之為排列。P(n,r) = n! / (n-r)!有順序的有重復(fù)nr有順序無重復(fù)的環(huán)形排列P(n,r) / r,組合,n元素的集合，取出r個元素，不考慮秩序，稱之為組合C(n,r) = n! / (n-r)! / r!也記作帕斯卡遞推：C(n,r) = C(n-1,r-1) + C(n-1,r),題目列表,POJ1496P

2、OJ1850hdu1465，錯排問題，基本題,容斥原理,最簡單的表述,一般表述,DeMorgan定理,,容斥原理,容斥原理遞歸實(shí)現(xiàn),dfs(int idx,set S,int sym)ans += num(S) * sym;for(int i=idx;i<n;++i)dfs(I,S交Ai,-sym)for(int i=0;i<n;++i)dfs(i,Ai,1),題目列表,POJ1173，亦可DPPOJ1091

3、POJ2773hdu1695,普通型母函數(shù),普通型母函數(shù)用來解決多重集合的組合問題。給定集合S={n1a1,n2a2,…,nnan}，從中選取k個元素的組合數(shù)，就是普通型母函數(shù)x的k次方的系數(shù),母函數(shù),普通型母函數(shù)x看成某種單位，每一個系數(shù)ai就是x達(dá)到i個單位的組合數(shù),普通型母函數(shù),1、3、5克砝碼各2個，稱出7克物體的砝碼選擇方式有多少種？一共可以稱出的質(zhì)量有多少種？母函數(shù),普通型母函數(shù),一個6面骰子，連續(xù)擲1

4、0次，點(diǎn)數(shù)之和為30的概率是多少？母函數(shù),指數(shù)型母函數(shù),指數(shù)型母函數(shù)用來求多重集合的排列問題。給定集合S={n1a1,n2a2,…,nnan}，從中選取k個元素的排列數(shù)與x的k次方相關(guān),指數(shù)型母函數(shù),指數(shù)型母函數(shù),三個1，兩個6,一個8，能夠組成多少個四位數(shù)？母函數(shù)Note：答案不是x的4次方的系數(shù)！??！,題目列表,hdu1028，求整數(shù)拆分?jǐn)?shù)，基本題hdu1085hdu1398，求整數(shù)拆分的變種hdu152

5、1，指數(shù)型母函數(shù)，基本題hdu2079,群,群是帶運(yùn)算的集合，是一種代數(shù)結(jié)構(gòu)給定一個集合G，以及G上的一個二元運(yùn)算如果運(yùn)算滿足封閉性結(jié)合性單位元存在逆元存在稱G是一個群,置換群,置換是一個操作置換群就是有關(guān)置換的集合,置換,Note：置換是一種變換，跟數(shù)出現(xiàn)的順序無關(guān),輪換,稱為一個輪換,不是所有置換都是輪換但所有置換都可以分解為輪換的運(yùn)算,置換-輪換,因?yàn)槿我庵脫Q都可以劃分為輪換，因此我們使用輪換來表示置

6、換，比原始表達(dá)要方便,Polya定理,設(shè)D是一個有限集，包含p個對象G是D上的一個置換群R是一個有限權(quán)集，共有m個權(quán)問：用R給D賦權(quán)，共有多少種不同的方法gi是G中的第i個元素，也就是第i個置換c(g)是g分解出輪換的個數(shù),Polya定理示例,計(jì)算互異的組合狀態(tài)計(jì)數(shù)問題,Polya定理示例,D是一個有限集，一共4個元素R是有限權(quán)集，一共2個權(quán)，也就是2種顏色G是D上的置換群，一共有4個置換a/b/c/d分別是

7、4個置換的輪換的個數(shù),Polya定理示例,旋轉(zhuǎn)0°，置換為(1)(2)(3)(4)，輪換數(shù)量為4旋轉(zhuǎn)90，置換為(1234)，輪換數(shù)量為1旋轉(zhuǎn)180，置換為(13)(24)，輪換數(shù)量為2旋轉(zhuǎn)270，置換為(1432)，輪換數(shù)量為1,例2,等邊三角形的三個頂點(diǎn)用三種顏色染色，一共有多少種方案？D是有限集，一共3個元素R是權(quán)集，一共3個元素G是置換群，一共6個置換分別是(1)(2)(3)、(123)、(132)、(1

8、)(23)、(13)(2)、(12)(3),題目列表,POJ1286POJ2409hdu1812，以上為最基本題POJ2154，略微優(yōu)化,Burnside引理,設(shè)G是置換群，g是G中的一個置換，則G的等價類個數(shù)為e(g)表示g中不變元的個數(shù),Burnside引理示例,,此時n為16旋轉(zhuǎn)0°，置換為單位元，不變元的個數(shù)為16旋轉(zhuǎn)90，不變元的個數(shù)為2旋轉(zhuǎn)180，不變元的個數(shù)為4旋轉(zhuǎn)270，不變元的個數(shù)為2