Appearance
排列与组合精讲
1. 基本计数原理
加法原理
若完成一件事有 $k$类办法，第$i$类办法中有$m_i$ 种不同方法，且各类办法彼此独立，则完成这件事共有 $$N = m_1 + m_2 + \cdots + m_k$$ 种不同的方法。
乘法原理
若完成一件事需要 $k$个步骤，第$i$步有$m_i$ 种不同方法，则完成这件事共有 $$N = m_1 \times m_2 \times \cdots \times m_k$$ 种不同的方法。
例：穿衣搭配
小明有 3 件上衣、2 条裤子。由乘法原理，共有 $3\times2=6$ 种搭配。
2. 排列 (Permutation)
排列的定义
从 $n$个不同元素中取出$m$ ($1\le m\le n$) 个元素，按照一定的顺序排成一列，叫做一个排列。所有不同排列的个数称为排列数，记作 $A_n^m$(或$P(n,m)$)。
当 $m=n$时称为全排列，记作$A_n^n = n!$。
排列数公式推导
利用乘法原理：第1位有 $n$种选法，第2位有$n-1$种，...，第$m$位有$n-m+1$ 种。 $$A_n^m = n(n-1)(n-2)\cdots(n-m+1) = \frac{n!}{(n-m)!}$$ 约定 $0! = 1$，则 $A_n^0 = 1$。
2.1 可重复排列
从 $n$个不同元素中取$m$个元素，允许重复的排列数为$n^m$。
2.2 圆排列
$n$个不同元素围成一圈，由于没有首尾之分，可先固定一个元素，其余$(n-1)$ 个任意排列，因此 $$Q_n = (n-1)!$$
2.3 有重复元素的排列
若 $n$个元素中有$k$类相同元素，第$i$类有$n_i$ 个 ($\sum n_i = n$)，则全排列数为 $$\frac{n!}{n_1!\thinspace{}n_2!\thinspace\cdots\thinspace{}n_k!}$$
3. 组合 (Combination)
组合的定义
从 $n$个不同元素中取出$m$个元素，不考虑顺序并成一组，叫做一个组合。所有不同组合的个数称为组合数，记作$C_n^m$或$\binom{n}{m}$。
组合数公式推导
从 $n$个元素中取$m$个的排列数$A_n^m$可视为：先取$m$个元素组成一组（组合），再将这$m$ 个元素全排列。因此 $$A_n^m = C_n^m \cdot m! \quad\Longrightarrow\quad C_n^m = \frac{A_n^m}{m!} = \frac{n!}{m!\thinspace(n-m)!}$$
组合数的基本性质
- 对称性：$\binom{n}{m} = \binom{n}{n-m}$
- 递推关系 (帕斯卡法则)：$\binom{n}{m} = \binom{n-1}{m} + \binom{n-1}{m-1}$
- 二项式定理：$\displaystyle (x+y)^n = \sum_{k=0}^{n} \binom{n}{k} x^{n-k}y^k$
- 多重集组合 (隔板法模型)：从 $n$种不同元素中取$m$个（允许重复、不考虑顺序）的组合数为$\binom{n+m-1}{m}$。
4. 经典题型与方法
4.1 相邻问题 — 捆绑法
例：7人站一排，甲、乙必须相邻
将甲、乙视为一个“大元素”，内部有 $2!$种排法；此时相当于6个元素全排列，共$6!$种。总数为$2!\times6! = 1440$。
4.2 不相邻问题 — 插空法
例：5男3女站一排，女生互不相邻
先排5个男生，有 $5!$种，产生 6 个空位（包括两端）。从6个空位中选3个给女生，女生全排列$3!$。总数为 $5!\times \binom{6}{3} \times 3! = 14400$。
4.3 相同元素分配 — 隔板法
正整数解
方程 $x_1+x_2+\cdots+x_m = n$ ($x_i\ge1$) 的正整数解个数为 $\binom{n-1}{m-1}$。相当于在 $n$个“1”之间的$n-1$个空隙中插入$m-1$ 块隔板。
非负整数解个数为 $\binom{n+m-1}{m-1}$(先令$y_i=x_i+1$ 转化为正整数解)。
4.4 分组分配问题
- 不同元素均匀分组：若分成每堆个数相同的无区别组，需除以组数的阶乘。
例：6本不同书分成3堆，每堆2本： $\frac{\binom{6}{2}\binom{4}{2}\binom{2}{2}}{3!} = 15$。
- 分配给人：若组有区别（分给不同人），则直接相乘，无需除以阶乘。
4.5 定序问题 — 倍缩法
$n$个元素排成一列，其中$m$个元素顺序固定，则排列数为$\frac{n!}{m!}$。 (视作从全排列中去掉这些元素内部顺序)
4.6 错位排列 (Derangement)
$n$个元素的全错位排列数记为$D_n$ (所有元素都不在原来的位置)。
- 递推公式：$D_1=0,\thickspace D_2=1$，$D_n = (n-1)(D_{n-1}+D_{n-2})$
- 容斥原理表达式：$\displaystyle D_n = n!\sum_{k=0}^{n}\frac{(-1)^k}{k!}$
常用值：$D_3=2,\thickspace D_4=9,\thickspace D_5=44$。
4.7 容斥原理在排列组合中的应用
设 $A_i$ 为满足某种限制的排列集合，则 $$\left|\bigcup_{i=1}^n A_i\right| = \sum|A_i| - \sum|A_i\cap A_j| + \cdots + (-1)^{n-1}|A_1\cap\cdots\cap A_n|.$$ 常用于求解“至少有一类限制被满足”的问题或错排问题。
5. 习题精选 (12 道，由易到难)
- 1. 计算 $A_8^3$与$\binom{10}{4}$。
- 解答
$$A_8^3 = 8\times7\times6 = 336.$$ $$\binom{10}{4} = \frac{10\times9\times8\times7}{4\times3\times2\times1} = 210.$$
:::
- 2. 用数字 0,1,2,3,4 可以组成多少个没有重复数字的三位偶数？
- 解答
按个位分类：
- 个位为0：百位从1,2,3,4选 $4$种，十位从剩下3个选$3$种 →$4\times3=12$。
- 个位为2或4：个位 $2$种；百位不能是0且不能与个位同，有$3$种；十位剩下$3$种。 →$2\times3\times3=18$。
合计 $12+18=30$ 个。
:::
- 3. 7人站成一排，其中甲、乙、丙三人必须相邻，有多少种排法？
- 解答
将甲、乙、丙捆绑成一整体，内部全排列 $3!$。整体与其他4人共5个元素全排列 $5!$。
总数：$3!\times5! = 6\times120 = 720$。
:::
- 4. 5个男生和3个女生站成一排，若女生互不相邻，有多少种排法？
- 解答
先排5名男生：$5! = 120$。
男生形成6个空位（包括两端），从中选3个空位放入女生，女生有序排列：$\binom{6}{3}\times3! = 20\times6 = 120$。
总数：$120\times120 = 14400$。
:::
- 5. 5对夫妇共10人围圆桌就坐，要求每对夫妇必须相邻，有多少种不同坐法？
- 解答
将每对夫妇视为一个整体，圆排列：$(5-1)! = 24$。
每对夫妇内部可交换座位：$2^5 = 32$。
总数：$24\times32 = 768$。
:::
- 6. 将15个完全相同的小球放入4个不同的盒子中，每个盒子至少放3个，有多少种放法？
- 解答
先每盒投入3个，用去 $12$个球，剩余$3$ 个球可任意分配（非负整数解）。
方程 $y_1+y_2+y_3+y_4 = 3,\thickspace y_i\ge0$的解数为$\binom{3+4-1}{4-1} = \binom{6}{3} = 20$。
:::
- 7. 6本不同的书分成三堆，每堆2本，有多少种分法？
- 解答
先无序选取：$\binom{6}{2}\binom{4}{2}\binom{2}{2} = 15\times6\times1 = 90$。
因三堆无区别，需除以 $3!$。
结果：$\frac{90}{6} = 15$ 种。
:::
- 8. 字母 A,A,A,B,B,C 全部排成一排，其中三个A互不相邻的排列有多少种？
- 解答
先排B,B,C：共有 $\frac{3!}{2!}=3$ 种排列（例如 B B C, B C B, C B B）。
每种排列产生4个空位（两端及之间），需选3个空位各放入一个A，且A相同，故只需选空位 $\binom{4}{3}=4$。
总数：$3\times4 = 12$。
:::
- 9. 编号为1,2,3,4,5的5个人，每人有一顶帽子，现随机戴帽，求所有人都戴错的戴法数。
- 解答
5个元素的错位排列数 $D_5$。
递推：$D_1=0, D_2=1, D_3=2, D_4=9$，$D_5=4\times(9+2)=44$。
或公式：$D_5 = 5!\left(1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+\frac{1}{4!}-\frac{1}{5!}\right)=120\left(\frac{1}{2}-\frac{1}{6}+\frac{1}{24}-\frac{1}{120}\right)=44$。
:::
- 10. 如图，某城市街道呈矩形网格，从西南角A走到东北角B，只能向北或向东行进。若必须经过点P(标记为路口)，求最短路径条数。（设A到B为4条街向东，5条街向北，P在从A向东2、向北3处）
- 解答
总步数：向东4步，向北5步。经过P的条件：先从A到P（向东2，向北3），再从P到B（向东2，向北2）。
A到P：路径数 $\binom{2+3}{2}=10$。
P到B：路径数 $\binom{2+2}{2}=6$。
总数：$10\times6 = 60$。
:::
- 11. 求方程 $x_1+x_2+x_3+x_4=20$满足条件$x_1\ge2,\thickspace x_2\ge3,\thickspace x_3\ge4,\thickspace x_4\ge1$ 的整数解个数。
- 解答
令 $y_1=x_1-2,\thickspace y_2=x_2-3,\thickspace y_3=x_3-4,\thickspace y_4=x_4-1$，则 $y_i\ge0$，且 $y_1+y_2+y_3+y_4=20-(2+3+4+1)=10$。
非负整数解数为 $\binom{10+4-1}{4-1}=\binom{13}{3}=286$。
:::
- 12. (传球问题) 甲、乙、丙、丁四人进行传球练习，从甲开始传球，经过5次传球后球又回到甲手中，求传球方法数（每次传球可传给其他三人中的任意一人）。
- 解答
设 $a_n$为传$n$次后球在甲手中的方法数，则$a_0=1$，且 $a_{n} = 3^{n-1} - a_{n-1}$对于$n\ge1$(思考：总传球方式$3^n$ 中，甲接球的前一次必不是甲)。
计算：$a_1=0$，$a_2=3^{1}-0=3$，$a_3=3^2-3=6$，$a_4=3^3-6=21$，$a_5=3^4-21=81-21=60$。
或使用递推矩阵，结果：60 种。
:::