組合

从 n 个不同元素中取出 k 个元素的所有不同组合的个数，叫做从 n 个不同元素中取出 k 个元素的组合数，记做：${\displaystyle C(n,k)}$ 、${\displaystyle {}_{n}C_{k}}$ 、${\displaystyle {}^{n}C_{k}}$ 、${\displaystyle C_{k}^{n}}$ （英语）、${\displaystyle C_{n}^{k}}$ （法语、罗马尼亚语、俄语、汉语（中國）^[1]、波兰语）。

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

${\displaystyle C_{k}^{n}={n \choose k}={\frac {P_{k}^{n}}{k!}}={\frac {n!}{k!(n-k)!}}}$

以六合彩為例。在六合彩中从49顆球中取出6顆球的组合數量为：

${\displaystyle C_{6}^{49}={49 \choose 6}={\frac {49!}{6!43!}}=13983816}$

从${\displaystyle n}$ 个元素中取出${\displaystyle k}$ 个元素，${\displaystyle k}$ 個元素可以重複出現，這组合數量为：

${\displaystyle H_{k}^{n}=C_{n-1}^{n+k-1}}$

以取色球為例，每種顏色的球有無限多顆，從8種色球中取出5顆球，好比是在5顆球間畫上分隔號“|”代表球色的分布情形。例如第1種色球取1顆，第2種色球取2顆，第3種色球取2顆可以表示成：

球|球球|球球| | | | |

可以理解为8类球每类取多少个，一起构成5个球。我们把5个球排成一排，用7个分隔线去隔开。如上图，表示含义：第1根线前表示第一类球取的个数，第1根和第2根线表示第二类球取的个数...第6第7根线前表示第七类球的个数，第7根后表示第八类球的个数。亦即問題是從(5+8-1)個位置中挑選出(8-1)個位置擺分隔號，這組合數量為：

${\displaystyle H_{5}^{8}=C_{8-1}^{5+8-1}=C_{7}^{12}={\frac {12!}{7!5!}}=792}$

因為組合數量公式特性，重複組合轉換成組合有另一種公式為：

${\displaystyle H_{k}^{n}=C_{n-1}^{n+k-1}={\frac {(n+k-1)!}{k!(n-1)!}}=C_{k}^{n+k-1}}$

另外${\displaystyle H_{k}^{n}}$ 也可以記為${\displaystyle F_{k}^{n}}$ ^[2]或${\displaystyle \left(\!\!{\binom {n}{k}}\!\!\right)}$

${\displaystyle F_{k}^{n}=H_{k}^{n}}$

${\displaystyle \left(\!\!{\binom {n}{k}}\!\!\right)=H_{k}^{n}}$

在${\displaystyle C_{k}^{n}}$ 的定義中，由於它有意義的範圍必須是滿足條件${\displaystyle n\geq k\geq 1}$ ，所以其他範圍必須另外定義，我們有:

${\displaystyle C_{k}^{n}={\begin{cases}1,&k=0\\0,&(0\leq n<k)\lor (k<0\leq n)\\(-1)^{k}C_{k}^{|n|+k-1},&(n<0)\land (k>0)\\(-1)^{n+k}C_{|n|-1}^{|k|-1},&(n<0)\land (k<0)\end{cases}}}$ ^[3]

組合 C 编辑

迴圈法 编辑

/***********************//** This is C++ code. **//**   Comb  Example   **//***********************/#include <iostream>using namespace std;bool next_comb(int* comb, const int n, const int k) {int i = k - 1;const int e = n - k;docomb[i]++;while (comb[i] > e + i && i--);if (comb[0] > e)return 0;while (++i < k)comb[i] = comb[i - 1] + 1;return 1;}int main() {int n, k;cout << "comb(n,k):" << endl;cin >> n >> k;if (n < k || k <= 0)return 0;int* comb = new int[k];for (int i = 0; i < k; i++)comb[i] = i;dofor (int i = 0; i < k; cout << ((++i < k) ? ',' : '\n'))cout << comb[i] + 1;while (next_comb(comb, n, k));delete[] comb;return 0;}

遞迴法 编辑

#include <iostream>#include <cstdio>using namespace std;namespace comb {int n, k;int arr[12];int count;bool arrsame(int site) {if (site > 0 && arr[site - 1] >= arr[site])return 0;return 1;}inline void arrprint() {for (int i = 0; i < k; i++)printf("%3d", arr[i]);puts("");count++;}void calculate(int now) {if (now == k) {arrprint();return;}for (int i = 0; i < n; i++) {arr[now] = i;if (arrsame(now)) {calculate(now + 1);}}}inline void run(int nn, int kk) {n = nn, k = kk;count = 0;if (k < 12 && n >= k && k > 0)calculate(0);if (count)printf("\n%d combination.\n\n", count);elseputs("Input error!");}}int main() {int n, k;while (scanf("%d%d", &n, &k) != EOF) {comb::run(n, k);fflush(stdout);}return 0;}

重複組合 H 编辑

迴圈法 编辑

/***********************//** This is C++ code. **//**  ReComb  Example  **//***********************/#include <iostream>using namespace std;bool next_re_comb(int* recomb, const int n, const int k) {int i = k - 1;dorecomb[i]++;while (recomb[i] > n - 1 && i--);if (recomb[0] > n - 1)return 0;while (++i < k)recomb[i] = recomb[i - 1];return 1;}int main() {int n, k;cout << "recomb(n,k):" << endl;cin >> n >> k;if (n <= 0 || k <= 0)return 0;int* recomb = new int[k];for (int i = 0; i < k; i++)recomb[i] = 0;dofor (int i = 0; i < k; cout << ((++i < k) ? ',' : '\n'))cout << recomb[i] + 1;while (next_re_comb(recomb, n, k));delete[] recomb;return 0;}

遞迴法 编辑

#include <iostream>#include <cstdio>using namespace std;namespace re_comb {int n, k;int arr[12];int count;bool arrsame(int site) {if (site > 0 && arr[site - 1] > arr[site])return 0;return 1;}inline void arrprint() {for (int i = 0; i < k; i++)printf("%3d", arr[i]);puts("");count++;}void calculate(int now) {if (now == k) {arrprint();return;}for (int i = 0; i < n; i++) {arr[now] = i;if (arrsame(now)) {calculate(now + 1);}}}inline void run(int nn, int kk) {n = nn, k = kk;count = 0;if (k < 12 && k > 0)calculate(0);if (count)printf("\n%d combination.\n\n", count);elseputs("Input error!");}}int main() {int n, k;while (scanf("%d%d", &n, &k) != EOF) {re_comb::run(n, k);fflush(stdout);}return 0;}

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

${\displaystyle {\binom {n}{k_{1},k_{2},\cdots ,k_{m}}}={\frac {n!}{k_{1}!k_{2}!\cdots k_{m}!}}}$

• 概率论
• 组合数学

1. ^ 普通高中教科书 数学 选择性必修第三册（A版）. 北京市海淀区中关村南大街17号院1号楼: 人民教育出版社. : 23 [2024-03-30]. ISBN 978-7-107-34598-2. 
2. ^ 組合數學 ─算法與分析─. 九章出版社. : 33.  OCLC:44527392
3. ^ ^{3.0 3.1} 組合數學 ─算法與分析─. 九章出版社. : 33.  OCLC:44527392

• 组合数公式的直观理解及其推广 （页面存档备份，存于互联网档案馆）