OI 计数技巧入门：排列组合 3 类高频题 + 一套组合数学公式速查表
【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. （某大型游戏线上攻略，内含炫酷算术魔法）项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki
OI 计数里最劝退的，往往不是计算，而是一上来就不知道该用哪个工具：看到 $\dbinom{n}{k}$ 想半天、见到 $x_1+x_2+\cdots+x_k=n$ 就发懵。这 3 道题都是 OI 计数与组合数学入门题里的高频面孔，我们把背后的排列组合技巧一层层拆给你看。
第一关：数清一种"安排"，先拆决策
题：5 个同学站成一排合影，其中甲必须站在中间位置，共有多少种站法？
做法拆开看：中间的位置被甲占掉，只剩 4 个位置，让剩下 4 个人全排进去，得 $\mathrm A_4^4 = 4! = 24$ 种。这里用到的是乘法原理的变体——每个位置独立做决策，方案数就是各步方案数相乘。
顺带把最基础的两个数说清：从 $n$ 个不同对象里取 $m$ 个排好顺序，是排列数 $\mathrm A_n^m=\dfrac{n!}{(n-m)!}$；取 $m$ 个不管顺序，是组合数 $\dbinom{n}{m}=\dfrac{n!}{m!(n-m)!}$。
例题：6 个人围圆桌坐，旋转后重合的算同一种，多少种坐法？
- 圆桌上没有"第一个位置"，先把 1 号固定住，破除旋转对称；
- 剩下 5 人在 5 个位置全排列；
- 答案 $(6-1)! = 120$。
⚠️ 这里有个坑：线性排队是 $n!$，圆排列是 $(n-1)!$，差的那一个因子就是"旋转对称"。别背公式，先问自己"谁被固定了"。
第二关：x₁+x₂+…+xₖ=n 的解，交给插板法
题：把 10 颗相同糖分给 3 个小朋友，每人至少 1 颗，多少种分法？
方程形式就是 $x_1+x_2+x_3=10$，$x_i\ge 1$。
- 糖分成一排，10 颗糖之间有 $10-1$ 个空隙；
- 在空隙里插 2 块板，把糖切成 3 段；
- 从 9 个空隙选 2 个插板，答案 $\dbinom{9}{2}=36$。
换个角度想，插板法其实就是"在 $k-1$ 个隔板里选位置"，所以正整数解的组数永远是 $\dbinom{n-1}{k-1}$。
插板法处理非负整数解的 3 种变形
变形一：允许分 0 颗（$x_i\ge 0$）。
直接插板会失效——板子可以叠在同一个空隙里。套路是先"借"：给每人先发 1 颗，总量变成 $n+k$，回到正整数情形，再退掉每人借的 1 颗。答案 $\dbinom{n+k-1}{k-1}$。
例题：$x_1+x_2+x_3=10$，$x_i\ge 0$，多少组非负解？
- 先发 3 颗，转成"13 颗、每人至少 1 颗"；
- $\binom{13-1}{3-1}=\binom{12}{2}$；
- 答案 $66$。
变形二：各变量有下界（$x_i\ge a_i$）。
先给第 $i$ 个人拨足 $a_i$ 颗，剩下 $n-\sum a_i$ 颗按无限制分，答案 $\binom{n+k-1}{k-1}$，其中 $n$ 换成 $n-\sum a_i$。
例题：$x_1+x_2=5$，且 $x_1\ge 2$。
- 先把 2 颗拨给 $x_1$，剩 3 颗自由分给两人；
- $\binom{3+2-1}{2-1}=\binom{4}{1}$；
- 答案 $4$，手查 $(2,3),(3,2),(4,1),(5,0)$ 正好对上。
变形三：带上界。
"每堆不超过 $c$"没法直接插板，通常绕道容斥：先算无限制的组数，再减去"某堆 $\ge c+1$"的方案——这个下一关登场。
第三关：带"不能""恰好"的条件，上容斥原理
题：1 到 100 中，既不能被 2 整除、也不能被 3 和 5 整除的整数有多少个？
正着想要按 2、3、5 的倍数情况分类讨论，烦得很。反过来，用容斥原理数掉"坏"的。
设 $A,B,C$ 分别是被 2、3、5 整除的数的集合，$|A|=50,\ |B|=33,\ |C|=20$；两两交集 $|A\cap B|=\lfloor 100/6\rfloor=16$，$|A\cap C|=20$，$|B\cap C|=10$；三集合交集 $|A\cap B\cap C|=20$。
- 先加：$50+33+20$；
- 再减两两重叠：$-16-20-10$；
- 加回被减掉的三重重叠：$+20$，得 $|A\cup B\cup C|=74$。
答案 $100-74=26$。
💡 一句话直觉：加单个、减两两交、加三个交，交替进行，直到把每类重叠恰好抵消。数值上 $74=103-46+20$，与上式一致。
从"至少一个"到"恰好 k 个"
容斥还能处理"恰好"。经典结论：$n$ 元集合上恰好命中 $k$ 个指定性质的方案数，可以用"命中至多 $k$ 个"逐层容斥叠出来；而"至少命中 1 个"就是全集减去"一个都不命中"。
例题：4 人分 4 顶互不相同的帽子，恰好有 2 人拿到自己帽子的分法？
- 先选那 2 人：$\binom{4}{2}=6$；
- 剩下 2 人必须互相拿错，只有 1 种（对换）；
- 答案 $6$。
组合数性质速查表
| 公式 | 名字 | 一句话直觉 | 5 秒数值验证 |
|---|---|---|---|
| $\dbinom{n}{m}=\dbinom{n}{n-m}$ | 对称性 | 选走 $m$ 个 = 留下 $n-m$ 个 | $\binom{5}{2}=\binom{5}{3}=10$ |
| $\dbinom{n}{m}=\dbinom{n-1}{m}+\dbinom{n-1}{m-1}$ | 杨辉三角递推 | 第 $n$ 行由上一行两肩相加得到 | $6=3+3$ |
| $(a+b)^n=\sum\limits_{i=0}^{n}\dbinom{n}{i}a^{n-i}b^i$ | 二项式定理 | 展开时"选 $i$ 项取 $b$"的方案数即系数 | $(1+x)^2=1+2x+x^2$ |
| $\sum\limits_{i}\dbinom{r}{i}\dbinom{s}{k-i}=\dbinom{r+s}{k}$ | 范德蒙恒等式 | 从 $r+s$ 人里选 $k$ 人 = 按两边人数分组求和 | $\binom{2}{0}\binom{2}{2}+\binom{2}{1}\binom{2}{1}+\binom{2}{2}\binom{2}{0}=1+4+1=6=\binom{4}{2}$ |
| $\sum\limits_{i=0}^{n}\dbinom{i}{k}=\dbinom{n+1}{k+1}$ | 朱世杰恒等式 | 杨辉三角中一条斜线之和仍是三角里的数 | $1+3+6=10=\binom{4}{3}$ |
公式的严格推导建议对照仓库文档 docs/math/combinatorics/combination.md 和 docs/math/combinatorics/vandermonde-convolution.md，那里给了组合意义解释；容斥部分可看 docs/math/combinatorics/inclusion-exclusion-principle.md。
下一步：3 件事验证你自己
- 回 OJ 上把这 3 道原型题亲手做一遍：线性+圆排列、"分球/求非负整数解"、"既不能……也不能……"的计数，各对应本文一、二、三关，能 10 分钟内写出答案就算过关。
- 自己推导一遍二项式定理与范德蒙恒等式（各用组合意义证，不超过半页纸），推不出来就回去读 docs/math/combinatorics/combination.md。
- 把上面那张速查表抄进自己的笔记，合上原文默写 5 个公式，卡壳的那条就是你下一周的复习重点。
【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. （某大型游戏线上攻略，内含炫酷算术魔法）项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki
创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
