組合

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

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

對於有n個元素的集S,當中k-組合的數目表示為二項式係數C(n, k)。

  1. 計算從有n個元素的集S中,選取k個不同元素組成的有序列的方法的數目,即是k的排列的數目,P(n,k)。
  2. 計算同樣的k個元素不同排列的數目,P(k,k)。這就是它們在上面的重複出現的次數。排列的數目除以每種組合重複出現的次數,就得到C(n,k):
 {n \choose k} = \frac{P(n,k)}{P(k,k)}

根據P(n,k)的定義:

 P(n,k) = \frac{n!}{(n-k)!}
 {n \choose k} = \frac{n!}{k! \cdot (n-k)!}

有重复的组合[编辑]

如果我们选出一个元素以后,把这个元素重新放回集合S中(使这个元素在以后的选择中可以被重新选中),得到不同结果的个数为有重复的组合。其值有下面的公式给出:

 {n+k-1 \choose k} = H_k^n  = \frac{(n-1+k)!}{k! \cdot (n-1)!} = \frac{n(n+1) \cdots (n+k-1)}{k!}

解释如下:想像有n+k个盒子排成一排。排除掉第一个盒子,我们在其中任意选取k个盒子作为空盒子。然后把1到n个集合中的元素依次放在剩下的盒子裡面。如果某个元素被尾随了M个连续的空盒子,那么我们就把这个元素选取M次。这样,每种选取空盒子方法就对应了一个有重复的选择元素的方法。于是,其总数为 {n+k-1 \choose k}

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

C_n^r的定義中,由於它有意義的範圍必須是滿足條件n \ge r \ge 1,所以其他範圍必須另外定義,我們有:

{n \choose r} = C_n^r = \begin{cases} 
1,  & r = 0 \\
0, & 0 \leq n < r \lor r < 0 \leq n\\
(-1)^{r} {\left| n \right| + r - 1 \choose r}, & n<0 \land r>0 \\
(-1)^{n+r} {\left| r \right| - 1 \choose \left| n \right| - 1}, & n<0 \land r < 0 
\end{cases}[1]

演算範例[编辑]

組合 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;
	int* comb = new int[n];
	for (int i = 0; i < k; i++)
		comb[i] = i;
	do {
		for (int i = 0; i < k; i++)
			cout << comb[i] + 1 << ((i + 1 < k) ? ',' : '\n');
	} 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;
	int* recomb = new int[n];
	for (int i = 0; i < k; i++)
		recomb[i] = 0;
	do {
		for (int i = 0; i < k; i++)
			cout << recomb[i] + 1 << ((i + 1 < k) ? ',' : '\n');
	} while (next_re_comb(recomb, n, k));
	delete[] recomb;
	return 0;
}

参见[编辑]

參考文獻[编辑]

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