【概念】

1.組合

從 n 個元素的集合 S 中，無序的選出 r 個元素，叫做 S 的一個 r 組合。

如果兩個組合中，至少有一個元素不同，它們就被認為是不同的組合。

2.不可重組合數

所有不同組合的個數，叫做組合數，記作：?或?

由于每一種組合都可以擴展到 r！種排列，而總排列為 A(n,r) ，所以組合數

特別的，C(n,0)=1

3.可重復組合數

從 n 個不同的元素中，無序的選出 r 個元素組成一個組合，且允許這 r 個元素重復使用，則稱這樣的組合為可重復組合。

其組合數記為：

4.不相鄰組合數

從 A={1,2,...,n} 中選取 m 個不相鄰的組合，其組合數為：

例題：

①?一班有10名同學，二班有8名同學，現每個班級要選出2名學生參加一個座談會，求有多少種選法？

根據組合數與乘法原理，共有：C(10,2)*C(8,2)=1260 種

② 某班有10名同學，有4名女同學，現要選出3名學生，其中至少有一名女同學，求有多少種選法？

根據組合數與加法原理，共有：C(4,1)*C(6,2)+C(4,2)*C(6,1)+C(4,3)*C(6,0)=60+36+4=100 種

【組合數常用公式】

1）

2）

3）

4）（二項式定理）

特殊展開：

5）?為奇數時有 n&m=n?

【求組合數的方法】

首先 C(n,m) 的值一定是自然數，因為連續 m?個自然數的積一定被 m! 整除，因此求 C(n,m) 的值關鍵在于如何避免做除法。

1.遞歸計算

利用公式??來遞歸的計算組合數

LL cal(LL n,LL k){if(n<k||k==0)return 0;if(n==k||k==1)return 1;return cal(n-1,k-1)+k*cal(n-1,k); } int main(){LL n,k;cin>>n>>k;cout<<cal(n,k)<<endl;return 0; }

2.楊輝三角打表

利用公式?，將計算 C(n,r) 的過程化為加法來做，由于二項式展開系數的與楊輝三角一致，故該方法的實質就是求楊輝三角第 n 行，第 r 列上的數。

int f[N][N]; int main() {f[0][0]=1;for(int i=1;i<=N-1;i++)for(int j=1;j<=i+1;j++)f[i][j]=f[i-1][j]+f[i-1][j-1];int n,r;scanf("%d%d",&n,&r);printf("%d\n",f[n+1][r+1]);return 0; }

3.公式化簡打表

用 ，由于除以 m，因此相對沒那么容易越界

int C[N]; void calculate(int n,int m){//C[i]即為C(n,i)的值C[0]=1;for(int i=1;i<=n;i++)C[i]=C[i-1]*(n-i+1)/i; }

4.約分求重數

約分之后，分母即會變為 1，借此將除法化為乘法，約分方法是計算 1 到 n 之間的任意一個質數在 C(n,r) 的重數。

具體做法是對分子分母上的每個數分解質因子，用一個數組 C[] 來記錄重數，若分子上的數分解一個質因子 p，則 C[p]++，反之若分母上的數分解出質因子 p，則 C[p]--，最后將每個質因子按其重數連乘即可。

將公式化為?，通過直接計算質數 p 在 n! 中的重數而得到數組 C[]，質數 p 在自然數 n 中的重數是指自然數 n 的質因數分解式質數 p 出現的次數，質數 p 在 n! 的重數為：?，根據公式：，可以遞推的求出 p 在 n！中的重數。

例如：72=2*2*2*3*3，質數 2 在 72 的重數是 3，質數 3 在 72 的重數是 2；n=1000，p=3時，有 1000 div 3+1000 div 9+1000 div 27+1000 div 81+1000 div 243+1000 div 729=333+111+37+12+4+1=498，因此 1000！能被 3^498 整除，但不能被 3^499 整除，使用遞推公式后，有：333 div 3=111 ,111 div 3=37,37 div 3=12,12 div 3=4,4 div 3=1

程序實現時，先求出 1 到 n 間所有質數，再對每個質數求重數，從而計算從 n-r+1 到 n 的因子的重數與從 1 到 r 的因子的重數，前者減去后者，C[i] 中所存儲的即為約分后質數因子的重數，再利用高精度加法，將答案存儲，最后倒序輸出即可。

#include<cstdio> #include<cstring> #include<vector> const int N=30000; vector<int> prime,C; bool vis[N]; int res[10]; void Get_Prime() {memset(vis,true,sizeof(vis));for(int i=2;i<=N;i++){if(vis[i]){prime.push_back(i);//存儲質數C.push_back(0);//當前質數的重數為0for(int j=i*i;j<=N;j+=i)//篩除所有以i為因子的數vis[j]=false;}} } void Add(int n,int p)//記錄重數個數 {for(int i=0;i<prime.size()&&prime[i]<=n;i++){while(!(n%prime[i])){n/=prime[i];C[i]+=p;}} } int main() {Get_Prime();//打表獲取質數int n,r;scanf("%d%d",&n,&r);if(r>n-r)//根據公式C(n,r)=C(n,n-r)簡化計算r=n-r;for(int i=0;i<r;i++){Add(n-i,1);//將n-r+1到n的因子加到C中去Add(i+1,-1);//將1到r的因子從C中減去}memset(res,0,sizeof(res));res[0]=1;for(int i=0;i<prime.size();i++)//枚舉所有質數{for(int j=0;j<C[i];j++)//枚舉對應質數的重數{for(int k=0;k<10;k++)res[k]*=prime[i];for(int k=0;k<10;k++)//高精存儲答案{if(k<9)res[k+1]+=res[k]/10;res[k]%=10;}}}for(int i=9;i>=0;i--)printf("%d",res[i]);printf("\n");return 0; }

【例題】

• Rooks（LightOJ-1005）(排列+組合)：點擊這里
• Wall Painting（HDU-4810）(楊輝三角組合數打表+二進制枚舉)：點擊這里
• Combinations（POJ-1306）(公式化簡法求組合數)：點擊這里
• Binomial Showdown（POJ-2249）(公式化簡法求組合數)：點擊這里
• 集合的劃分（信息學奧賽一本通-T1315）(遞歸法求組合數)：點擊這里

總結

以上是生活随笔為你收集整理的组合数学 —— 组合数的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。