組合

  此条目页介紹的是一个数学概念。

• 關於音樂表演的編制單位，請見「樂團」。
• 關於一種可解釋為「組合」的組織型態，請見「辛迪加」。

此條目需要擴充。 (2009年10月20日) 请協助改善这篇條目，更進一步的信息可能會在討論頁或扩充请求中找到。请在擴充條目後將此模板移除。

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

表示方式[编辑]

从 n 个不同元素中取出 k 个元素的所有不同组合的个数，叫做从 n 个不同元素中取出 k 个元素的组合数，记做：${\displaystyle C(n,k)}$、${\displaystyle {}_{n}C_{k}}$、${\displaystyle {}^{n}C_{k}}$、${\displaystyle C_{k}^{n}}$（英语）、${\displaystyle C_{n}^{k}}$（法语、罗马尼亚语、俄语、汉语（中國）^[1]、波兰语）。

理論與公式[编辑]

从${\displaystyle n}$个元素中取出${\displaystyle k}$个元素，${\displaystyle k}$个元素的组合數量为：

${\displaystyle C_{k}^{n}={n \choose k}={\frac {P_{k}^{n}}{k!}}={\frac {n!}{k!(n-k)!}}}$

以六合彩為例。在六合彩中从49顆球中取出6顆球的组合數量为：

${\displaystyle C_{6}^{49}={49 \choose 6}={\frac {49!}{6!43!}}=13983816}$

在集合中取出k項元素[编辑]

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

从${\displaystyle n}$个元素中取出${\displaystyle k}$个元素，${\displaystyle k}$個元素可以重複出現，這组合數量为：

${\displaystyle 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)個位置擺分隔號，這組合數量為：

${\displaystyle H_{5}^{8}=C_{8-1}^{5+8-1}=C_{7}^{12}={\frac {12!}{7!5!}}=792}$

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

${\displaystyle H_{k}^{n}=C_{n-1}^{n+k-1}={\frac {(n+k-1)!}{k!(n-1)!}}=C_{k}^{n+k-1}}$

另外${\displaystyle H_{k}^{n}}$也可以記為${\displaystyle F_{k}^{n}}$^[2]或${\displaystyle \left(\!\!{\binom {n}{k}}\!\!\right)}$

${\displaystyle F_{k}^{n}=H_{k}^{n}}$

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

取值範圍的擴充^[3][编辑]

在${\displaystyle C_{k}^{n}}$的定義中，由於它有意義的範圍必須是滿足條件${\displaystyle n\geq k\geq 1}$，所以其他範圍必須另外定義，我們有:

${\displaystyle 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}}}$^[3]

演算範例[编辑]

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

遞迴法[编辑]

#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份，每份的个数分别为:${\displaystyle k_{1},k_{2}\cdots k_{m}}$个，那么，总的分类数为

${\displaystyle {\binom {n}{k_{1},k_{2},\cdots ,k_{m}}}={\frac {n!}{k_{1}!k_{2}!\cdots k_{m}!}}}$

参见[编辑]

• 概率论
• 组合数学

參考文獻[编辑]

1. ^ 普通高中教科书 数学 选择性必修第三册（A版）. 北京市海淀区中关村南大街17号院1号楼: 人民教育出版社. : 23 [2024-03-30]. ISBN 978-7-107-34598-2. 
2. ^ 組合數學 ─算法與分析─. 九章出版社. : 33.  OCLC:44527392
3. ^ ^{3.0 3.1} 組合數學 ─算法與分析─. 九章出版社. : 33.  OCLC:44527392

外部链接[编辑]

• 组合数公式的直观理解及其推广 （页面存档备份，存于互联网档案馆）

查 论 编 主要的数学领域 历史 纲要（英语：Outline of mathematics） 列表（英语：Lists of mathematics topics） 符号表 数学基础 范畴论 集合论 数理逻辑 数学哲学 代数 抽象 交換 群论 初等代數 线性代数 多重线性代数 泛代数 数学分析 微积分 实变函数 复变函数 微分方程 泛函分析 調和分析 傅立葉分析 几何分析 离散数学 组合数学 图论 序理论 博弈论 几何学 代数几何 解析几何 微分几何 离散几何学 欧几里得几何 非欧几里得几何 有限几何学 数论 算术 代數數論 解析数论 几何数论 算术几何 丢番图几何 拓扑学 点集拓扑 代数拓扑 微分拓扑 几何拓扑 统计学 测度与概率 数理统计学 数据科学 统计推断 迴歸分析 统计学习理论 机器学习 人工智能 数据结构与算法 计算数学 计算机科学 计算理论 数值分析 最优化 计算机代数 应用数学 控制论 信息论 计算化学 数理生物学 数理经济学 计量经济学 數理金融學 数学心理学 数学物理学 生物統計學 其它 娱乐数学 数学与艺术（英语：Mathematics and art） 数学教育 注释 数学的领域也可根据“MSC分类标准”或“中国学科分类国家标准”进行分类。 分类 主题 共享资源 专题