OI 组合数学实战指南7 个竞赛场景吃透排列组合计数技巧与完整公式速查【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki本文基于 OI-wiki 开源项目的数学模块从一道真实的 OI 计数题出发按问题场景 → 解题工具的映射组织 OI 组合数学内容加法/乘法原理、排列数与组合数、插板法三变体、容斥原理、圆排列、二项式反演等计数技巧一次讲清并附组合数性质完整速查表帮你快速建立见题型想工具的反射。先看题目10 个球塞进 3 个盒子 下面这道题在很多 OI 模拟考中都出现过把 10 个完全相同的小球放进 3 个有编号的盒子里每个盒子至少放 1 个问有多少种放法硬枚举会很累设三个盒子分别放 $x_1,x_2,x_3$ 个条件就是 $x_1x_2x_310$ 且 $x_i\ge 1$。如果 $n$ 变成 1000枚举直接判死刑。组合数学的做法是把数方案改写成套公式这个式子的正整数解个数恰好等于 $\binom{10-1}{3-1}\binom{9}{2}36$。为什么是这个数背后的工具叫插板法后面工具箱一节会展开。下面先把最底层的两把算盘讲清楚再一层层搭到这道题的解法上。两个基础计算工具加法与乘法原理 所有计数问题最后都会落到这两个原理上先分清分类和分步。加法原理几类方案之间是或的关系一顿午餐只选一样吃餐车窗口有 4 种汤、5 种面任选一种即可。总方案数是$$ S 4 5 9 $$一般地一件事拆成 $n$ 类互不重叠的做法第 $i$ 类有 $a_i$ 种总数就是 $Sa_1a_2\cdotsa_n$。乘法原理几个步骤之间是且的关系点一份套餐要连续做两个决定主菜 3 种、配饮品 2 种都各取其一。总方案数是$$ S 3 \times 2 6 $$一般地一件事要按顺序走 $n$ 步第 $i$ 步有 $a_i$ 种走法总数就是 $Sa_1\times a_2\times\cdots\times a_n$。一句话判别方案能划分成若干类类与类之间用或连接 → 加法原理过程拆成若干步步骤之间用且连接 → 乘法原理。混合使用时先对每一类内部用乘法再对类之间用加法即可。排列数与组合数一个管顺序一个不管区分这两个概念只有一条标准选出来的东西要不要排序。排列数$\mathrm{A}_n^m$也写作 $\mathrm{P}_n^m$从 $n$ 个不同元素取 $m$ 个排成一列$m\le n$位置 1 有 $n$ 种选法、位置 2 有 $n-1$ 种、……连乘得$$ \mathrm{A}_n^m n(n-1)\cdots(n-m1) \frac{n!}{(n-m)!} $$$mn$ 时就是全排列 $\mathrm{A}_n^nn!$。组合数$\dbinom{n}{m}$只取 $m$ 个、不管先后。每一组取法若强行排队会被重复计算 $m!$ 次所以除以 $m!$$$ \dbinom{n}{m} \frac{\mathrm{A}_n^m}{m!} \frac{n!}{m!(n-m)!} $$约定 $mn$ 时 $\mathrm{A}_n^m\dbinom{n}{m}0$。算例8 名选手中——选 3 人评出金、银、铜牌有顺序$\mathrm{A}_8^3 8\times7\times6 336$ 种只抽 3 人组成小组无顺序$\dbinom{8}{3}\dfrac{8!}{3!,5!}56$ 种。两者关系一目了然$336 56\times 6 56\times 3!$即先挑人再给这 3 个人排座位。解题工具箱一类问题配一个工具 下面每个小节对应一类高频题型比赛时按题型对号入座即可。插板法三种变体怎么选插板法处理的核心是相同物品分进不同容器等价于线性不定方程解的个数。把 $n$ 个相同物品摆成一排相邻物品之间有 $n-1$ 个空隙选几个空隙放隔板即可分组。变体约束条件答案关键操作① 正整数解$x_i\ge 1$$\dbinom{n-1}{k-1}$直接在 $n-1$ 个空隙插 $k-1$ 块板② 非负整数解$x_i\ge 0$$\dbinom{nk-1}{n}$先给每组预放 1 个再插板最后收回③ 不同下界$x_i\ge a_i$$\dbinom{n-\sum a_ik-1}{k-1}$令 $x_ix_i-a_i$ 先消化下界变体①就是开头的球盒题$\binom{9}{2}36$。变体②算例5 颗相同糖果分给 3 个有编号的袋子允许空袋。答案 $\binom{53-1}{3}\binom{7}{3}35$。变体③算例求 $x_1x_2x_312$ 满足 $x_1\ge 2,\ x_2\ge 1,\ x_3\ge 0$ 的解的个数。代换 $x_1x_1-2,\ x_2x_2-1$ 后化为 $x_1x_2x_39$ 的非负解套变体②得 $\binom{93-1}{3}\binom{11}{2}55$。容斥原理重叠部分要减掉统计至少命中一个条件的方案数时直接相加会把同时命中多个条件的方案重复计数于是先加后减、再加后减交替进行$$ |A\cup B\cup C| |A||B||C| - |A\cap B|-|A\cap C|-|B\cap C| |A\cap B\cap C| $$算例统计 $1\sim 100$ 中能被 2 或 3 整除的整数个数。记 $A$ 为 2 的倍数$50$ 个$B$ 为 3 的倍数$33$ 个交集 $A\cap B$ 是 6 的倍数$\lfloor 100/6\rfloor16$ 个所以答案是 $5033-1667$。用途提示凡题目出现至少一个至多一个恰好一个这类模糊条件优先考虑容斥把模糊翻译成精确。推导细节可查官方文档docs/math/combinatorics/inclusion-exclusion-principle.md。圆排列固定一人答案除以 n场景圆桌围坐时整体旋转不算新方案。$n$ 个人围成一圈固定其中一人作为参照点切断旋转自由度剩下 $n-1$ 人线性排队$$ \mathrm{Q}_n^n \frac{\mathrm{A}_n^n}{n} (n-1)! $$算例6 个选手围坐讨论席方案数为 $(6-1)! 120$。只围坐一部分人时公式推广为 $\mathrm{Q}_n^r \dfrac{\mathrm{A}_n^r}{r}$。注意只有整体旋转等价才除以 $n$若翻转镜像也算同一种如手链还要再除以 2。二项式反演把至少翻译成恰好设 $f_n$ 是恰好使用 $n$ 个不同元素的方案数$g_n$ 是至多使用 $n$ 个元素即不超过 $n$ 个的方案数两者满足$$ g_n \sum_{i0}^{n}\binom{n}{i}f_i $$方向反过来由 $g_n$ 求 $f_n$ 就是二项式反演$$ f_n \sum_{i0}^{n}\binom{n}{i}(-1)^{n-i}g_i $$用途提示当恰好 $k$很难直接数、而至少/至多 $k$容易数时用反演公式取回精确值是计数题里最经典的换道超车手段。组合数性质速查表⚡ 比赛时真正高频的是下面这几条建议背下来名称公式典型用途对称性$\binom{n}{m}\binom{n}{n-m}$$m$ 接近 $n$ 时把参数换小杨辉三角递推$\binom{n}{m}\binom{n-1}{m}\binom{n-1}{m-1}$$O(n^2)$ 递推打表预处理组合数二项式定理$(ab)^n\sum_{i0}^n\binom{n}{i}a^{n-i}b^i$取 $ab1$ 得 $\sum\binom{n}{i}2^n$子集总数、三角每行求和范德蒙恒等式$\sum_{i0}^k\binom{n}{i}\binom{m}{k-i}\binom{mn}{k}$组合数拆开重组卷积题核心朱世杰恒等式$\sum_{l0}^n\binom{l}{k}\binom{n1}{k1}$三角中斜线求和、恒等式证明更多性质带权和、平方和、斐波那契关联式等在官方文档中有完整整理docs/math/combinatorics/combination.md。多重集的排列与组合多重集的排列设 $S{n_1\cdot a_1,,n_2\cdot a_2,,\dots,,n_k\cdot a_k}$共 $nn_1\cdotsn_k$ 个元素全排列数为$$ \binom{n}{n_1,n_2,\dots,n_k}\frac{n!}{n_1!,n_2!\cdots n_k!} $$算例把 2 个 a、3 个 b 排成一串共 $\dfrac{5!}{2!,3!}10$ 种。用途字母重复的字符串计数、排序后相同的序列有多少个这类题直接套。多重集的组合从 $S$ 中取 $r$ 个但每种元素至多取 $n_i$ 个——这比插板法多了一层上限需要用容斥把超限方案剔掉答案为$$ \mathrm{Ans}\sum_{p0}^{k}(-1)^{p}\ \sum_{\substack{A\subseteq{1,\dots,k}\ |A|p}} \binom{kr-1-\sum_{i\in A}n_i-p}{k-1} $$用途带上下限的线性方程解数、有上限的相同物品分组。注意区分两个易混概念——多重组合数指上面那类排列公式多重集的组合数指带限制选取的问题官方文档在 docs/math/combinatorics/combination.md 中专门做了辨析。学习路径练题方向与下一步 建议按一个工具配 2~3 道题的节奏巩固插板法先练三种变体各自的基础题再练下界上限混合容斥原理从能被哪些数整除系列入手过渡到恰好满足某性质圆排列/排列组合配合插空法不相邻选取混合题练。后续方向可以沿 OI-wiki 的组合数学模块继续深入卡特兰数、错排、斯特林数、范德蒙卷积以及多项式与生成函数方向docs/math/poly/——生成函数能把上述大量恒等式统一成展开取系数的单一套路是计数进阶的分水岭。【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 
长河君 · 2026/9/4 12:50:24 · 阅读 1.2k OI 组合数学实战指南：7 个竞赛场景吃透排列组合计数技巧与完整公式速查
OI 组合数学实战指南7 个竞赛场景吃透排列组合计数技巧与完整公式速查【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki本文基于 OI-wiki 开源项目的数学模块从一道真实的 OI 计数题出发按问题场景 → 解题工具的映射组织 OI 组合数学内容加法/乘法原理、排列数与组合数、插板法三变体、容斥原理、圆排列、二项式反演等计数技巧一次讲清并附组合数性质完整速查表帮你快速建立见题型想工具的反射。先看题目10 个球塞进 3 个盒子 下面这道题在很多 OI 模拟考中都出现过把 10 个完全相同的小球放进 3 个有编号的盒子里每个盒子至少放 1 个问有多少种放法硬枚举会很累设三个盒子分别放 $x_1,x_2,x_3$ 个条件就是 $x_1x_2x_310$ 且 $x_i\ge 1$。如果 $n$ 变成 1000枚举直接判死刑。组合数学的做法是把数方案改写成套公式这个式子的正整数解个数恰好等于 $\binom{10-1}{3-1}\binom{9}{2}36$。为什么是这个数背后的工具叫插板法后面工具箱一节会展开。下面先把最底层的两把算盘讲清楚再一层层搭到这道题的解法上。两个基础计算工具加法与乘法原理 所有计数问题最后都会落到这两个原理上先分清分类和分步。加法原理几类方案之间是或的关系一顿午餐只选一样吃餐车窗口有 4 种汤、5 种面任选一种即可。总方案数是$$ S 4 5 9 $$一般地一件事拆成 $n$ 类互不重叠的做法第 $i$ 类有 $a_i$ 种总数就是 $Sa_1a_2\cdotsa_n$。乘法原理几个步骤之间是且的关系点一份套餐要连续做两个决定主菜 3 种、配饮品 2 种都各取其一。总方案数是$$ S 3 \times 2 6 $$一般地一件事要按顺序走 $n$ 步第 $i$ 步有 $a_i$ 种走法总数就是 $Sa_1\times a_2\times\cdots\times a_n$。一句话判别方案能划分成若干类类与类之间用或连接 → 加法原理过程拆成若干步步骤之间用且连接 → 乘法原理。混合使用时先对每一类内部用乘法再对类之间用加法即可。排列数与组合数一个管顺序一个不管区分这两个概念只有一条标准选出来的东西要不要排序。排列数$\mathrm{A}_n^m$也写作 $\mathrm{P}_n^m$从 $n$ 个不同元素取 $m$ 个排成一列$m\le n$位置 1 有 $n$ 种选法、位置 2 有 $n-1$ 种、……连乘得$$ \mathrm{A}_n^m n(n-1)\cdots(n-m1) \frac{n!}{(n-m)!} $$$mn$ 时就是全排列 $\mathrm{A}_n^nn!$。组合数$\dbinom{n}{m}$只取 $m$ 个、不管先后。每一组取法若强行排队会被重复计算 $m!$ 次所以除以 $m!$$$ \dbinom{n}{m} \frac{\mathrm{A}_n^m}{m!} \frac{n!}{m!(n-m)!} $$约定 $mn$ 时 $\mathrm{A}_n^m\dbinom{n}{m}0$。算例8 名选手中——选 3 人评出金、银、铜牌有顺序$\mathrm{A}_8^3 8\times7\times6 336$ 种只抽 3 人组成小组无顺序$\dbinom{8}{3}\dfrac{8!}{3!,5!}56$ 种。两者关系一目了然$336 56\times 6 56\times 3!$即先挑人再给这 3 个人排座位。解题工具箱一类问题配一个工具 下面每个小节对应一类高频题型比赛时按题型对号入座即可。插板法三种变体怎么选插板法处理的核心是相同物品分进不同容器等价于线性不定方程解的个数。把 $n$ 个相同物品摆成一排相邻物品之间有 $n-1$ 个空隙选几个空隙放隔板即可分组。变体约束条件答案关键操作① 正整数解$x_i\ge 1$$\dbinom{n-1}{k-1}$直接在 $n-1$ 个空隙插 $k-1$ 块板② 非负整数解$x_i\ge 0$$\dbinom{nk-1}{n}$先给每组预放 1 个再插板最后收回③ 不同下界$x_i\ge a_i$$\dbinom{n-\sum a_ik-1}{k-1}$令 $x_ix_i-a_i$ 先消化下界变体①就是开头的球盒题$\binom{9}{2}36$。变体②算例5 颗相同糖果分给 3 个有编号的袋子允许空袋。答案 $\binom{53-1}{3}\binom{7}{3}35$。变体③算例求 $x_1x_2x_312$ 满足 $x_1\ge 2,\ x_2\ge 1,\ x_3\ge 0$ 的解的个数。代换 $x_1x_1-2,\ x_2x_2-1$ 后化为 $x_1x_2x_39$ 的非负解套变体②得 $\binom{93-1}{3}\binom{11}{2}55$。容斥原理重叠部分要减掉统计至少命中一个条件的方案数时直接相加会把同时命中多个条件的方案重复计数于是先加后减、再加后减交替进行$$ |A\cup B\cup C| |A||B||C| - |A\cap B|-|A\cap C|-|B\cap C| |A\cap B\cap C| $$算例统计 $1\sim 100$ 中能被 2 或 3 整除的整数个数。记 $A$ 为 2 的倍数$50$ 个$B$ 为 3 的倍数$33$ 个交集 $A\cap B$ 是 6 的倍数$\lfloor 100/6\rfloor16$ 个所以答案是 $5033-1667$。用途提示凡题目出现至少一个至多一个恰好一个这类模糊条件优先考虑容斥把模糊翻译成精确。推导细节可查官方文档docs/math/combinatorics/inclusion-exclusion-principle.md。圆排列固定一人答案除以 n场景圆桌围坐时整体旋转不算新方案。$n$ 个人围成一圈固定其中一人作为参照点切断旋转自由度剩下 $n-1$ 人线性排队$$ \mathrm{Q}_n^n \frac{\mathrm{A}_n^n}{n} (n-1)! $$算例6 个选手围坐讨论席方案数为 $(6-1)! 120$。只围坐一部分人时公式推广为 $\mathrm{Q}_n^r \dfrac{\mathrm{A}_n^r}{r}$。注意只有整体旋转等价才除以 $n$若翻转镜像也算同一种如手链还要再除以 2。二项式反演把至少翻译成恰好设 $f_n$ 是恰好使用 $n$ 个不同元素的方案数$g_n$ 是至多使用 $n$ 个元素即不超过 $n$ 个的方案数两者满足$$ g_n \sum_{i0}^{n}\binom{n}{i}f_i $$方向反过来由 $g_n$ 求 $f_n$ 就是二项式反演$$ f_n \sum_{i0}^{n}\binom{n}{i}(-1)^{n-i}g_i $$用途提示当恰好 $k$很难直接数、而至少/至多 $k$容易数时用反演公式取回精确值是计数题里最经典的换道超车手段。组合数性质速查表⚡ 比赛时真正高频的是下面这几条建议背下来名称公式典型用途对称性$\binom{n}{m}\binom{n}{n-m}$$m$ 接近 $n$ 时把参数换小杨辉三角递推$\binom{n}{m}\binom{n-1}{m}\binom{n-1}{m-1}$$O(n^2)$ 递推打表预处理组合数二项式定理$(ab)^n\sum_{i0}^n\binom{n}{i}a^{n-i}b^i$取 $ab1$ 得 $\sum\binom{n}{i}2^n$子集总数、三角每行求和范德蒙恒等式$\sum_{i0}^k\binom{n}{i}\binom{m}{k-i}\binom{mn}{k}$组合数拆开重组卷积题核心朱世杰恒等式$\sum_{l0}^n\binom{l}{k}\binom{n1}{k1}$三角中斜线求和、恒等式证明更多性质带权和、平方和、斐波那契关联式等在官方文档中有完整整理docs/math/combinatorics/combination.md。多重集的排列与组合多重集的排列设 $S{n_1\cdot a_1,,n_2\cdot a_2,,\dots,,n_k\cdot a_k}$共 $nn_1\cdotsn_k$ 个元素全排列数为$$ \binom{n}{n_1,n_2,\dots,n_k}\frac{n!}{n_1!,n_2!\cdots n_k!} $$算例把 2 个 a、3 个 b 排成一串共 $\dfrac{5!}{2!,3!}10$ 种。用途字母重复的字符串计数、排序后相同的序列有多少个这类题直接套。多重集的组合从 $S$ 中取 $r$ 个但每种元素至多取 $n_i$ 个——这比插板法多了一层上限需要用容斥把超限方案剔掉答案为$$ \mathrm{Ans}\sum_{p0}^{k}(-1)^{p}\ \sum_{\substack{A\subseteq{1,\dots,k}\ |A|p}} \binom{kr-1-\sum_{i\in A}n_i-p}{k-1} $$用途带上下限的线性方程解数、有上限的相同物品分组。注意区分两个易混概念——多重组合数指上面那类排列公式多重集的组合数指带限制选取的问题官方文档在 docs/math/combinatorics/combination.md 中专门做了辨析。学习路径练题方向与下一步 建议按一个工具配 2~3 道题的节奏巩固插板法先练三种变体各自的基础题再练下界上限混合容斥原理从能被哪些数整除系列入手过渡到恰好满足某性质圆排列/排列组合配合插空法不相邻选取混合题练。后续方向可以沿 OI-wiki 的组合数学模块继续深入卡特兰数、错排、斯特林数、范德蒙卷积以及多项式与生成函数方向docs/math/poly/——生成函数能把上述大量恒等式统一成展开取系数的单一套路是计数进阶的分水岭。【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考