排列与组合 Permutation and Combination

数学中,假设集合S包含n个元素（由集合的定义可知，这n个元素不同，且没有先后顺序），以下讨论的S均指这个集合。

排列 Arrangement / Permutation

从集合S中无序选取k个元素出来，按取出元素的先后顺序将取出的k个元素排成一个序列(Sequence)，这个序列称为S的一个k-排列(k-permutation)。

注意到取出的元素排成一个序列。两个排列相等 <==> 两个序列相等 <==> 两序列所含元素及其数量相同，且元素排列顺序相同。
例如(1,2,3)与(2,1,3)是不同的序列，因为前两个元素的顺序不同。

由上述排列相等的要求可知，不同选取方法得到的排列是不同的。

排列数 the number of permutations

从n个元素无序选取k个元素所能取得的不同排列总数称为排列数(the number of permutations)，通常记为$A_n^k$或A(n,k)。
推导如下：
取第1个元素可在n个元素任取，即有n种取法；第2个在n-1个元素任取；第3个在n-2个元素任取…第k个在n-k+1个元素任取。
由概率的乘法公式可得，n个元素中无序选取k个元素出来的排列有$A_n^k$ = n(n-1)(n-2)•••（n-k+1)=${n!} \over {(n-k)!}$个。
当k=n时，该排列称为全排列，此时$A_n^n$ = ${n!} \over {(n-n)!}$ = ${n!} \over {(0)!}$ = ${n!} \over {1}$ = n!
当k>n时，$A_n^k = 0$

组合 Combination

从集合S中无序选取k个元素出来，作为一个新的集合(set)，该集合称为S的一个k-组合(k-combination)。

注意到取出的元素在一个集合中，即该组合实际为S的一个子集（subset)。由集合的定义可知，这些元素没有先后顺序。
两个组合相等 <==> 两个集合相等 <==> 两个集合所含元素相同
由此可知，组合与排列的不同在于组合内的元素是无序的，某种意义上，组合数<排列数。
例如{1,2,3}与{2,1,3}是相同的组合，因为它们所含元素相同。

组合数 the number of combinations

从n个元素无序选取k个元素所能取得的不同组合总数称为组合数(the number of combinations)，通常记为$C_n^k$或C(n,k)。
推导如下:
从n个元素无序选取k个元素的过程与选取排列的过程(permuting)相同，由于组合（注意到组合是一个集合）中元素顺序无关，因而选取的相同k个元素的不同排列属于同一个组合
（例如(1,2,3)、(2,1,3)、(3,2,1)…都属于同一个组合{1,2,3}），前面提到（k=n时)k个元素的不同排列有k!种，由此可得
$$C_n^k = {A_n^k} \over {k!} = {n!} \over {k!(n-k)!} = {n(n-1)•••（n-k+1)} \over {k(k-1)•••1}$$
当k>n时，$C_n^k = 0$
注意到该值也等于二项式系数(binomial coefficient)

排列组合数的应用，例如从n件物品中随机（即无序）选取k件物品，则有C(n,k)种取法，之所以不是A(n,k)是因为这里同一件物品先后被取出来的次序是无关的。
又如把n个物品分成k组，第k组别有$n_k$个物品，且n = $n_1$ + $n_2$ + ••• + $n_k$，则不同的分组方法有${n!} \over {n_1!n_2!•••n_k!}$种(n个物品有n!种分法，第k组有$n_k!$种分法)。