組合數學在程序設計競賽中的應用

（一）軟件學院2003級穆浩英組合數學在程序設計競賽中的應用

（一）軟件學院2003級穆浩1內容提要排列組合和容斥原理群論與Polya定理遞推關系內容提要排列組合和容斥原理2兩個基本原則1、加法原則

如果完成一件事情有兩種方案，而第一個方案有m種方法，第二個方案有n中方法，則完成該事情共有m+n種方法。2、乘法原則

如果完成一件事情需要兩個步驟，第一步有m中方法，第二步又有n種方法，則完成該事情共有m*n種方法兩個基本原則3排列組合的幾個基本結論1、相異元素不允許重復的排列數和組合數：

n!(n-r)!P(n,r)=C(n,r)=n!(n-r)!r!2、不盡相異元素的全排列RP(n,n)=n!n1!n2!...nt!排列組合的幾個基本結論1、相異元素不允許重復的排列數和組合數4排列組合的幾個基本結論3、相異元素不允許重復的圓排列

CP(n,n)=P(n,n)n4、相異元素允許重復的組合數集合描述：設S={∞·e1,∞·e2,……∞·en,}，從S中允許重復地取出r個元素，稱為r可重組合RC(∞,r)=C(n+r-1,r)=(n+r-1)!r!(n-1)!排列組合的幾個基本結論3、相異元素不允許重復的圓排列CP(n5排列組合例題例1：電子鎖

某機要部門安裝了電子鎖。M工作人員每人發一張磁卡，卡上有開鎖的密碼特征，為了確保安全，規定至少有N人同時使用各自的磁卡才能將鎖打開。 現在需要計算一下，電子鎖上至少要有多少種特征，每個人的磁卡上至少要有多少特征。排列組合例題例1：電子鎖6排列組合例題先做一個簡單的假設：M=7，N=4。對于問題一：任意3人在一起，至少缺一種特征，不能打開。電子鎖的至少應有C(7,3)=35種特征。對于問題二：對任一位工作者的磁卡而言，其余6人中任意3人在場至少缺少一種A所具有的特征而無法打開大門。每張磁卡至少應有C(6,3)=20種特征所以總終答案是C(M,N-1)和C(M-1,N-1)排列組合例題先做一個簡單的假設：M=7，N=4。7排列組合例題例2：zju1976PathOnaGrid求n*m的方格圖形中，從點（0，0）到點（n，m）的最短路徑數目（0，0）（n，m）SampleInput（給定n，m）54

11

00

SampleOutput(路徑數目)126

2排列組合例題例2：zju1976PathOnaGri8排列組合例題 我們用組合數學的思路來解題。最短路徑必定是一條只向右上走得路。設向右走一步為x，向上走一步為y。則每一條路線一定對應由n個x，m個y共m+n個元素組成的排列。以n=5，m=4為例，任意一條路線如下圖所示，對應的xy序列為：xyxxxyxyy可見，只要能確定9個位置中4個y的位置就唯一確定了一條路徑。所以，本題答案就是C(n+m,m)排列組合例題 我們用組合數學的思路來解題。最短路徑必定是一條9排列組合數的一般計算方法20!12!8!C(20，12)=怎么計算？設計一個求階乘的函數？20！=243290200817664000012！=4790016008！=40320C(20,12)=125970顯然20！用int表示一定是失敗的，而C(20,12)的結果又完全可以用int來表示。回想我們是怎么計算的?先約分再計算！排列組合數的一般計算方法20!C(20，12)=怎么10排列組合數的一般計算方法（一）計算組合數的函數intgcd(inta,intb){ if(b==0)returna; elsereturngcd(b,a%b);}//歐幾里德輾轉相除法求最大公約數intC(intn,intm){ inti,a,fz=1,fm=1;

for(i=1;i<=m;i++) { fz*=(n-i+1); fm*=i; a=gcd(fz,fm); fz/=a; fm/=a; } returnfz/fm;}分子分母排列組合數的一般計算方法（一）計算組合數的函數intgcd11排列組合數的一般計算方法（二）使用double類型doubleC2(intn,intm){doubleproduct;inti;

for(i=m;i>=1;i--){product=product/i*(n+i);}returnproduct;}/*在輸出結果是應該注意要以整數形式輸出.*/#include<iostream>#include<iomanip>usingnamespacestd;intmain{ intn,m; cin>>n>>m; cout<<setiosflags(ios::fixed)<<setprecision(0)<<C2(n,m)<<endl; return0;}排列組合數的一般計算方法（二）使用double類型doubl12排列的生成算法字典序法:

