組合

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

對於有n個元素的集S，當中k-組合的數目表示為二項式係數C(n, k)。

1. 計算從有n個元素的集S中，選取k個不同元素組成的有序列的方法的數目，即是k的排列的數目，P(n,k)。
2. 計算同樣的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} = H_k^n = \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}$。

取值範圍的擴充

在$C_r^n$的定義中，由於它有意義的範圍必須是滿足條件$n \ge r \ge 1$，所以其他範圍必須另外定義，我們有:

${n \choose r} = C_r^n = \begin{cases} 1, & r = 0 \\ 0, & 0 \leq n 0 \\ (-1)^{n+r} {\left| r \right| - 1 \choose \left| n \right| - 1}, & n<0 \land r < 0 \end{cases}$

参见

• 概率论
• 组合数学
• 排列组合符号