組合

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

表示方式

從 n 個不同元素中取出 k 個元素的所有不同組合的個數，叫做從 n 個不同元素中取出 k 個元素的組合數，記做： $C(n,k)$ 、 ${}_{n}C_{k}$ 、 ${}^{n}C_{k}$ 、 $C_{k}^{n}$ （英語）、 $C_{n}^{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項元素

重複組合理論與公式

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

F_{k}^{n}=H_{k}^{n}

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

取值範圍的擴充^[2]

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

^[2]

演算範例

組合 C

迴圈法

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

遞迴法

#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}!}}

參見

參考文獻

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

外部連結

組合數公式的直觀理解及其推廣（頁面存檔備份，存於互聯網檔案館）

[組合數學P33-1] 組合數學 ─算法與分析─. 九章出版社. : 33. OCLC:44527392

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

[1]

[2]

閱論編主要的數學領域
歷史綱要（英語：Outline of mathematics）列表（英語：Lists of mathematics topics）符號表
數學基礎	範疇論集合論數理邏輯數學哲學
代數	抽象交換群論初等代數線性代數多重線性代數泛代數
數學分析	微積分實變函數複變函數微分方程泛函分析調和分析傅立葉分析幾何分析
離散數學	組合數學圖論序理論博弈論
幾何學	代數幾何解析幾何微分幾何離散幾何學歐幾里得幾何非歐幾里得幾何有限幾何學
數論	算術代數數論解析數論幾何數論算術幾何丟番圖幾何
拓撲學	點集拓撲代數拓撲微分拓撲幾何拓撲
統計學	測度與概率數理統計學數據科學統計推斷迴歸分析統計學習理論機器學習人工智能數據結構與算法
計算數學	計算機科學計算理論數值分析最優化計算機代數
應用數學	控制論信息論計算化學數理生物學數理經濟學計量經濟學數理金融學數學心理學數學物理學生物統計學
其它	娛樂數學數學與藝術（英語：Mathematics and art）數學教育
註釋	數學的領域也可根據「MSC分類標準」或「中國學科分類國家標準」進行分類。
分類主題共享資源專題