排列组合

加法 & 乘法原理

加法原理

一个人有 n 种上衣，第 i 种上衣有 a_i 件，则他有 S=a_1+a_2+ \cdots +a_n 种选择。

乘法原理

一个人有很多件衣服，比如衣服、鞋子、帽子等，第 i 种衣服有 a_i 件，则他有 S=a_1 \times a_2 \cdots \times a_n 种搭配方式。

总而言之，一个步骤内部使用加法原理，多个步骤之间使用乘法原理。

排列数和组合数

排列数

从 n 个不同元素中取出 m 个数（m \leq n）有顺序地排成一列，叫做从 n 个不同元素中取出 m 个元素的一个排列。

从 n 个不同元素中取出 m 个元素的所有排列的个数，叫做从 n 个不同元素中取出 m 个元素的排列数，用符号 A_n^m 表示。

我们考虑，选取第一个元素时有 n 个元素可以选择，第二个时有 n-1 个可以选择……直到第 m 个时，有 n-m+1 个可以选择，所以可以得到排列的计算公式：

当 m=n 时，称这种情况为全排列，选取第一个元素时有 n 个元素可以选择，第二个时有 n-1 个可以选择……直到第 n 个时，有 1 个可以选择，所以可以得到全排列的计算公式：

组合数

从 n 个不同元素中取出 m 个数（m \leq n）无顺序地排成一列，叫做从 n 个不同元素中取出 m 个元素的一个组合。

从 n 个不同元素中取出 m 个元素的所有组合的个数，叫做从 n 个不同元素中取出 m 个元素的组合数，用符号 C_n^m 表示。

组合数是无序的，所以如果能够删去 A_n^m 中重复的组合，就可以得到 C_n^m。

考虑对于 m 个元素，其一共有 A_m^m 即 m! 种排列方式，也就是对于 m 个元素，其有 m! 种重复组合，所以可以得到：

插板法

不存在 0 的分组

现在有 n 个相同的鸡蛋，要求将其放到 k 个篮子中，且篮子不能为空，一共有多少种分法？

我们可以将问题抽象化，将鸡蛋排成一条线，篮子变成长板，则问题可以转化为将板子插到鸡蛋的间隔之间，有多少种插法。

重新考虑原始问题，发现如果把每个板子左边部分的鸡蛋放到篮子里，那么最右边会有几个鸡蛋没有被放进篮子，所以我们先拿出一个板子放在最右边，用来承接这部分鸡蛋。

那么问题就可以转化为将 k-1 个板子插到 n 个鸡蛋形成的 n-1 个间隔中，故答案为：

可以感性理解到其本质是求 x_1+x_2+ \cdots +x_k=n 的解的个数（x > 0）。

存在 0 的分组

在上一种情况的基础上，让篮子可以为空，一共有多少种分法？

发现没有办法直接插板。

我们考虑额外拿出 k 个虚拟的鸡蛋，此时有 n+k 个鸡蛋和 k 个篮子，鸡蛋间有 n+k-1 个间隔，我们对其进行插板法，插板结束后将那 k 个虚拟的鸡蛋拿出来，此时之前只被分到一个虚拟鸡蛋的篮子就变成了空的，答案为：

因为组合数学的神秘性质，我们可以知道，在 n 个数中选 m 个数，等价于在 n 个数中不选 n-m 个数，即 C_n^m=C_n^{n-m}。

所以答案也可以化为：

可以感性理解到其本质是求 x_1+x_2+ \cdots +x_k=n 的解的个数（x \geq 0）。

每组有最小限制的分组

如果，对于第 i 个篮子，至少要分到 a_i 个鸡蛋呢？

可以感性理解到其本质是求 x_1+x_2+ \cdots +x_k=n 的解的个数（x_i \geq a_i）。

类比上面的情况，我们可以借 \sum{a_i} 个虚拟的鸡蛋，设 x_i' = x_i - a_i，因为 x_i \geq a_i，易得 x_i' >= 0。

那么方程就可以进行转化：

因为 x_i' >= 0，所以这个问题就就转化为了上文篮子可以为空的问题，带入上文求出的公式（将 n 替换为 n-\sum{a_i}），得到：

不相邻的排列

在 1 \sim n 这 n 个数中，选 k 个，其中两两不相邻的组合有多少种？

能够选择 k 个，说明其中分开了 k-1 个间隔，不同的是，为了两两不相邻，这次的“间隔”是具体的数。

所以问题转化为有 n-k+1 个数，选择其中 k 个数，求有多少种组合。答案为：

二项式定理

二项式定理阐明了一个展开式的系数：

其意义是 (a+b)^n 展开后，等于 n+1 个单项式的和，其中在第 i 个单项式中，单项式的系数为 C_n^i，a 的幂数为 n-i，b 的幂数为 i。

二项式定理也可以推广到多项式：

• 其中 C_{n}^{n_1,n_2,\cdots,n_k} 是组合数的扩展形式，其等价于 \dfrac{n!}{n_1!n_2! \cdots n_k!}。
• 其中 n_1,n_2 \cdots n_k > 0。