📚 排列与组合

1️ 排列（Permutation）—— 在乎顺序

✅ 全排列

$n$ 个不同元素全部排队：

$P_n^n = n × (n-1) × ... × 2 × 1 = n!$

规定：0! = 1

📌 示例：5 个人排队 → 5! = 120 种

---

✅ 部分排列（选 m 个排队）

从 $n$ 个中选 $m$ 个进行排列 $(0 \le m \le n）$ ：

$P_n^m = n × (n-1) × ... × (n - m + 1) = \frac{n!}{(n - m)!}$

📌 示例：从 6 人中选 3 人站成一排 → $P_6^3 = 6×5×4 = 120$

---

2️⃣ 组合（Combination）—— 不在乎顺序

从 $n$ 个中选 $m$ 个组成一组（不排序）：

$C_n^m = \frac{P_n^m}{m!} = \frac{n!}{m! × (n - m)!}$

📌 示例：从 6 人中选 3 人组成小组 → $C_6^3 = 20$

---

🔁 组合数重要性质（需记忆）

性质	公式	说明
对称性	$C_n^m = C_n^{n-m}$	选 $m$ 个等价于留下 $n-m$ 个
帕斯卡恒等式	$C_n^m = C_{n-1}^m + C_{n-1}^{m-1}$	杨辉三角基础
边界值	$C_n^0 = C_n^n = 1$	空集或全集只有一种选法

---

3️⃣ 特殊排列与组合模型（重点扩展）

---

（1）圆排列（Circular Permutation）

$n$ 个人围成一圈，旋转后相同视为同一种排列：

$Q_n^n = (n - 1)!$

✅ 推导：固定一人位置，其余 $n-1$ 人全排列 → $(n-1)!$

➤ 部分圆排列 $Q_n^r$

从 $n$ 人中选 $r$ 人围成圆圈：

$Q_n^r = \frac{P_n^r}r = \frac{n!}{r × (n - r)!}$

📌 示例：从 8 人中选 4 人围坐圆桌 → $Q_8^4 = \frac{P_8^4}4 = \frac{1680}4 = 420$

---

（2）重复排列（有限多重集排列）

有 $k$ 类元素，每类数量分别为 $a_1, a_2, \dots, a_k$，总个数 $n = \sum a_i$

则这 $n$ 个元素的不同排列数为：

$\frac{n!}{ {a_1}! * {a_2}! * \dots * {a_k}! }$

示例：单词 MISSISSIPPI 中字母排列数：

• M:1个, I:4个, S:4个, P:2个 → 总长 11个字母
• 排列数 = $\frac{11!}{1! × 4! × 4! × 2!} = 34650$

---

（3）重复组合（无限供应下的组合）

从 $n$ 种物品中任选 $k$ 个（可重复），不考虑顺序: $C_{n + k - 1}^k$

✅ 证明思路（变量替换法）：

设选出的数为 $b_1 \le b_2 \le \dots \le b_k ∈ [1, n]$

令 $c_i = b_i + i - 1 ⇒ c_1 < c_2 < \dots < c_k ∈ [1, n+k−1]$

→ 转化为无重复组合 → $C_{n+k−1}^k$

📌 示例：买 3 杯奶茶，店里有 5 种口味（可重复），有多少种买法？

→ $C_{5+3−1}^3 = C_7^3 = 35$

---

（4）不相邻组合（间隔选取）

从 $1 \sim n$ 中选 $k$ 个数，要求任意两个数不相邻：

$C_{n - k + 1}^ k$

✅ 证明：构造新序列消除“相邻”限制

原序列：$b_1 < b_2 < \dots < b_k$，满足 $b_i + 2 \le b_{i+1}$

令 $c_i = b_i - (i - 1)$，则 $c_1 < c_2 < \dots < c_k ∈ [1, n - k + 1]$

→ 转化为标准组合 → $C_{n - k + 1}^k$

📌 示例：从 1~10 中选 3 个互不相邻的数 → $C_{10-3+1}^3 = C_8^3 = 56$

---

（5）第二类 Stirling 数 $S_n^r$ —— 子集划分【必背】

定义：将 $n$ 个不同元素划分为 $r$ 个非空无序子集的方法总数。

记作 $S(n, r)$。

📌 示例：$S(4,2)=7$（如 $\{1\},\{2,3,4\}$、$\{1,2\},\{3,4\}$ 等 7 种划分方式）。

🔄 递推公式（高频考点）：

$$S(n, r) = r \cdot S(n-1, r) + S(n-1, r-1)$$

边界条件：$S(n,1)=1,\ S(n,n)=1,\ S(n,0)=0\ (n\ge 1)$ ✅ 推导思路：考虑第 $n$ 个元素的去向：

• 单独成一组：其余 $n-1$ 个元素需分成 $r-1$ 组 → $S(n-1, r-1)$
• 加入已有的某一组：其余 $n-1$ 个元素已分成 $r$ 组，第 $n$ 个元素可放入任意一组 → $r \cdot S(n-1, r)$

🧮 计算示例：求 $S(6,3)$

$$S(6,3) = 3 \cdot S(5,3) + S(5,2) = 90$$

常用通项：$S(n,3) = \frac{1}{2}(3^{n-1} + 1) - 2^{n-1}$

（6）错位排列（Derangements）$D_n$

定义：$n$ 个不同元素重新排列，使得没有任何一个元素出现在其原始位置上。记为 $D_n$ 或 $!n$。 📌 经典模型：信封装错、球员不住同号房间、密码锁每位都不在原位。

📊 数列前几项：

$n$	1	2	3	4	5	6
$D_n$	0	1	2	9	44	265

🔄 递推公式：

$$D_n = (n-1)(D_{n-1} + D_{n-2})$$

或等价形式：

$$D_n = n \cdot D_{n-1} + (-1)^n$$

✅ 边界条件：$D_1=0,\ D_2=1$

✅ 推导思路（分类讨论第 n 个元素的位置）：

• 情况1：第 n 个元素与某个前 n−1 个元素互换 → 剩余 n−2 个错排 → (n−1) × Dₙ₋₂
• 情况2：第 n 个元素占据某位置 j，但 j 不占 n 的位置 → 相当于对 n−1 个元素做错排 → (n−1) × Dₙ₋₁

合并得：Dₙ = (n−1)(Dₙ₋₁ + Dₙ₋₂)

（7）Catalan 数列（卡特兰数）$H_n$ 【重中之重】

以下 8 类经典问题 均对应同一数列：

1. 合法括号序列：$n$ 对括号的正确匹配数。
2. 栈的出栈序列：进栈序列为 $1,2,\dots,n$，合法出栈序列数。
3. 二叉树计数：$n$ 个节点能构成的不同二叉搜索树数量。
4. 找零问题：$2n$ 人排队，$n$ 人持 5 元，$n$ 人持 10 元，剧院无零钱，求始终能找零的排队方式。
5. 格路问题：从 $(0,0)$ 到 $(n,n)$ 不穿越对角线 $y=x$ 的路径数。
6. 圆上连弦：$2n$ 个点两两连线且线段互不相交的方法数。
7. 凸多边形三角剖分：$n+2$ 边形用不相交对角线划分为三角形的方法数。
8. Dyck 路径：$n$ 个 $+1$ 和 $n$ 个 $-1$ 构成序列，任意前缀和 $\ge 0$ 的方案数。

数列前几项：

$H_0=1,\ H_1=1,\ H_2=2,\ H_3=5,\ H_4=14,\ H_5=42,\ H_6=132,\ \dots$

🧮 通项公式：

$$H_n = \frac{1}{n+1} C_{2n}^n = \frac{(2n)!}{(n+1)!\,n!}$$

🔄 递推关系：

$$H_n = \sum_{i=0}^{n-1} H_i H_{n-1-i} \quad \text{或} \quad H_n = \frac{4n-2}{n+1} H_{n-1}$$

📌 示例：H₄ = ?

H₄ = C(8,4)/5 = 70/5 = 14 ✔️ 或用递推： H₄ = H₀H₃ + H₁H₂ + H₂H₁ + H₃H₀ = 1×5 + 1×2 + 2×1 + 5×1 = 14 ✔️

附录：核心公式速查表

模型	符号	公式	关键特征
全排列	$P_n^n$	$n!$	顺序重要，元素不重复
部分排列	$P_n^m$	$\frac{n!}{(n-m)!}$	选 $m$ 个排队
组合	$C_n^m$	$\frac{n!}{m!(n-m)!}$	顺序无关
圆排列	$Q_n^n$	$(n-1)!$	旋转等价
重复排列	-	$\frac{n!}{a_1!a_2!\cdots a_k!}$	多重集全排
重复组合		$C_{n+k-1}^k$	可重复选取
不相邻组合		$C_{n-k+1}^k$	任意两数不相邻
第二类 Stirling	$S(n,r)$	$rS(n-1,r)+S(n-1,r-1)$	集合划分
错位排列	$D_n$	$(n-1)(D_{n-1}+D_{n-2})$	全错开
Catalan 数	$H_n$	$\frac{1}{n+1}C_{2n}^n$	栈/树/路径/括号

---

💡 学习建议

1. 先掌握基础：熟练运用 $P_n^m$ 与 $C_n^m$ 解决常规排队/分组问题。
2. 理解递推本质：Stirling、错排、Catalan 的核心都在于“分类讨论最后一个元素的状态”，建议手绘状态转移图。
3. 编程验证：遇到复杂计数题，可用 Python/C++ 写暴力递归或 DP 验证小数据，再推导通项。
4. 真题导向：CSP-J/S 初赛常考 Catalan 与 错排，NOIP/省选偏爱 Stirling 数与容斥原理结合，务必熟记递推式与边界条件。

---

一、排列与组合基础（第1～6题）

【题1】 从7本不同的书中任选3本，并按顺序摆放在书架的同一层，共有 {{ input(1) }} 种不同的摆法。

【题2】 某班级有10名学生，现要从中选出4人组成学习小组（不考虑组内顺序），共有 {{ input(2) }} 种选法。

【题3】 已知 $C(n, 2) = 15$，则正整数 $n$ 的值为 {{ input(3) }}。

【题4】 用数字1、2、3、4、5组成没有重复数字的三位数，共有 {{ input(4) }} 个。

【题5】 集合 $A = \{a, b, c, d\}$ 的所有子集（包含空集和自身）共有 {{ input(5) }} 个。

【题6】 计算 $C(8, 3) + C(8, 4)$ 的值等于 {{ input(6) }}。

二、圆排列与重复问题（第7～12题）

【题7】 8名同学围成一圈做游戏，若只考虑相对位置（旋转后相同视为同一种），共有 {{ input(7) }} 种不同的围法。

【题8】 从6颗颜色各不相同的珠子中选出4颗串成一个手环（仅考虑旋转等价，不考虑翻转），共有 {{ input(8) }} 种不同的串法。

【题9】 单词 BANANA 中的字母重新排列，能组成 {{ input(9) }} 个不同的单词。

【题10】 将4个相同的红球和3个相同的蓝球排成一行，共有 {{ input(10) }} 种不同的排法。

【题11】 用数字 1,1,2,2,3,3 这6个数字组成六位数，共有 {{ input(11) }} 个不同的六位数。

【题12】 5对夫妇围坐在圆桌旁，若每对夫妇必须相邻而坐，共有 {{ input(12) }} 种不同的坐法。

三、特殊组合模型（第13～18题）

【题13】 一家甜品店有5种口味的蛋糕，每种口味供应充足。小明想买6块蛋糕（允许重复口味），共有 {{ input(13) }} 种不同的购买方案。

【题14】 方程 $x_1 + x_2 + x_3 = 10$ 的非负整数解共有 {{ input(14) }} 组。

【题15】 将8颗完全相同的糖果分给4个小朋友，要求每人至少分到1颗，共有 {{ input(15) }} 种分法。

【题16】 从自然数 $1 \sim 10$ 中选出4个数，要求任意两个数都不相邻，共有 {{ input(16) }} 种选法。

【题17】 在一排10个连续的座位中，选择3个座位放置警示牌，要求任意两个警示牌不相邻，共有 {{ input(17) }} 种放法。

【题18】 集合 $\{1, 2, \dots, 12\}$ 中，恰好包含5个元素且元素互不相邻的子集共有 {{ input(18) }} 个。

四、递推数列应用：Stirling、错排与Catalan（第19～30题）

【题19】 第二类 Stirling 数 $S(5, 2)$ 的值为 {{ input(19) }}。

【题20】 将6名不同的学生分成3个非空小组（小组无编号/无序），共有 {{ input(20) }} 种分法。

【题21】 利用公式 $S(n,3) = \frac{1}{2}(3^{n-1}+1) - 2^{n-1}$，计算 $S(6,3)$ 的值为 {{ input(21) }}。

【题22】 错位排列数 $D_4$ 的值为 {{ input(22) }}。

【题23】 5封不同的信投入5个对应的信箱，每封信都投错了信箱，共有 {{ input(23) }} 种投法。

【题24】 利用公式 $D_n = nD_{n-1} + (-1)^n$，计算 $D_6$ 的值为 {{ input(24) }}。

【题25】 7个人参加聚会，各自将帽子混放后随机取一顶，恰好没有人拿到自己帽子的情况有 {{ input(25) }} 种。

【题26】 3对括号 () 能组成 {{ input(26) }} 种合法的括号序列。

【题27】 一个栈的进栈序列为 $1,2,3,4$，则可能的不同出栈序列共有 {{ input(27) }} 种。

【题28】 由5个不同的节点可以构造出 {{ input(28) }} 棵不同的二叉搜索树。

【题29】 在圆周上取8个点，两两连线成4条弦，要求所有弦互不相交，共有 {{ input(29) }} 种连线方法。

【题30】 用数字 $0,1,2,3,4$ 组成无重复数字的四位数，且该数能被5整除，共有 {{ input(30) }} 个。