排列组合

引入¶

排列组合是组合数学中的基础。排列就是指从给定个数的元素中取出指定个数的元素进行排序；组合则是指从给定个数的元素中仅仅取出指定个数的元素，不考虑排序。排列组合的中心问题是研究给定要求的排列和组合可能出现的情况总数。排列组合与古典概率论关系密切。

在高中初等数学中，排列组合多是利用列表、枚举等方法解题。

加法 & 乘法原理¶

加法原理¶

完成一个工程可以有 $n$ 类办法，$a_i(1 \le i \le n)$ 代表第 $i$ 类方法的数目。那么完成这件事共有 $S=a_1+a_2+\cdots +a_n$ 种不同的方法。

乘法原理¶

完成一个工程需要分 $n$ 个步骤，$a_i(1 \le i \le n)$ 代表第 $i$ 个步骤的不同方法数目。那么完成这件事共有 $S = a_1 \times a_2 \times \cdots \times a_n$ 种不同的方法。

排列与组合基础¶

排列数¶

从 $n$ 个不同元素中，任取 $m$（$m\leq n$，$m$ 与 $n$ 均为自然数，下同）个元素按照一定的顺序排成一列，叫做从 $n$ 个不同元素中取出 $m$ 个元素的一个排列；从 $n$ 个不同元素中取出 $m$($m\leq n$) 个元素的所有排列的个数，叫做从 $n$ 个不同元素中取出 $m$ 个元素的排列数，用符号 $\mathrm A_n^m$（或者是 $\mathrm P_n^m$）表示。

排列的计算公式如下：

\[ \mathrm A_n^m = n(n-1)(n-2) \cdots (n-m+1) = \frac{n!}{(n - m)!} \]

$n!$ 代表 $n$ 的阶乘，即 $6! = 1 \times 2 \times 3 \times 4 \times 5 \times 6$。

公式可以这样理解：$n$ 个人选 $m$ 个来排队 ($m \le n$)。第一个位置可以选 $n$ 个，第二位置可以选 $n-1$ 个，以此类推，第 $m$ 个（最后一个）可以选 $n-m+1$ 个，得：

\[ \mathrm A_n^m = n(n-1)(n-2) \cdots (n-m+1) = \frac{n!}{(n - m)!} \]

全排列：$n$ 个人全部来排队，队长为 $n$。第一个位置可以选 $n$ 个，第二位置可以选 $n-1$ 个，以此类推得：

\[ \mathrm A_n^n = n(n-1)(n-2) \cdots 3 \times 2 \times 1 = n! \]

全排列是排列数的一个特殊情况。

组合数¶

从 $n$ 个不同元素中，任取 $m \leq n$ 个元素组成一个集合，叫做从 $n$ 个不同元素中取出 $m$ 个元素的一个组合；从 $n$ 个不同元素中取出 $m \leq n$ 个元素的所有组合的个数，叫做从 $n$ 个不同元素中取出 $m$ 个元素的组合数，用符号 $\dbinom{n}{m}$ 来表示，读作「$n$ 选 $m$」。

组合数计算公式

\[ \dbinom{n}{m} = \frac{\mathrm A_n^m}{m!} = \frac{n!}{m!(n - m)!} \]

如何理解上述公式？我们考虑 $n$ 个人选 $m$ 个出来（$m \le n$），不排队，不在乎顺序。如果在乎顺序那么就是 $\mathrm A_n^m$，如果不在乎那么就要除掉重复，那么重复了多少？同样选出来的 $m$ 个人，他们还要「全排」得 $m!$，所以得：

\[ \begin{aligned} \dbinom{n}{m} \times m! &= \mathrm A_n^m\\ \dbinom{n}{m} &= \frac{\mathrm A_n^m}{m!} = \frac{n!}{m!(n-m)!} \end{aligned} \]

