前言

这一期是关于csp S组必考的排列组合。讲述了排列组合的基本概念。 （这东西他们tm是真的难，老CS了）

---

---

1.排列（Permutation/Arrangement)

定义：从给定的$n$个不同元素中，去出指定个数为 $m$（ $m \le n$ ）的元素进行排序.

通俗来说就是从$n$个不同的人中，叫那$m$出来排队。

公式：

\( A_n^m = P_n^m= n*(n-1)*(n-2)*...*(n-m+1)=\frac{n!}{(n-m)!} \)

别看那么复杂说白了就是从$n$乘到$(n-m+1)$。

例子：

$$A_5^3=P_5^3=5 * 4 * 3=60$$

注：\( A_n^m \) 和 \(P_n^m\) 是一样的。只是因为排列的英文有两个(Permutation/Arrangement)

📘 例题（排列应用）

题目：

从 7 名不同学生（A、B、C、D、E、F、G）中，选出 4 人 排成一列队形（顺序不同算不同队形）。 问：共有多少种不同的排队结果？

答案：840

解析：

定义回顾：从给定的$n$个不同元素中，去出指定个数为 $m$（ $m \le n$ ）的元素进行排序.

题目中：$n$=7,$m$=4;

所以 \( A_7^4=7 * 6 * 5 * 4 =42 * 20 =840 \)

---

特殊排列类型

• 全排列 (Full Permutation)
  • 定义： 从n个不同元素中取出全部n个元素，按照一定的顺序排成一列，所得到的排列称为全排列，全排列是排列数公式中$m$=$n$的情况。
  • 公式：

$$A_n^n=P_n^n=n!$$

• 可重复排列 (Permutation with Repetition)
  • 定义： 从$n$个不同元素中，每次允许重复选取元素，取出$m$个元素进行排列。换句话说，就是$n$个元素中的每个元素都可以无限量供应。
  • 公式: 由于每次选取都有$n$种选择，且可以重复，根据乘法原理，可重复排列的公式为：

$$n^m$$

• 例子：有 3 种颜色，给 4 个不同的格子染色，每个格子都可以选 3 种颜色之一，共有 $3^4=81$ 种方案。

• 多重集排列（有重复元素的全排列）

  • 定义：给定 $n$ 个元素，其中有 $k$ 种元素，每种分别有 $n_1,n_2,\dots,n_k$ 个，且 $n_1+n_2+\cdots+n_k=n$，把这些元素全部拿来排列，去重后的排列数。
  • 公式：

$$\frac{n!}{n_1!n_2!\cdots n_k!}$$

• 例子：字符串 BANANA，其中 B 有 1 个，A 有 3 个，N 有 2 个，总长度 6：

$$\frac{6!}{1!3!2!}=60$$

• 圆排列
  • 定义：$n$ 个不同元素围成一圈，旋转后相同算同一种排列。
  • 公式：

$$(n-1)!$$

• 例子：4 个人围一张圆桌坐，排列数为 $(4-1)!=3!=6$。
• 如果规定翻转后相同也算同一种，例如项链问题，通常还要再除以 2：

$$\frac{(n-1)!}{2}$$

• 错位排列
  • 定义：$n$ 个元素排列，要求每个元素都不在自己的原位置上。
  • 递推公式：

$$D_1=0,\quad D_2=1$$ $$D_n=(n-1)(D_{n-1}+D_{n-2})$$

• 通项公式：

$$D_n=n!\sum_{i=0}^{n}\frac{(-1)^i}{i!}$$

• 例子：3 个元素错位排列 $D_3=2$，例如 $1,2,3$ 可以变成 $2,3,1$ 或 $3,1,2$。

---

2. 组合（Combination）

定义

从 $n$ 个不同元素中，取出 $m$ 个元素，不考虑顺序，叫做组合。

也就是说：

• 排列：AB 和 BA 不同；
• 组合：AB 和 BA 相同。

公式

$$C_n^m=\binom{n}{m}=\frac{A_n^m}{m!}=\frac{n!}{m!(n-m)!}$$

其中 $C_n^m$ 也常写作 $\binom{n}{m}$，读作“$n$ 选 $m$”。

例子

从 5 个人中选 3 个人组成一个队伍，不排队：

$$C_5^3=\frac{5!}{3!2!}=10$$

如果这 3 个人还要排成一列，则是：

$$A_5^3=5\times4\times3=60$$

也可以理解为：

$$A_5^3=C_5^3\times3!=10\times6=60$$

---

组合的重要性质

1. 对称性

$$C_n^m=C_n^{n-m}$$

例如：$C_5^2=C_5^3=10$。

2. 边界值

$$C_n^0=C_n^n=1$$

3. 杨辉三角递推式

$$C_n^m=C_{n-1}^{m-1}+C_{n-1}^m$$

这个在动态规划、组合数预处理中非常常用。

4. 二项式定理

$$(a+b)^n=\sum_{m=0}^{n}C_n^m a^{n-m}b^m$$

例如：

$$(a+b)^3=C_3^0a^3+C_3^1a^2b+C_3^2ab^2+C_3^3b^3$$

---

可重复组合

从 $n$ 种不同元素中，取出 $m$ 个元素，允许重复，且不考虑顺序。

公式：

$$C_{n+m-1}^{m}=C_{n+m-1}^{n-1}$$

• 例子：有苹果、香蕉、橘子 3 种水果，买 3 个，允许重复，不考虑顺序：

$$C_{3+3-1}^{3}=C_5^3=10$$

可以理解为方程：

$$x_1+x_2+\cdots+x_n=m$$

的非负整数解个数，其中 $x_i$ 表示第 $i$ 种元素取了多少个。

用隔板法：

• 非负整数解：$C_{n+m-1}^{n-1}$
• 正整数解：$C_{m-1}^{n-1}$

---

3. 排列与组合的关系

核心关系：

$$A_n^m=C_n^m\times m!$$

意思是：

1. 先从 $n$ 个里面选出 $m$ 个：$C_n^m$；
2. 再把这 $m$ 个排列：$m!$；
3. 合起来就是排列数 $A_n^m$。

所以：

• 有序：排列；
• 无序：组合；
• 先选后排：组合乘阶乘。

---

4. CSP S 常见注意点

1. 有序用排列，无序用组合。
2. 可重复排列是 $n^m$。
3. 可重复组合是 $C_{n+m-1}^m$。
4. 有重复元素全排列要除以重复元素阶乘。
5. 圆排列是 $(n-1)!$。
6. 错位排列用递推：$D_n=(n-1)(D_{n-1}+D_{n-2})$。
7. 组合数取模常用阶乘 + 逆元：

$$C_n^m\bmod p=fac[n]\times invfac[m]\times invfac[n-m]\bmod p$$

其中：

$$invfac[i]=(fac[i])^{p-2}\bmod p$$

这是 CSP / 竞赛里非常常见的组合数预处理方式。

---

综合小例题

从 5 名男生、4 名女生中选出 3 名男生和 2 名女生，并排成一排。

先选人：

$$C_5^3\times C_4^2=10\times6=60$$

再排列：

$$5!=120$$

所以总数：

$$60\times120=7200$$

答案：

$$\boxed{7200}$$

---

到这里，排列组合的基础框架就差不多完整了：排列、组合、全排列、可重复排列、多重集排列、圆排列、错位排列、可重复组合。

再往后刷题时，常见方法还有：捆绑法、插空法、隔板法、容斥原理、DP 计数等。