理论与公式

从 n {\displaystyle n} 个元素中取出 k {\displaystyle k} 个元素， k {\displaystyle k} 个元素的组合数量为：

以六合彩为例。在六合彩中从49颗球中取出6颗球的组合数量为：

在集合中取出k项元素

  在有五个元素中的集合中，取出3个元素，形成的子集合

重复组合理论与公式

从 n {\displaystyle n} 个元素中取出 k {\displaystyle k} 个元素， k {\displaystyle k} 个元素可以重复出现，这组合数量为：

以取色球为例，每种颜色的球有无限多颗，从8种色球中取出5颗球，好比是在5颗球间画上分隔号“|”代表球色的分布情形。例如第1种色球取1颗，第2种色球取2颗，第3种色球取2颗可以表示成：

可以理解为8类球每类取多少个，一起构成5个球。我们把5个球排成一排，用7个分隔线去隔开。如上图，表示含义：第1根线前表示第一类球取的个数，第1根和第2根线表示第二类球取的个数...第6第7根线前表示第七类球的个数，第7根后表示第八类球的个数。亦即问题是从(5+8-1)个位置中挑选出(8-1)个位置摆分隔号，这组合数量为：

因为组合数量公式特性，重复组合转换成组合有另一种公式为：

另外 H k n {\displaystyle H_{k}^{n}} 也可以记为 F k n {\displaystyle F_{k}^{n}} 或 ( ( n k ) ) {\displaystyle \left(\!\!{\binom {n}{k}}\!\!\right)}

取值范围的扩充

在 C k n {\displaystyle C_{k}^{n}} 的定义中，由于它有意义的范围必须是满足条件 n ≥ ≥ --> k ≥ ≥ --> 1 {\displaystyle n\geq k\geq 1} ，所以其他范围必须另外定义，我们有:

演算范例

组合 C

循环法

/***********************//** This is C++ code. **//** Comb Example **//***********************/#includeusingnamespacestd;boolnext_comb(int*comb,constintn,constintk){inti=k-1;constinte=n-k;docomb[i]++;while(comb[i]>e+i&&i--);if(comb[0]>e)return0;while(++i<k)comb[i]=comb[i-1]+1;return1;}intmain(){intn,k;cout<<"comb(n,k):"<>n>>k;if(n<k||k<=0)return0;int*comb=newint[k];for(inti=0;i<k;i++)comb[i]=i;dofor(inti=0;i<k;cout<<((++i<k)?",":"\n"))cout<<comb[i]+1;while(next_comb(comb,n,k));delete[]comb;return0;}

递回法

#include#includeusingnamespacestd;namespacecomb{intn,k;intarr[12];intcount;boolarrsame(intsite){if(site>0&&arr[site-1]>=arr[site])return0;return1;}inlinevoidarrprint(){for(inti=0;i<k;i++)printf("%3d",arr[i]);puts("");count++;}voidcalculate(intnow){if(now==k){arrprint();return;}for(inti=0;i<n;i++){arr[now]=i;if(arrsame(now)){calculate(now+1);}}}inlinevoidrun(intnn,intkk){n=nn,k=kk;count=0;if(k=k&&k>0)calculate(0);if(count)printf("\n%d combination.\n\n",count);elseputs("Input error!");}}intmain(){intn,k;while(scanf("%d%d",&n,&k)!=EOF){comb::run(n,k);fflush(stdout);}return0;}

重复组合 H

循环法

/***********************//** This is C++ code. **//** ReComb Example **//***********************/#includeusingnamespacestd;boolnext_re_comb(int*recomb,constintn,constintk){inti=k-1;dorecomb[i]++;while(recomb[i]>n-1&&i--);if(recomb[0]>n-1)return0;while(++i<k)recomb[i]=recomb[i-1];return1;}intmain(){intn,k;cout<<"recomb(n,k):"<>n>>k;if(n<=0||k<=0)return0;int*recomb=newint[k];for(inti=0;i<k;i++)recomb[i]=0;dofor(inti=0;i<k;cout<<((++i<k)?",":"\n"))cout<<recomb[i]+1;while(next_re_comb(recomb,n,k));delete[]recomb;return0;}

递回法

#include#includeusingnamespacestd;namespacere_comb{intn,k;intarr[12];intcount;boolarrsame(intsite){if(site>0&&arr[site-1]>arr[site])return0;return1;}inlinevoidarrprint(){for(inti=0;i<k;i++)printf("%3d",arr[i]);puts("");count++;}voidcalculate(intnow){if(now==k){arrprint();return;}for(inti=0;i<n;i++){arr[now]=i;if(arrsame(now)){calculate(now+1);}}}inlinevoidrun(intnn,intkk){n=nn,k=kk;count=0;if(k0)calculate(0);if(count)printf("\n%d combination.\n\n",count);elseputs("Input error!");}}intmain(){intn,k;while(scanf("%d%d",&n,&k)!=EOF){re_comb::run(n,k);fflush(stdout);}return0;}

推广

组合数可以推广到多分类的情形 ，我们将n个物品分为m份，每份的个数分别为: k 1 , k 2 ⋯ ⋯ --> k m {\displaystyle k_{1},k_{2}\cdots k_{m}} 个，那么，总的分类数为

参见

概率论

组合数学

免责声明：以上内容版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。感谢每一位辛勤著写的作者，感谢每一位的分享。