有 序 排列组合

排列是一组不重复对象的有序排列。例如，在不重复字母的情况下，对字母 abc 进行排序的方法有六种。这六种排列是 abc、acb、bac、bca、cab、cba。

使用排列函数可以确定从 n 项中一次选择 k 项的排列数。排列用来在只有两种可能结果的试验（二项试验）中计算事件的概率。

语法

PERMUTATIONS (项数, 要选择的数)

为项数和要选择的数字指定一个数字或一列数字。项数必须大于或等于 1，要选择的数字必须大于或等于 0。

示例

假设有 10 个人参加比赛。当顺序至关重要时，可通过多少种不同的方式获得第一、第二和第三名？

公式

通常，从 n 项中一次选择 k 项的排列数为：

其他用途

排列也可用来确定对一组字母或数字进行排序的可能方法数，这已应用于编码中。排列组合（称为组合数学）在网络工程、计算机科学（密码术）、分子生物学（模式分析）和其他领域具有重要作用。

\[\begin{equation} \begin{split} P(n, r) &= n \cdot (n-1) \cdot (n-2)......(n-r+2)(n-r+1)\\ &= n! \verb|/| (n-r)! \end{split} \end{equation} \]

特别地，当\(r=n\)时，称为全排列，\(p(n, n)=n!\)

3.2 组合

• 定义：从\(n\)个不同元素中取\(r\)个元素，且不考虑顺序，称为从\(n\)个中取\(r\)个的组合。
• 组合数用\(c(n,r)\)或者\(\tbinom{n}{r}\)来表示
• 与排列不同的是，组合只是相当于从\(n\)个球中选择\(r\)个组合在一起即可，与排列相比，无需\(r\)个球构成一个全排列这么一个操作。因此，组合数的计算相当于是在排列数的基础上除去一个\(r\)的全排列\(r!\)即可。所以

\[\begin{equation} \begin{split} C(n,r) &= P(n, r) \verb|/| r!\\ &= n! \verb|/| \left[ (n-r)! \cdot r! \right] \end{split} \end{equation} \]

四 圆排列与项链排列

4.1 圆排列

• 定义：从\(n\)个不同的元素中取\(r\)个元素排列在一个圆环上的排列
• 圆排列数用\(Q(n,r)\)来表示。因为圆排列的缘故，每\(r\)个首尾相连顺序一样的排列都只能算一种，如下图所示，所以，圆排列数相当于是在排列数的基础上除去\(r\)。所以

\[Q(n, r) = P(n, r) \verb|/| r \]

\[Q(n, n) = P(n, n) \verb|/| n = (n-1)! \]

4.2 项链排列

• 定义：项链排列如同项链一般，在圆排列的基础上，逆时针方向和顺时针方向的放置各个数是同一个排列。
• 因此项链排列的排列数为\(Q(n, r) \verb|/| 2 = P(n, r) \verb|/| 2r\)

五 可重排列与可重组合

5.1 可重排列

可重排列的定义：
设有\(n\)种不同的物体\(a_1,a_2,...,a_n\)，
第一种物体\(a_1\)有相同的\(k_1\)个，
第二种物体\(a_2\)有相同的\(k_2\)个，
......
第n中物体\(a_n\)有相同的\(k_n\)个，
从这\(n\)中物品里取\(r\)个物品进行排列，称为\(r\)可重排列。

依据\(r\)和\(k_i\)的数量情况可以分为以下三种情况：

• \(r = k_1 + k_2 + ... + k_n\)

• \(k_1 \ge r, k_2 \ge r, ... , k_n \ge r\)或者\(k_1 = \infty, k_2 = \infty, ..., k_n = \infty\)

• 存在\(k_i < r\)

那么对于上述三种情况，如何计算它们的排列数呢？

对于情况1，设\(S =\left \{ k_1 \cdot a_1, k_2 \cdot a_2, ..., k_n \cdot a_n\right \}\)，当\(k_1 + k_2 + ... + k_n = r\)时，从\(n\)种物品中取\(r\)个物品的全体排列数用\(P(r;k_1, k_2,...,k_n)\)或\(\tbinom{r}{k_1 k_2 ... k_n}\)表示。则

\[P(r;k_1, k_2, ..., k_n) = r! \verb|/| (k_1 ! \cdot k_2 ! \cdot ... \cdot k_n !) \]

证明过程略

对于情况2，有

\[P(r; a_1 \cdot \infty, a_2 \cdot \infty, ..., a_n \cdot \infty) = n^r \]

证明过程略。

对于情况3，没有一个现成的公式可以计算其排列数。

5.2 可重组合

可重组合的定义：
有\(n\)种不同的物品，构成集合\(S =\left \{ k_1 \cdot a_1, k_2 \cdot a_2, ..., k_n \cdot a_n\right \}\)，从这\(n\)种物品中取出\(r\)个物品的组合，称为\(r\)可重组合。对于可重组合可以分成以下两种特殊情况：

• \(k_i > r~(i = 1, 2, ..., n)\)
• \(a_1 ,a_2, ..., a_n\)至少出现一次的组合

对于情况1，有

\[C(r; a_1 \cdot \infty, a_2 \cdot \infty, ..., a_n \cdot \infty) = \tbinom{r + n - 1}{r} \]