组合数也常用 $\mathrm C_n^m$ 表示，即 $\displaystyle \mathrm C_n^m=\binom{n}{m}$。现在数学界普遍采用 $\dbinom{n}{m}$ 的记号而非 $\mathrm C_n^m$。

组合数也被称为「二项式系数」，下文二项式定理将会阐述其中的联系。

特别地，规定当 $m>n$ 时，$\mathrm A_n^m=\dbinom{n}{m}=0$。

排列组合解题八大核心模板¶

核心理念：解题前先判断 “有序还是无序”（用A还是C）、“分类还是分步”（加还是乘）。
90%的高考及模拟题均适用以下模板。

模板一：优先处理特殊元素/位置¶

适用信号：出现 “甲不站两端”、“某人不能担任某职”。
口诀：特殊元素优先排，特殊位置先安排。
策略：先排有绝对限制的人或位置，剩余随便排。

典型例题：6人站一排，甲不站排头，乙不站排尾。
解法：

情况1：甲站排尾 → 剩余5人全排：$ A_5^5 = 120 $
情况2：甲不站排尾 → 甲有中间4个位置（4种），乙不能站尾且不能占甲位（剩4个位置，4种），其余全排 $ A_4^4 $： $ 4 \times 4 \times 24 = 384 $

总数：$ 120 + 384 = 504 $

模板二：相邻问题捆绑法¶

适用信号：出现 “甲乙相邻”、“必须挨着”、“坐在一起”。
口诀：捆绑视为大元素，内部再排要乘阶。
策略：把相邻元素捆成“大胖子”，先算大胖子与其他人的排列，再乘以内部排列。

典型例题：7人站队，甲乙丙3人必须相邻。
解法：

甲乙丙绑成1个整体 → 共 $ 5 $ 个对象全排：$ A_5^5 $
甲乙丙内部互换：$ A_3^3 $

总数：$ A_5^5 \times A_3^3 = 120 \times 6 = 720 $

模板三：不相邻问题插空法¶

适用信号：出现 “甲乙不相邻”、“不能挨着”、“中间有间隔”。
口诀：先排无要求，再把不相邻插进空。
策略：先排其他元素产生空位，再把不相邻元素插入空位（注意两端是否可用）。

典型例题：7人站队，甲乙丙3人互不相邻。
解法：

先排其余4人：$ A_4^4 $，产生5个空位（含两端）
甲乙丙分别插入空位：$ A_5^3 $

总数：$ A_4^4 \times A_5^3 = 24 \times 60 = 1440 $

模板四：定序问题倍缩法¶

适用信号：出现 “甲乙丙顺序一定”（不要求相邻，只要求前后次序固定）。
口诀：先全排，再除以顺序固定的那几个人的全排列。
策略：先全排列，再除以固定顺序元素的排列数以去重。

典型例题：7人站队，甲必须在乙前，乙必须在丙前（甲乙丙顺序固定）。
解法：

7人先全排：$ A_7^7 $
甲乙丙3人顺序有 $ A_3^3 $ 种，现只取“甲>乙>丙”这一种
总数：$ \frac{A_7^7}{A_3^3} = \frac{5040}{6} = 840 $

模板五：分组与分配问题¶

适用信号：出现 “分成3组”、“分给3个人”、“部分均匀分组”。
口诀：不等分直接乘，等分堆要除阶乘；先分堆再分配。
策略：

分给不同对象：直接乘组合数。
分成无名称堆：若堆数相同，必须除以相同堆数的阶乘去重。

典型例题：

不等分：6本书分成1本、2本、3本三堆 → $ C_6^1 \times C_5^2 \times C_3^3 = 60 $（无需除）
均匀分：6本书分成3堆，每堆2本 → $ \frac{C_6^2 \times C_4^2 \times C_2^2}{A_3^3} = \frac{15 \times 6 \times 1}{6} = 15 $
分配：6本书分给甲乙丙，每人2本 → 先均匀分堆（15种），再分给3人（$ A_3^3 $ 种）：$ 15 \times 6 = 90 $

