组合
此条目需要扩充。 (2009年10月20日) |
在组合数学，一个集的元素的组合（英语：Combination）是一个子集。S的一个k-组合是S的一个有k个元素的子集。若两个子集的元素完全相同并顺序相异，它仍视为同一个组合，这是组合和排列不同之处。
表示方式[编辑]
从 n 个不同元素中取出 k 个元素的所有不同组合的个数，叫做从 n 个不同元素中取出 k 个元素的组合数，记做：<math>C (n, k)</math>、<math>{}_{n}C_{k}</math>、<math>{}^{n}C_{k}</math>、<math>C^n_k</math>（英语）、<math>C_n^k</math>（法语、罗马尼亚语、俄语、汉语、波兰语）。
理论与公式[编辑]
从<math>n</math>个元素中取出<math>k</math>个元素，<math>k</math>个元素的组合数量为：
- <math>C^n_k ={n \choose k} = \frac{P^n_k}{k!} = \frac{n!}{k!(n-k)!}</math>
以六合彩为例。在六合彩中从49颗球中取出6颗球的组合数量为：
- <math>C^{49}_{6} = {49 \choose 6} = \frac{49!}{6!43!} = 13983816</math>
在集合中取出k项元素[编辑]
重复组合理论与公式[编辑]
从<math>n</math>个元素中取出<math>k</math>个元素，<math>k</math>个元素可以重复出现，这组合数量为：
- <math>H_k^n = C_{n-1}^{n+k-1}</math>
以取色球为例，每种颜色的球有无限多颗，从8种色球中取出5颗球，好比是在5颗球间画上分隔号“|”代表球色的分布情形(隔板法)。例如第1种色球取1颗，第2种色球取2颗，第3种色球取2颗可以表示成：
- 球|球球|球球| | | | |
可以理解为8类球每类取多少个，一起构成5个球。我们把5个球排成一排，用7个分隔线去隔开。如上图，表示含义：第1根线前表示第一类球取的个数，第1根和第2根线表示第二类球取的个数...第6第7根线前表示第七类球的个数，第7根后表示第八类球的个数。亦即问题是从(5+8-1)个位置中挑选出(8-1)个位置摆分隔号，这组合数量为：
- <math>H_5^8 = C_{8-1}^{5+8-1} = C_7^{12} = \frac{12!}{7!5!} = 792</math>
因为组合数量公式特性，重复组合转换成组合有另一种公式为：
- <math>H_k^n=C_{n-1}^{n+k-1}=\frac{(n+k-1)!}{k!(n-1)!}=C_{k}^{n+k-1}</math>
另外<math>H_k^n</math>也可以记为<math>F_k^n</math>[1]或<math>\left(\!\!\binom{n}{k}\!\!\right)</math>
- <math>F_k^n = H_k^n</math>
- <math>\left(\!\!\binom{n}{k}\!\!\right) = H_k^n</math>
取值范围的扩充[1][编辑]
在<math>C_k^n</math>的定义中，由于它有意义的范围必须是满足条件<math>n \ge k \ge 1</math>，所以其他范围必须另外定义，我们有:
- <math>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}</math>[1]
演算范例[编辑]
组合 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份，每份的个数分别为:<math> k_1,k_2\cdots k_m</math>个，那么，总的分类数为
- <math>\binom{n}{k_1,k_2,\cdots, k_m}=\frac{n!}{k_1!k_2!\cdots k_m!}</math>
