排列组合详解

· · 个人记录

一、引入

排列组合是组合数学的基础，主要是研究各种排列和组合的情况数。

1. 加法原理

在同一步中，有不同类别的选择，可以将各类选择方案数累加获得总方案数。

举例说明，比如从 A 城到达 B 城，坐火车有 3 种方案，坐飞机有 2 种方案。则总共有 2 + 3 = 5 种方案。

2. 乘法原理

在不同步骤中，有不同种方案，可以将各步方案数累乘获得总方案数。

举例说明，比如从 A 城到达 B 城，中间需要从 C 城转乘。到达 C 城有 3 种方案，到达 B 城有 2 种方案。则总共有 2 \times 3 = 6 种方案。

二、公式

排列数：从 n 个不同元素中任意选出 m(m \leq n) 个，按照一定顺序排成一列，叫做从 n 个不同元素中取出 m 个元素的排列数。

A^m_n = n(n-1)(n-2) \cdots (n-m+1)=\frac{n!}{(n-m)!}

组合数：从 n 个不同元素中任意选出 m(m \leq n) 个的所有组合的个数，叫做从 n 个不同元素中取出 m 个元素的组合数。

C^m_n = \frac{A^n_m}{A^m_m} = \frac{n!}{m!(n-m)!}

组合数的性质

  1. 规定：C_n^0 = 1

  2. C^m_n = C^{n - m}_n
  4. rC^r_n = nC^{r-1}_{n-1}
r C_{n}^{r}=r \cdot \dfrac{n !}{r !(n-r) !}=\dfrac{n !}{(r-1) !(n-r) !}
  1. \Sigma^n_{k = 0}{C^k_n} = 2^n
  2. C^m_n = \frac{n}{m}C^{m-1}_{n-1}
  3. \sum^n_{i = 0}\dbinom{n - i}{i} = F_{n + 1}

    三、经典题型

1. 特殊元素和位置优先

某些问题中对于特殊的位置有要求，要提前考虑特殊的，再去正常排列或组合其他元素。

例 1： 由 0,1,2,3,4,5 可以组成多少个没有重复数字的五位奇数？

解答 由题已知，这是一个五位奇数，因此首位不能是 0，末位不能是偶数。

对于首位和末位有特殊要求，应该优先安排，以免不合要求的元素把这两个位置占掉。

先排末位共有 C^1_3，然后排首位共有 C_4^1，最后排其它位置共有 A_4^3

由乘法原理可以算出 ans=C^1_3 C_4^1 A_4^3

变式训练 1： 用 0 到 9 这 10 个数字，可以组成多少个没有重复数字的三位偶数？

解析

2. 相邻元素捆绑

有些元素不能分开，于是可以将这几个元素看作一个整体元素来进行排列组合。

例 2：

**解答：** 甲乙相邻，丙丁相邻，看作两个整体元素。 甲乙内部 $A^2_2$ 种方案，丙丁内部 $A^2_2$ 种方案，这两个整体元素和其他剩余 $5$ 个元素进行排列，有 $A^5_5$ 种方案。 则答案为 $ans = A^2_2A^2_2A^5_5

变式训练 2： 记者要为 5 名志愿者和他们帮助的 2 位老人拍照，要求排成一排，2 位老人相邻但不排在两端，求不同排法的数量？

解析

3. 不相邻元素插空

有些元素要求不能放在一起，我们可以将其他元素先排列好，再将这些不能放在一起的元素插在已经排好元素的空位中。

例 3： 一个晚会的节目有 4 个舞蹈，2 个相声，3 个独唱，舞蹈节目不能连续出场，则节目的出场顺序有多少种？

解答： 第一步，先把 2 个相声和 3 个独唱排列好，共 A^5_5 种方案；

第二步，将这四个舞蹈插入 6 个空之中，共 A^4_6 种方案。

则答案为 ans = A^5_5A^4_6

变式训练 3： 道路边上有编号 1 到 10 的 10 盏路灯，现要关掉其中的 3 盏，但不能关掉相邻的 2 盏或 3 盏，也不能关掉两端的路灯，则满足要求的关灯方法有几种？

解析

4. 定序问题倍缩和空位插入

倍缩法：对于某几个元素顺序一定的排列问题，可先把这几个元素与其他元素一起进行排列，然后用总排列数除以这几个元素之间的全排列数。

例 4：

**解答：** **法一：** 先把这几个需要固定顺序的元素和其他元素一同进行排列，即 $A^7_7$ 种； 然后再除以这几个元素的全排列数，即 $A^3_3$ 种； 答案即为 $$ans = \frac{A^7_7}{A^3_3} = A^4_7 $$ **法二：** 设总共有 $7$ 个位置，先让除了甲乙丙之外的 $4$ 人选择位置，一共有 $A^4_7$ 种方法，剩下三个位置由于甲乙丙顺序一定，只有一种排法。 $$ans = A^4_7 \times 1 = A^4_7$$ **变式训练 $4$：** 停车场划出一排 $12$ 个停车位置，今有 $8$ 辆车需要停放。要求空车位置连在一起，不同的停车方法有多少种？ [解析](https://www.luogu.com.cn/paste/b7qda6gc) --- ### 5. 排列问题求幂 **例 $5$：** 把 $6$ 名学生分配到 $7$ 个班级，共有多少种分法？ **解答：** 完成这件事需要分 $6$ 步，每一步都是把一名学生分班。 对于第一个学生，把他分班有 $7$ 种分法，第二个学生也是如此，以此类推。 共有 $7^6$ 种分法。 **变式训练 $5$：** ## 随堂练习 **1. [P3223 [HNOI2012]排队](https://www.luogu.com.cn/problem/P3223)** 主要是插空法 + 高精度