查看“組合”的源代码

{{Other uses list|一个数学概念|音樂表演的編制單位|樂團|一種可解釋為「組合」的組織型態|辛迪加}}
{{Expand|time=2009-10-20}}
在[[組合數學]]，一個[[集合 (数学)|集]]的元素的'''組合'''（{{lang-en|Combination}}）是一個[[子集]]。''S''的一個''k''-組合是''S''的一個有k個元素的子集。若兩個子集的元素完全相同並順序相異，它仍視為同一個組合，這是組合和[[排列]]不同之處。

==理論與公式==
从<math>n</math>个元素中取出<math>k</math>个元素，<math>k</math>个元素的组合數量为：
:<math>C^n_k ={n \choose k} = \frac{P^n_k}{k!} = \frac{n!}{k!(n-k)!}</math>

以[[六合彩]]為例。在六合彩中从49顆球中取出6顆球的组合數量为：
:<math>C^{49}_{6}  = {49 \choose 6} = \frac{49!}{6!43!} = 13983816</math>

== 在集合中取出k項元素==
[[File:Combinations without repetition; 5 choose 3.svg|thumb|在有五個元素中的集合中，取出3個元素，形成的子集合]]
{{main|二項式係數}}

==重複組合理論與公式==

从<math>n</math>个元素中取出<math>k</math>个元素，<math>k</math>個元素可以重複出現，這组合數量为：
:<math>H_k^n = C_{k}^{n+k-1}</math>

以取色球為例，每種顏色的球有無限多顆，從8種色球中取出5顆球，好比是在5顆球間畫上[[分隔號]]“|”代表球色的分布情形。例如第1種色球取1顆，第2種色球取2顆，第3種色球取2顆可以表示成：
:<font color="red">球</font>|<font color="blue">球球</font>|<font color="green">球球</font>| | | | |
可以理解为8类球每类取多少个，一起构成5个球。我们把5个球排成一排，用7个分隔线去隔开。如上图，表示含义：第1根线前表示第一类球取的个数，第1根和第2根线表示第二类球取的个数...第6第7根线前表示第七类球的个数，第7根后表示第八类球的个数。亦即問題是從(5+8-1)個位置中挑選出(8-1)個位置擺分隔號，這組合數量為：
:<math>H_5^8 = C_{5}^{8+5-1} = C_5^{12} = \frac{12!}{5!7!} = 792</math>

因為組合數量公式特性，重複組合轉換成組合有另一種公式為：
:<math>H_k^n=C_{n-1}^{n+k-1}=\frac{(n+k-1)!}{k!(n-1)!}=C_{k}^{n+k-1}</math>

另外<math>H_k^n</math>也可以記為<math>F_k^n</math><ref name="組合數學P33">{{cite book | title=組合數學 ─算法與分析─ | publisher=九章出版社 |  pages=33}} OCLC:44527392 </ref>或<math>\left(\!\!\binom{n}{k}\!\!\right)</math>
:<math>F_k^n = H_k^n</math>
:<math>\left(\!\!\binom{n}{k}\!\!\right) = H_k^n</math>

== 取值範圍的擴充<ref name="組合數學P34">{{cite book | title=組合數學 ─算法與分析─ | publisher=九章出版社 |  pages=33}} OCLC:44527392 </ref> ==
在<math>C_k^n</math>的定義中，由於它有意義的範圍必須是滿足條件<math>n \ge k \ge 1</math>，所以其他範圍必須另外定義，我們有:
:<math>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}</math><ref name="組合數學P34"/>

== 演算範例 ==
=== 組合 C ===
==== 迴圈法 ====
<source lang="cpp">

/***********************/
/** 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;
}

</source>
==== 遞迴法 ====
<source lang="cpp">
#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;
}

</source>

=== 重複組合 H ===

====迴圈法====
<source lang="cpp">

/***********************/
/** 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;
}

</source>
====遞迴法====
<source lang="cpp">
#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;
}
</source>

== 推广 ==
组合数可以推广到多分类的情形  ，我们将n个物品分为m份，每份的个数分别为:<math>
k_1,k_2\cdots k_m</math>个，那么，总的分类数为
:<math>\binom{n}{k_1,k_2,\cdots, k_m}=\frac{n!}{k_1!k_2!\cdots k_m!}</math>

== 参见 ==
{{mathportal}}
* [[概率论]]
* [[组合数学]]
[[Category:组合数学]]

== 參考文獻 ==
<references/>
== 外部链接 ==
* [http://www.fuzihao.org/blog/2015/02/27/%E7%BB%84%E5%90%88%E6%95%B0%E5%85%AC%E5%BC%8F%E7%9A%84%E7%9B%B4%E8%A7%82%E7%90%86%E8%A7%A3%E5%8F%8A%E5%85%B6%E6%8E%A8%E5%B9%BF/  组合数公式的直观理解及其推广]

{{Template:数学主要领域}}