组合

在组合数学，一个集的元素的组合（英语：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]

表示方式[编辑]

理论与公式[编辑]

在集合中取出k项元素[编辑]

重复组合理论与公式[编辑]

取值范围的扩充[3][编辑]

演算范例[编辑]

组合 C[编辑]

循环法[编辑]

递回法[编辑]

重复组合 H[编辑]

循环法[编辑]

递回法[编辑]

推广[编辑]

参见[编辑]

参考文献[编辑]

外部链接[编辑]

取值范围的扩充^[3][编辑]