组合

在组合数学，一个集的元素的组合（英语：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分类标准”或“中国学科分类国家标准”进行分类。
分类主题共享资源专题