模板六：隔板法（名额分配）¶

适用信号：出现 “相同元素”（如名额、小球）分成若干份，且至少为1。
口诀：n个相同元素分给m个人，每人至少1个，插 $ m-1 $ 块板。
策略：在 $ n-1 $ 个空隙中插入 $ m-1 $ 块板子，分成 $ m $ 份。

基本公式：$ C_{n-1}^{m-1} $
允许有人为0：先借 $ m $ 个元素使每人至少1个 → $ C_{n+m-1}^{m-1} $

典型例题：10个相同篮球分给3个班，每班至少1个。
解法：$ C_{9}^{2} = 36 $ 种

模板七：错位排列（装错信封）¶

适用信号：出现 “全都不对应”、“不在自己原来位置”、“互不归还”。
口诀：记住前4个数字：0, 1, 2, 9。
策略：直接套用固定公式。

$ D_1 = 0 $，$ D_2 = 1 $，$ D_3 = 2 $，$ D_4 = 9 $
递推公式：$ D_n = (n-1)(D_{n-1} + D_{n-2}) $

典型例题：4个人各写一张贺卡，互相赠送，每个人都不能拿自己的。
解法：直接套 $ D_4 = 9 $ 种

模板八：涂色问题¶

适用信号：地图涂色、区域染色。
口诀：先选颜色最多（或相邻最多）的区域，按“用了多少种颜色”分类讨论。
策略：按颜色使用数量分类，利用乘法原理计算。

典型例题：四棱锥（底面四边形+4个侧面），共5个区域用3种颜色涂，相邻不同色。
解法：

先涂底面：3种颜色选1种
再涂侧面：剩下2种颜色围成一圈，环形排列公式 $ (2-1)! \times 2 = 2 $ 种

总数：$ 3 \times 2 = 6 $

💡 三大保命锦囊¶

除法去重：只要是“分成组”且组没有名字，出现个数相同的一定要除以 $ A_{\text{相同组数}}^{\text{相同组数}} $。
正难则反：遇到“至少有一个”或条件苛刻时，用总情况数减去反面情况（补集思想），大幅减少计算量。
结果检验：高考小题中答案若为几万或几十万，通常不正常，检查是否误乘了 $ A $ 或漏除了 $ A $。

正整数和的数目¶

问题一：现有 $n$ 个 完全相同 的元素，要求将其分为 $k$ 组，保证每组至少有一个元素，一共有多少种分法？

考虑拿 $k - 1$ 块板子插入到 $n$ 个元素两两形成的 $n - 1$ 个空里面。

因为元素是完全相同的，所以答案就是 $\dbinom{n - 1}{k - 1}$。

本质是求 $x_1+x_2+\cdots+x_k=n$ 的正整数解的组数。

非负整数和的数目¶

问题二：如果问题变化一下，每组允许为空呢？

显然此时没法直接插板了，因为有可能出现很多块板子插到一个空里面的情况，非常不好计算。

我们考虑创造条件转化成有限制的问题一，先借 $k$ 个元素过来，在这 $n + k$ 个元素形成的 $n + k - 1$ 个空里面插板，答案为

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

虽然不是直接求的原问题，但这个式子就是原问题的答案，可以这么理解：

开头我们借来了 $k$ 个元素，用于保证每组至少有一个元素，插完板之后再把这 $k$ 个借来的元素从 $k$ 组里面拿走。因为元素是相同的，所以转化过的情况和转化前的情况可以一一对应，答案也就是相等的。

由此可以推导出插板法的公式：$\dbinom{n + k - 1}{n}$。

本质是求 $x_1+x_2+\cdots+x_k=n$ 的非负整数解的组数（即要求 $x_i \ge 0$）。

不同下界整数和的数目¶

问题三：如果再扩展一步，要求对于第 $i$ 组，至少要分到 $a_i,\sum a_i \le n$ 个元素呢？

本质是求 $x_1+x_2+\cdots+x_k=n$ 的解的数目，其中 $x_i \ge a_i$。

