組合

维基百科,自由的百科全书
跳转至: 导航搜索

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

理論與公式[编辑]

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項元素[编辑]

在有五個元素中的集合中,取出3個元素,形成的子集合

重複組合理論與公式[编辑]

n个元素中取出k个元素,k個元素可以重複出現,這组合數量为:

H_k^n = C_{k}^{n+k-1}

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

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

亦即問題是從(5+8-1)個位置中挑選出(8-1)個位置擺分隔號,這組合數量為:

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

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

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

另外H_k^n也可以記為F_k^n[1]

F_k^n = H_k^n

取值範圍的擴充[2][编辑]

C_k^n的定義中,由於它有意義的範圍必須是滿足條件n \ge k \ge 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}[2]

演算範例[编辑]

組合 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;
}

重複組合 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;
}

推广[编辑]

组合数可以推广到多分类的情形 ,我们将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!}

参见[编辑]

參考文獻[编辑]

  1. ^ 組合數學 ─算法與分析─. 九章出版社. : 33.  OCLC:44527392
  2. ^ 2.0 2.1 組合數學 ─算法與分析─. 九章出版社. : 33.  OCLC:44527392

外部链接[编辑]