在組合數學，一個集的元素的組合是一個子集。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項元素
重複組合理論與公式
从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 0) \\
(-1)^{n + k} C_{|n| - 1}^{|k| - 1}, & (n
演算範例
組合 C
迴圈法
/***********************/
/ This is C++ code. /
/ Comb Example /
/***********************/
#include
#include
using namespace std;
bool next_comb(vector& 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 > n >> k;
if (n = k and k must be > 0." comb(k);
for (int i = 0; i
遞迴法
#include
#include
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 && 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
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 > n >> k;
if (n
遞迴法
#include
#include
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 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!}
参见
- 概率论
- 组合数学
參考文獻
外部链接
评论 (0)