类比无限制的情况，我们借 $\sum a_i$ 个元素过来，保证第 $i$ 组至少能分到 $a_i$ 个。也就是令

\[ x_i^{\prime}=x_i-a_i \]

得到新方程：

\[ \begin{aligned} (x_1^{\prime}+a_1)+(x_2^{\prime}+a_2)+\cdots+(x_k^{\prime}+a_k)&=n\\ x_1^{\prime}+x_2^{\prime}+\cdots+x_k^{\prime}&=n-a_1-a_2-\cdots-a_k\\ x_1^{\prime}+x_2^{\prime}+\cdots+x_k^{\prime}&=n-\sum a_i \end{aligned} \]

其中

\[ x_i^{\prime}\ge 0 \]

然后问题三就转化成了问题二，直接用插板法公式得到答案为

\[ \binom{n - \sum a_i + k - 1}{n - \sum a_i} \]

不相邻的排列¶

$1 \sim n$ 这 $n$ 个自然数中选 $k$ 个，这 $k$ 个数中任何两个数都不相邻的组合有 $\dbinom {n-k+1}{k}$ 种。

二项式定理¶

在进入排列组合进阶篇之前，我们先介绍一个与组合数密切相关的定理——二项式定理。

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

\[ (a+b)^n=\sum_{i=0}^n\binom{n}{i}a^{n-i}b^i \]

证明可以采用数学归纳法，利用 $\dbinom{n}{k}+\dbinom{n}{k-1}=\dbinom{n+1}{k}$ 做归纳。

二项式定理也可以很容易扩展为多项式的形式：

设 $n$ 为正整数，$x_i$ 为实数，

\[ (x_1 + x_2 + \cdots + x_t)^n = \sum_{满足 n_1 + \cdots + n_t=n 的非负整数解} \binom{n}{n_1,n_2,\cdots,n_t} x_1^{n_1}x_2^{n_2}\cdots x_t^{n_t} \]

其中的 $\dbinom{n}{n_1,n_2,\cdots,n_t}$ 是多项式系数，它的性质也很相似：

\[ \sum{\binom{n}{n_1,n_2,\cdots,n_t}} = t^n \]

排列与组合进阶篇¶

接下来我们介绍一些排列组合的变种。

多重集的排列数 | 多重组合数¶

请大家一定要区分 多重组合数 与 多重集的组合数！两者是完全不同的概念！

多重集是指包含重复元素的广义集合。设 $S=\{n_1\cdot a_1,n_2\cdot a_2,\cdots,n_k\cdot a_k\}$ 表示由 $n_1$ 个 $a_1$，$n_2$ 个 $a_2$，…，$n_k$ 个 $a_k$ 组成的多重集，$S$ 的全排列个数为

\[ \frac{n!}{\prod_{i=1}^kn_i!}=\frac{n!}{n_1!n_2!\cdots n_k!} \]

相当于把相同元素的排列数除掉了。具体地，你可以认为你有 $k$ 种不一样的球，每种球的个数分别是 $n_1,n_2,\cdots,n_k$，且 $n=n_1+n_2+\ldots+n_k$。这 $n$ 个球的全排列数就是 多重集的排列数。多重集的排列数常被称作 多重组合数。我们可以用多重组合数的符号表示上式：

\[ \binom{n}{n_1,n_2,\cdots,n_k}=\frac{n!}{\prod_{i=1}^kn_i!} \]

可以看出，$\dbinom{n}{m}$ 等价于 $\dbinom{n}{m,n-m}$，只不过后者较为繁琐，因而不采用。

多重集的组合数 1¶

设 $S=\{n_1\cdot a_1,n_2\cdot a_2,\cdots,n_k\cdot a_k\}$ 表示由 $n_1$ 个 $a_1$，$n_2$ 个 $a_2$，…，$n_k$ 个 $a_k$ 组成的多重集。那么对于整数 $r(r