組合

在組合數學，一個集的元素的組合（英語：Combination）是一個子集。S的一個k-組合是S的一個有k個元素的子集。若兩個子集的元素完全相同並順序相異，它仍視為同一個組合，這是組合和排列不同之處。

表示方式

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

理論與公式

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

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

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

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

在集合中取出k項元素

重複組合理論與公式

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

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)個位置擺分隔號，這組合數量為：

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

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

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

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

F_{k}^{n}=H_{k}^{n}

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

取值範圍的擴充^[3]

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

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;
	do
		comb[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;
	do
		for (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);
	else
		puts("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;
	do
		recomb[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;
	do
		for (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);
	else
		puts("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份，每份的个数分别为: $k_{1},k_{2}\cdots k_{m}$ 个，那么，总的分类数为

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

参见

參考文獻

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

外部链接

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

[1] 普通高中教科书数学选择性必修第三册（A版）. 北京市海淀区中关村南大街17号院1号楼: 人民教育出版社. : 23 [2024-03-30]. ISBN 978-7-107-34598-2.

[組合數學P33-2] 組合數學 ─算法與分析─. 九章出版社. : 33. OCLC:44527392

[組合數學P34-3] 3.0 ^3.1 組合數學 ─算法與分析─. 九章出版社. : 33. OCLC:44527392

[1]

[2]

[3]

查论编主要的数学领域
历史纲要（英语：Outline of mathematics）列表（英语：Lists of mathematics topics）符号表
数学基础	范畴论集合论数理逻辑数学哲学
代数	抽象交換群论初等代數线性代数多重线性代数泛代数
数学分析	微积分实变函数复变函数微分方程泛函分析調和分析傅立葉分析几何分析
离散数学	组合数学图论序理论博弈论
几何学	代数几何解析几何微分几何离散几何学欧几里得几何非欧几里得几何有限几何学
数论	算术代數數論解析数论几何数论算术几何丢番图几何
拓扑学	点集拓扑代数拓扑微分拓扑几何拓扑
统计学	测度与概率数理统计学数据科学统计推断迴歸分析统计学习理论机器学习人工智能数据结构与算法
计算数学	计算机科学计算理论数值分析最优化计算机代数
应用数学	控制论信息论计算化学数理生物学数理经济学计量经济学數理金融學数学心理学数学物理学生物統計學
其它	娱乐数学数学与艺术（英语：Mathematics and art）数学教育
注释	数学的领域也可根据“MSC分类标准”或“中国学科分类国家标准”进行分类。
分类主题共享资源专题