排列组合计数4个工具搞定小球分盒问题【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki刷题做到一半我被一道题卡了整整两分钟7个相同小球放进3个不同盒子每盒至少1个球。第一反应是算 7×6×5后来才意识到这是经典的插板法问题答案只有15。读完这篇你能独立处理排列组合、小球分盒、整除与不整除这三类计数问题。先花30秒建立全景工具一句话定义加法原理「分类」的方案数直接相加乘法原理「分步」的方案数依次相乘排列 Aₙᵐ从n个不同元素选m个排成一列顺序敏感组合 C(n,m)从n个不同元素选m个不管顺序插板法相同元素分进k组等价于线性方程的解的组数容斥原理有「重复 / 不重复」条件时加加减减这些工具的完整推导在组合数文档的排列、组合与插板法一节里都有。当题目说「把相同物品分进不同组」适用条件元素完全相同、组可区分盒子1、盒子2、盒子3是不同的且带「每组至少1个 / 可以为空」这类条件。推导思路把n个相同小球排成一排两两之间共有n−1个空往空里插板子就能把球切成k段。把板子想象成一串糖上的刀口切在哪里就是唯一的区别。每组至少1个球正整数解$$\binom{n-1}{k-1}$$也就是从n−1个空中挑k−1个插板仅此而已。允许某组为空时先借k个球让每组都不空插完板再还回去$$\binom{nk-1}{n}$$这就是方程 $x_1x_2\cdotsx_kn$ 非负整数解的组数。最小例子3个相同球分进2个不同盒子允许为空$\binom{32-1}{3}\binom{4}{3}4$。手写枚举 (0,3)、(1,2)、(2,1)、(3,0)正好4种。边界提醒一旦某个盒子有上限比如「盒子1最多放2个」纯插板法失效要再配容斥把超上限的解剔掉。当题目说「从一堆人里选几个 / 排成一列」适用条件元素互不相同只问「多少种」。「顺序重不重要」决定了用排列还是组合这是第一判断。推导思路第一个位置有n种选法第二个n−1种依此类推乘起来$$\mathrm{A}_n^m\frac{n!}{(n-m)!}$$一句话排列数就是「座位数」按顺序发。顺序不重要时每选出的m个人组被重复数了m!次除掉它$$\binom{n}{m}\frac{n!}{m!(n-m)!}$$一句话组合数就是「人组数」。最小例子5人选2个排队。方法一直接 $\mathrm{A}_5^25\times420$方法二先选人 $\binom{5}{2}10$再让2人内部互换2!种也得20。两条路都对但显然方法一更快少绕一步。边界提醒mn 时按定义 $\binom{n}{m}0$别硬套公式去算分母。当题目问「整除、不整除、必须都出现」适用条件条件以「不、都、至少一个」这类否定或全称形式出现直接数很费劲。推导思路$|A|$ 和 $|B|$ 各自数完相加交集被数了两次减一次$$|A\cup B||A||B|-|A\cap B|$$三个集合时三集合的交集被减了3次要加回来一次$$|A\cup B\cup C||A||B||C|-|A\cap B|-|B\cap C|-|C\cap A||A\cap B\cap C|$$把它想象成先撒大网再把捞重复的部分挑出来。最小例子1~12中能被2整除的有6个能被3整除的有4个两者都整除即被6整除的有2个所以 $64-28$。边界提醒属性个数k超过4个时手算就费劲了该用代码枚举 $2^k$ 个子集先检查k再动手。高频题型实战题17个相同小球放进3个不同盒子每盒至少1个球有多少种思路题目里「相同」二字出现先想到插板法「每盒至少1个」是正整数解不用借球。 结果n−16个空中选2个插板$\binom{6}{2}15$ 种。题25个人围桌而坐要求甲乙必须相邻有多少种思路圆排列有公式 $(n-1)!$甲乙相邻没法直接放先把两人捆成一个块。4个块围一圈 $(4-1)!6$ 种甲乙在块内可左右互换乘2。 结果$6\times212$ 种。题31~12中既不能被2整除也不能被3整除的数有几个思路「既不也不」是双重否定直接数麻烦。先数补集「能被2或3整除」64其中交集被6整除有2个必须减掉否则多扣——这就是本题的陷阱。 结果$12-(64-2)4$ 个。⚠️ 易错点清单❌ 用排列算「相同球分盒」套 $\mathrm{A}_7^3$ → 为什么错球是相同的交换任意两个并不产生新分法A按不同元素算会重复 → ✅ 用插板法 $\binom{6}{2}15$。❌ 「允许为空」直接套正整数公式 $\binom{n-1}{k-1}$ → 为什么错不空与可空差一个公式直接用会少算 → ✅ 先借k再插板$\binom{nk-1}{n}$比如n3、k2时是4种而非2种。❌ 圆排列直接写n! → 为什么错整圈旋转后是同一种坐法n!多算了n倍 → ✅ 用 $(n-1)!$比如5人围桌是24种不是120种。❌ 容斥时先减各集再减交集 → 为什么错$|A\cap B|$ 被减了两次答案偏小 → ✅ 先加单集再减交集$64-28$。现在你手里多了三件工具排列组合、插板法、容斥原理题2里那招圆排列也算见过。下一步去读组合数性质看公式怎么帮你少算一半步数再翻翻容斥原理的应用里面有硬币购物这类进阶例题。【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
