組合

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

## 表示方式

從 n 個不同元素中取出 k 個元素的所有不同組合的個數，稱為從 n 個不同元素中取出 k 個元素的組合數，記做：$C (n, k)$、${}_{n}C_{k}$、${}^{n}C_{k}$、$C^n_k$（英語、香港、台灣）、$C_n^k$（法語、羅馬尼亞語、俄語、中國內地、波蘭語）。

## 理論與公式

從$n$個元素中取出$k$個元素，$k$個元素的組合數量為：

$$C^n_k ={n \choose k} = \frac{P^n_k}{k!} = \frac{n!}{k!(n-k)!}$$

以六合彩為例。在六合彩中從49顆球中取出6顆球的組合數量為：

$$C^{49}_{6} = {49 \choose 6} = \frac{49!}{6!43!} = 13983816$$

## 在集合中取出k項元素

<image>

## 重複組合理論與公式

從$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$或$\left(\!\!\binom{n}{k}\!\!\right)$

$$F_k^n = H_k^n$$

$$\left(\!\!\binom{n}{k}\!\!\right) = H_k^n$$

## 取值範圍的擴充

在$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}$

## 演算範例

### 組合 C

#### 迴圈法

```cpp
/***********************/
/** This is C++ code. **/
/**   Comb  Example   **/
/***********************/

#include <iostream>
#include <vector>
using namespace std;

bool next_comb(vector<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 false;
    while (++i < k)
        comb[i] = comb[i - 1] + 1;
    return true;
}

int main() {
    int n, k;
    cout << "comb(n, k):" << endl;
    cin >> n >> k;

    if (n < k || k <= 0) {
        cout << "Invalid input: n must be >= k and k must be > 0." << endl;
        return 0;
    }

    vector<int> comb(k);
    for (int i = 0; i < k; i++)
        comb[i] = i;

    do {
        for (int i = 0; i < k; i++) {
            cout << comb[i] + 1;
            if (i < k - 1) cout << ',';
        }
        cout << endl;
    } while (next_comb(comb, n, k));

    return 0;
}
```

#### 遞迴法

```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;
}
```

### 重複組合 H

#### 迴圈法

```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;
}
```

#### 遞迴法

```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;
}
```

## 推廣

組合數可以推廣到多分類的情形，我們將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!}$$