简要证明：
第1步：问题相当于\(r\)个相同的球放入\(n\)个互异的盒子，每个盒子的数目可以不同，求总的方案数

第2步：上述问题又可以转换为\(r\)个相同的球与\(n-1\)个相同的盒壁的排列问题

因此，排列数为：

\[(r+n-1)! \verb|/| (r! \cdot (n - 1)!) = \tbinom{n+r-1}{r} \]

对于情况2，\(a_1 ,a_2, ..., a_n\)至少出现一次的组合数为\(\tbinom{r-1}{r-n}\)

简要证明：
因为\(a_1 ,a_2, ..., a_n\)至少出现一次，所以，先取出\(a_1 ,a_2, ..., a_n\)各一个，剩下的问题就转化为从\(n\)中取\(r-n\)个的可放回组合问题。因此，组合数为：

\[\tbinom{r-n+n-1}{r-n} = \tbinom{r-1}{r-n} \]

六 若干组合等式

6.1 Stirling近似公式

Stirling公式给出了一个求\(n!\)的近似公式。

\[n! \approx \sqrt{2n\pi} (\frac{n}{e})^n \]

6.2 Pascal公式

\[\tbinom{n}{k} = \tbinom{n-1}{k} + \tbinom{n-1}{k-1} \]

该公式相当直观，证明也相当简单：
令\(S\)是\(n\)个元素的集合，任取一个元素用\(x\)表示，则\(S\)的\(k-\)组合的集合可以划分为不包含\(x\)的\(k-\)组合和包含\(x\)的\(k-\)组合，于是

\[\tbinom{n}{k} = \tbinom{n-1}{k} + \tbinom{n-1}{k-1} \]

6.3 二项式定理及二项式系数

设\(n\)是正整数，对任意的\(x\)和\(y\)有：

\[(x+y)^n = \sum_{k=0}^n \tbinom{n}{k} x^k y^{n-k} \]

其中\(\tbinom{n}{k}\)为二项式系数。

根据上述二项式定理，有以下推论：

令\(y=1\)有：

\[(1+x)^n = \sum_{k=0}^n \tbinom{n}{k} x^k = \tbinom{n}{0} + \tbinom{n}{1}x + ... + \tbinom{n}{n}x^n \]

令\(y = 1, x = -x\)有：

\[(1-x)^n = \sum_{k=0}^n (-1)^k \tbinom{n}{k}x^k = \tbinom{n}{0} - \tbinom{n}{1}x + ... + \tbinom{n}{n}(-1)^k x^n \]

令\(x = 1, y = 1\)有：

\[\tbinom{n}{0} + \tbinom{n}{1} + ... + \tbinom{n}{n} = 2^n \]

令\(x = -1, y = 1\)有：

\[\tbinom{n}{0} - \tbinom{n}{1} + \tbinom{n}{2} ... + (-1)^n \tbinom{n}{n} = 0 \]

6.4 多项式定理

设\(n\)是正整数，则对一切实数\(x_1, x_2, ..., x_m\)有：

\[\begin{equation} \begin{split} (x_1 + x_2 + ... + x_m)^n &= \sum_{n_1 + n_2 + ... + n_m = n} \frac{n!}{n_1 ! \cdot n_2 ! ... n_m !}x_1^{n_1}x_2^{n_2}...x_m^{n_m}\\ &= \sum_{n_1 + n_2 + ... + n_m = n}\tbinom{n}{n_1 n_2 ... n_m}x_1^{n_1}x_2^{n_2}...x_m^{n_m} \end{split} \end{equation} \]

其中\(\tbinom{n}{n_1 n_2 ... n_m}\)为多项式系数。

6.5 牛顿二项式定理

设\(\alpha\)是一个实数。则对于所有满足$0 \leq \vert x \vert < \vert y \vert \(的\)x\(和\)y$有：

\[(x+y)^{\alpha} = \sum_{k=0}^{\infty} \tbinom{\alpha}{k} x^k y^{\alpha - k} \]

其中

\[\tbinom{\alpha}{k} = \begin{cases} 0 & k < 0\\ 1 & k = 0\\ \frac{\alpha (\alpha - 1) ... (\alpha - k + 1)}{k!} & k > 0 \end{cases} \]

6.6 组合恒等式

下面是一些组合恒等式，证明过程略。

\[\tbinom{n}{r} = \tbinom{n}{n-r} \]

\[\tbinom{n}{1}^2 + 2\tbinom{n}{2}^2 + ... + n\tbinom{n}{n}^2 = n \cdot \tbinom{2n-1}{n-1} \]

\[\tbinom{n}{r} = \tbinom{n-1}{r-1} + \tbinom{n-2}{r-1} + \tbinom{n-3}{r-1} + ... + \tbinom{r-1}{r-1} \]

\[\tbinom{n}{l}\tbinom{l}{r} = \tbinom{n}{r}\tbinom{n-r}{l-r} \neq \tbinom{n}{r} \]

\[\tbinom{n}{0} + \tbinom{n}{1} + \tbinom{n}{2} + ... + \tbinom{n}{n} = 2^n \]

\[\tbinom{m+n}{r} = \tbinom{m}{0}\tbinom{n}{r} + \tbinom{m}{1}\tbinom{n}{r-1} + ... + \tbinom{m}{r}\tbinom{n}{0} \]