顧名思義,這種方法就是將所有n元排列按“字典順序”排成隊，以12……n為第一個排列，排序規則，即：由一個排列P(p1,p2……pn)直接生成下一個排列的算法可歸結為：（1）求滿足pk-1<pk的k的最大值，設為i,即i=max{k|pk-1<pk}（2）求滿足pi-1<pk的k的最大值，設為j,即j=max{k|pi-1<pk}（3）pi-1與pj互換位置得（q）=（q1q2……qn）（4）(q)=（q1q2……qi-1qiqi+1……qn）中qiqi+1……qn部分的順序逆轉，得 q1q2……qi-1qqn……qi+1qi這便是下一個排列.排列的生成算法字典序法:（1）求滿足pk-1<pk的k的最大13組合的生成算法Zju1089

有n(n>=6)個數字，要求按字典序輸出所有從該n個數字中取6個的組合。SampleInput712345678123581321340SampleOutput12345612345712346712356712456713456723456712358131235821123583412351321……n組合的生成算法Zju1089SampleInputSamp14組合的生成算法Code:#include<iostream>#include<memory>#include<algorithm>usingnamespacestd;intk;intused[13];intlotto[13];voidoutput();voidchoosenext(intI,intnum);intmain(){ intn_case=0,i; while(cin>>k&&k) { if(n_case++)cout<<endl; for(i=0;i<k;i++) cin>>lotto[i]; sort(lotto,lotto+k); memset(used,0,sizeof(used)); choosenext(0,0); }return0;}組合的生成算法Code:#include<iostream>15組合的生成算法voidoutput(){ inti,n=0; for(i=0;i<k;i++){ if(used[i]){if(n)cout<<''; cout<<lotto[i]; n++; } } cout<<endl;}voidchoosenext(intI,intnum){ if(num==6){ output();return; } if(I==k)return; for(inti=I;i<k;i++){ used[i]=1; choosenext(i+1,num+1); used[i]=0; }}組合的生成算法voidoutput(){voidchoo16容斥原理1、容斥原理：|A1+A2+……+An|=∑|Ai|-∑|AiAj|+∑|AiAjAk|-…+(-1)n-1|A1A2…An|ni=11≤i<j≤n1≤i<j<k≤n2、逐步淘汰原理|A1.A2…An|=|S|-∑|Ai|+∑|AiAj|-∑|AiAjAk|+…+(-1)n|A1A2…An|i=1n1≤i<j≤n1≤i<j<k≤n另外容斥原理還有：Jordan公式和對稱原理、對稱篩。容斥原理1、容斥原理：ni=11≤i<j≤n1≤i<17容斥原理應用1、錯排問題。

問題描述：n個元素一次給以標號1，2，…，n進行全排列，求每個元素不再自己原來位置上的排列數Dn。解令Ai表示數I排在第I個位置上的所有排列，則|Ai|=(n-1)!,I=1,2,…,n|AiAj|=(n-2)!I,j=1,2,…,n;I≠j|AiAjAk|=(n-3)!I,j,k=1,2,…,n;I,j,k兩兩不相等容斥原理應用1、錯排問題。解令Ai表示數I排在第I個位置上18容斥原理應用一般地，|Ai1Ai2…Aik|=(n-k)!,k=1,2…,n我們所求的是：1不在第一位，2不在第二位，3不在第三位……n不在第n位的全排列數.即：Dn=|A1.A2…An|根據逐步淘汰原理得：Dn=n!–C(n,1)(n-1)!+C(n,2)(n-2)!-…(-1)nC(n,n)0!=n!(1-1/1!+1/2!-…+(-1)n1/n!)容斥原理應用一般地，我們所求的是：1不在第一位，219容斥原理應用例：zju1619Present

n個朋友每人買了一份禮物，混合在一起后，每人拿一份，求恰有m人拿到了恰好是自己買的禮物的概率。即:n個數的全排列中，m個保位,(n-m)個錯位的排列數占總排列數的比例。全排列數：n!m個保位,(n-m)錯位的排列數：C(n,m)Dn-m結論：p=C(n,m)Dn-m/n!容斥原理應用例：zju1619Present即:n個數的全20容斥原理應用#include<iostream>#include<iomanip>usingnamespacestd;doublejc[100];voidJC(){ jc[0]=1.0; inti; for(i=1;i<100;i++){ jc[i]=jc[i-1]/(double)i; }}容斥原理應用#include<iostream>21容斥原理應用intmain(){intm,n,curr=1;JC();while(cin>>n>>m){doubleres=0;inti; for(i=0;i<=n-m;i++){ if(i%2==0)res+=jc[i]; elseres-=jc[i];} res*=jc[m];cout<<setiosflags(ios::fixed)<<setprecision(8)<<res<<endl;} return0;}容斥原理應用intmain(){22群論

