组合

组合（正體）

本文介绍的是一个数学概念。关于音乐演奏单位，详见“乐团”。

此条目或章节需要扩充，请协助改善这篇条目。（2009年10月20日）
更进一步的信息可能会在讨论页或扩充请求中找到。请在扩充条目后将此模板移除。

在组合数学，一个集的元素的组合是一个子集。S的一个k-组合是S的一个有k个元素的子集。若两个子集的元素完全相同并顺序相异，它仍视为同一个组合，这是组合和排列不同之处。

对于有n个元素的集S，当中k-组合的数目表示为二项式系数C(n, k)。

计算从有n个元素的集S中，选取k个不同元素组成的有序列的方法的数目，即是k的排列的数目，P(n,k)。
计算同样的k个元素不同排列的数目，P(k,k)。这就是它们在上面的重复出现的次数。排列的数目除以每种组合重复出现的次数，就得到C(n,k)：

${n \choose k} = \frac{P(n,k)}{P(k,k)}$ 。

根据P(n,k)的定义：

$P(n,k) = \frac{n!}{(n-k)!}$ ，

${n \choose k} = \frac{n!}{k! \cdot (n-k)!} .$

有重复的组合

如果我们选出一个元素以后，把这个元素重新放回集合S中（使这个元素在以后的选择中可以被重新选中），得到不同结果的个数为有重复的组合。其值有下面的公式给出：

${n+k-1 \choose k} = \frac{(n-1+k)!}{k! \cdot (n-1)!} = \frac{n(n+1) \cdots (n+k-1)}{k!}$ 。

解释如下：想象有 $n + k$ 个盒子排成一排。排除掉第一个盒子，我们在其中任意选取 $k$ 个盒子作为空盒子。然后把1到 $n$ 个集合中的元素依次放在剩下的盒子里面。如果某个元素被尾随了 $M$ 个连续的空盒子，那么我们就把这个元素选取M次。这样，每种选取空盒子方法就对应了一个有重复的选择元素的方法。于是，其总数为 ${n+k-1 \choose k}$ 。

参见

概率论

1个分类: 组合数学

1个隐藏分类: 自2009年10月扩充中的条目

stock | retire | vm
Why are we here?
All text is available under the terms of the GNU Free Documentation License
This page is cache of Wikipedia. History