群：給定非空集合G及定義在G上的二元運算“.”，若滿足以下四個條件，則稱集合G在運算“.”下構成一個群，簡稱G群：(1)、封閉性：a,b∈G,則a.b∈G;(2)、結合律：(a.b).c=a.(b.c)(3)、單位元：存在e∈G,對任意a∈G,有a.e=e.a=a;(4)、逆元素：對任意a∈G,存在b∈G,使得a.b=b.a=e,稱b為a的逆元素，記為a-1;群論群：給定非空集合G及定義在G上的二元運算“23群論置換：n個元素1,2,…,n之間的一個置換：12…na1a2…an表示被1到n中的某個數a1取代，2被1到n中的某個數a取代，直到n被1中的某個數an取代，且a1,a2…an互不相同。置換群:置換群的元素是置換，運算是置換的連接。例如：1234123431244321=12342431群論置換：n個元素1,2,…,n之間的一個置換：1224群論循環記： (a1a2…an)=a1a2…an-1ana2a3…ana1稱為：n階循環。每個置換都可以寫成若干個互不相交的循環的乘積，兩個循環(a1a2…an)和(b1b2…bn)互不相交是指ai≠bj,i,j=1,2,…n.例如：123456356421=(136)(25)(4)循環又叫輪換，二階輪換叫對換群論循環記：a1a2…an-1an稱為：n階循環。25群論輪換上乘上一個對換的效果：(1)、對換的兩個元素分屬于不同的輪換中——兩個輪換合并成一個輪換。有連個輪換(a1,a2,a3,…an),(b1,b2,b3…,bn),一個對換(a1,b1)(a1,a2,a3,…an)(a1,b1)(b1,b2,b3…,bn)=(a1,a2,…,b1,b2…bn)(2)、對換的兩個元素屬于同一個輪換——一個輪換拆分成了兩個輪換(a1,a2,a3,…,an)(a1,ai)=(a1,a2,…ai-1)(ai,ai+1,…,an)群論輪換上乘上一個對換的效果：(1)、對換的兩個元素分屬于不26群論例：傳球游戲兩個組進行傳球比賽。每組n人，圍成一個圈，每人有一個在該組中唯一的編號（1…n之間），每人有一個編號（1…n）在改組唯一的球。每個人的球的編號是任意給定的。然后，游戲開始，每組的人開始進行組內對傳，爭取以最短的時間把球傳到位。傳到位是指一個組中的每每人手中的球的編號與他自己的編號相同。最后獲勝的就是那個用最少的地傳球次數把球傳到位的組。現需要你編一個程序從初始狀態確定至少需幾次對傳才能將球傳到位。群論例：傳球游戲27群論分析：初始狀態為一個置換，假設為：123456356432末狀態為n個長度為1的輪換：(1)(2)(3)(4)(5)(6)123456356432=(136)(25)(4)乘以(25)(136)(2)(5)(4)乘以(13)(16)(3)(2)(5)(4)乘以(16)所以：在該假設下，至少需要３次對換，分別是(25)(13)(16)群論分析：123456末狀態為n個長度為1的輪換28群論結論: 1、把初始狀態轉化成一系列輪換之積 2、若原輪換的長度為n，次數為n-1；群論結論:29Polya定理例：手鐲pku1286 如果手鐲有n個位置可用來嵌入寶石，有m種寶石可以嵌入，能生產出多少種不同類的手鐲？ 如果將其中一只手鐲做某種旋轉或翻轉使得兩個手鐲完全一樣，我們認為這兩個手鐲是同類的。翻轉旋轉Polya定理例：手鐲pku1286翻轉旋轉30Polya定理對于有4個嵌寶石位置的手鐲來說，有4種旋轉方式，有4種翻轉方式，用輪換相乘來表示：1234置換輪換相乘C(i)循環節數旋轉1(1)(2)(3)(4)4旋轉2(1234)1旋轉3(13)(24)2旋轉4(1432)1翻轉1(14)(23)2翻轉2(1)(3)(24)3翻轉3(12)(34)2翻轉4(2)(4)(13)3Polya定理對于有4個嵌寶1234置換輪換相乘C(i)循環31Polya定理Polya定理：設G是p個對象的一個置換群，用k種顏色突然這p個對象，若一種染色方案在群G的作用下變為另一種方案，則這兩個方案當作是同一種方案，這樣的不同染色方案數為：L=1G∑

f∈Gkc(f)對于手鐲一題，設n=4,m=2L=(24+2+22+2+22+23+22+23)/8=6Polya定理Polya定理：設G是p個對象的一32Polya定理置換及循環節數的計算方法:對于有n個位置的手鐲，有n種旋轉置換和n種翻轉置換對于旋轉置換:c(fi)=gcd(n,i)i為一次轉過i顆寶石。 i=0時c=n;對于翻轉置換:如果n為偶數c(f)=n/2的置換有n/2個;c(f)=n/2+1的置換有n/2個如果n為奇數，c(f)=n/2+1;Polya定理置換及循環節數的計算方法:對于有n個位置的手鐲33Polya定理Code#include<iostream>#include<cmath>#include<iomanip>usingnamespacestd;intgcd(inta,intb){returnb?gcd(b,a%b):a;}doublego(intn);intmain(){intn;while(cin>>n&&n!=-1){if(n<=0)cout<<0<<endl;elsecout<<setiosflags(ios::fixed)<<setprecision(0)<<go(n)<<endl;}return0;}

Polya定理Code#include<iostream>34Polya定理