组合容斥 · 考纲词条练习

考点：组合数快算 C(8,2)（A1）。

（A1）考点：组队不分角色是组合：$C(8,2) = \dfrac{8 \times 7}{2} = 28$。（2022 年 CSP-S 单选真题）

解析：两人组内无序：$8 \times 7$ 的有序选法除以 $2!$；分子连乘 $k$ 项、分母 $k!$ 是快算定式。

排除法：选 $64$ 的人按 $8^2$ 放回有序算了；选 $56$ 的人忘了除以 $2$（那是 $A(8,2)$ 有序）；选 $32$ 的人凑了 $2^5$。

考点：对称式 C(n,k)=C(n,n-k)（A2）。

（A2）考点：$C(10, 8) = C(10, 2) = \dfrac{10 \times 9}{2} = 45$——选 $8$ 个等于留 $2$ 个。

解析：对称式是"算小的那边"的开关；$k > n/2$ 时立即翻转，避免连乘 8 项。

排除法：选 $90$ 的人硬连乘算错；选 $80$ 的人按 $10 \times 8$ 算；选 $10$ 的人只算了分子一半。

考点：边界值 C(n,0) 与 C(n,n)（A3）。

（A3）考点：$C(n, 0) = C(n, n) = 1$：一个都不选、全选，都恰有一种方案。

解析：公式层面 $\dfrac{n!}{0!\,n!} = 1$；组合层面"空选"是合法且唯一的方案。

排除法：选 $0$ 和 $2026$ 的人以为不选就是零种；选 $1$ 和 $2026$ 的人只对一半；选 $2026$ 和 $1$ 的人方向反了。

考点：帕斯卡递推回顾（A4）。

（A4）考点：杨辉三角的生成式：$C(n,k) = C(n-1,k-1) + C(n-1,k)$——第 $n$ 行由上一行两肩相加。

解析：从 $n$ 个里选 $k$ 个，按"是否含指定元素"二分：含它再选 $k-1$、不含它选 $k$——递推的组合理义。

排除法：A 是对称式、B 是全和公式、C 是吸收式变形——只有 D 写出了两肩相加。

考点：排列组合区分回顾（A5）。

（A5）考点：正副组长职务不同是有序：$A(5,2) = 20$；参加活动不分角色是无序：$C(5,2) = 10$。

解析：先问"换了顺序算不算新方案"：算则排列、不算则组合。

排除法：选都是 $10$ 的人把两个有序当无序；选 $10$ 和 $20$ 的人安反了；选 $25$ 的人按 $5^2$ 算。

考点：大 n 小 k 约分（A6）。

（A6）考点：$C(100,2) = \dfrac{100 \times 99}{2} = 4950$——连乘 $k$ 项除以 $k!$，绝不碰 $100!$。

解析：$\dfrac{n(n-1)\cdots(n-k+1)}{k!}$ 的分子恰好 $k$ 项；这既是手算技巧也是编程防爆写法。

排除法：选先算 $100!$ 的人会溢出；选查表的人第 $100$ 行不现实；选对称算 $98$ 项的人把对称式用反了方向。

考点：阶乘溢出边界（A7）。

（A7）考点：long long 上限约 $9.2 \times 10^{18}$，$20! \approx 2.4 \times 10^{18}$ 装得下、$21!$ 溢出——直接存阶乘最大 $20!$。

解析：$25!$、$30!$ 远超上限；组合数计算要边乘边除（或预处理逆元），不要先算大阶乘再除。

排除法：选 $15!$ 的人低估了上限；选 $25!$、$30!$ 的人高估——都需按 $9.2 \times 10^{18}$ 逐一对照。

考点：有序对与无序对（A8）。

（A8）考点：$6$ 点的有向线段（区分起终点）$= 6 \times 5 = 30$；无向线段 $= C(6,2) = 15$。

解析：有序对 $n(n-1)$、无序对除以 $2$——图论里"完全图边数"用的就是无向口径（H 组展开）。

排除法：选 $15$ 和 $30$ 的人答反；选都是 $15$ 的人漏了有序情形；选 $36$ 和 $30$ 的人把 $6 \times 6$ 当有序对。

考点：多重集全排公式（B1）。

（B1）考点：多重集 $\{a{\times}2, b{\times}2, c{\times}2\}$ 的全排 $= \dfrac{6!}{2!\,2!\,2!} = \dfrac{720}{8} = 90$。

解析：$6!$ 个全排列中，同字母的两个副本互换不产生新串——每种重复除掉 $r_i!$；公式 $\dfrac{n!}{\prod r_i!}$。

排除法：选 $720$ 的人没除重复；选 $48$ 的人乱除；选 $120$ 的人只除了一个 $2!$。

考点：aabb 全排（B2）。

（B2）考点：$\dfrac{4!}{2!\,2!} = \dfrac{24}{4} = 6$：aabb、abab、abba、baab、baba、bbaa。

解析：两种字母各重复 $2$——分母两个 $2!$ 相乘；小例子可全枚举验证公式。

排除法：选 $24$ 的人没除；选 $12$ 的人只除了一个 $2!$；选 $4$ 的人少除了。

考点：aab 型枚举（B3）。

（B3）考点：$\dfrac{3!}{2!} = 3$：aab、aba、baa——重复的 a 换位不产生新串。

解析：多重集公式 $n=3$ 最小非平凡例；全枚举与公式一致。

排除法：选 $6$ 的人没除 $2!$；选 $2$ 的人漏了一种；选 $1$ 的人过度去重。

考点：全同元素排列为 1（B4）。

（B4）考点：$\{a{\times}4\}$ 全排 $= \dfrac{4!}{4!} = 1$——全同元素只有一种排法。

解析：公式的极限情形：分母把分子的所有交换全部除尽；"aaa 相互换位置"看不见。

排除法：选 $24$ 的人没除；选 $4$ 的人把元素数当方案；选 $0$ 的人以为不算排列。

考点：数字 1,1,2,4,8,8 组四位数（B5）。

（B5）考点：多重集 $\{1,1,2,4,8,8\}$ 取 $4$ 个排成四位数，按"取到哪些多重子集"分类：$C(6,4)=15$ 种子集中含重复的除重，合计 $102$。（2019 年 CSP-S 单选真题）

解析：四元子集分三类——四元素互不相同（$2$ 种？含 $1,2,4,8$：$4!=24$）、恰一对相同（如 $1,1,2,4$：$\dfrac{4!}{2!}=12$，共 $7$ 种此类子集）……逐类累加恰得 $102$；手算费劲，模拟验证最稳（验算脚本已断言）。

排除法：选 $98$、$100$、$104$ 的人都是某一类去重漏/多算一步——精确分类是本题全部难度。

考点：必含某重复元素（B6）。

（B6）考点：四位数必须用上两个 $8$：再从 $\{1,1,2,4\}$ 多重子集选 $2$ 个，共 $\{1,1\},\{1,2\},\{1,4\},\{2,4\}$ 四类，每类 $\dfrac{4!}{2!} = 12$，合计 $48$。

解析：把"必须含双 8"固化后，问题缩成"小多重集选 2"：$4 \times 12 = 48$。

排除法：选 $60$、$36$ 的人子集分类不全；选 $12$ 的人只算了一类。

考点：多重集组合定理背景（B7）。

（B7）考点：多重集组合 $=$ 从含重复元素的集合选取，同色不可区分——数的是"每种各取几个"的方案向量。

解析：区别于普通组合（元素互异）：$3$ 红 $5$ 蓝里选 $4$ 个，答案是"红 $i$ 蓝 $4-i$"的可行 $i$ 个数，而非 $C(8,4)$。

排除法：选互异选取的人是普通组合；选排一排的人是排列；选分组排序的人是多步混题。

考点：可重组合与多重组合辨析（B8）。

（B8）考点：无限供应同种可重复取：合法，隔板法 $C(4+6-1, 3) = C(9,3) = 84$；各不相同却要选超过总数：$C(4,6) = 0$，不合法。

解析：可重组合的公式在 J 卷隔板法已立（球同盒异）；本题对照"不可重选取超量即零"。

排除法：选"数相同"的人一个 $84$ 一个 $0$；选"前者不合法"的人反了；选"排列组合"的人概念错位。

考点：限量多重组合（B9）。

（B9）考点：库存 $2,3,4$ 各一颗同种，取 $4$ 颗：非负解 $x_1{+}x_2{+}x_3{=}4$ 共 $C(6,2)=15$，减去 $x_1 \ge 3$ 的 $C(3,2)=3$ 种，得 $12$。

解析：上限约束用"总数减违规"（容斥思想小试）；库存上限 $3$ 与 $4$ 在取 $4$ 时不会越界，只有 $x_1 \le 2$ 起约束。

排除法：选 $15$ 的人忘了 $x_1$ 上限；选 $9$ 的人多减了不存在的违规；选 $6$ 的人减过头。

考点：字母组词计数（B10）。

（B10）考点：MATHS 五个字母互不相同，全排 $= 5! = 120$。

解析：无重复字母就是普通全排；与 B1 对照可见"重复除重"才是多重集的增量。

排除法：选 $5$ 的人只数了字母个数；选 $60$ 的人错除；选 $3125$ 的人按 $5^5$ 放回排列算。

考点：含 0 数字首位限制（B11）。

（B11）考点：$\{0,1,2,2\}$ 组四位数：多重全排 $\dfrac{4!}{2!} = 12$，减首位为 $0$ 的（剩 $\{1,2,2\}$ 排三位 $\dfrac{3!}{2!} = 3$），得 $9$。

解析："多重排列 $+$ 首位限制"两步走：先全排再去违规；首位 $0$ 时剩余元素仍按多重排。

排除法：选 $12$ 的人没去首位 $0$；选 $4$ 的人乱减；选 $6$ 的人减多了。

考点：多重集综合（B12）。

（B12）考点：$M = \{a{\times}2, b{\times}2, c{\times}2\}$ 全排 $\dfrac{6!}{2!\,2!\,2!} = 90$：每个字母的两个副本互换不可见。

解析：公式 $\dfrac{n!}{\prod r_i!}$ 的直接应用；取 $4$ 个的排列须逐种子集分类，不能直接套全排公式（选项 C 的错误）。

排除法：选 $720$（即 $6!$ 原值）的人没除重复；选"取 4 也套同公式"的人混淆了选取与全排；选 $3! \times 2 = 12$ 的人把字母种类排法当了全排，取 $4$ 个的排列须另行分类。

考点：两集并公式（C1）。

（C1）考点：$|A \cup B| = |A| + |B| - |A \cap B|$：交里的元素被两个单集数了两遍，减回一遍。

解析：容斥的原子公式；"加回来、减回去"的交替本质由此展开。

排除法：直接相加的人重复计交；加交的人越加越多；相乘的人把笛卡尔积当并。

考点：两并数值（C2）。

（C2）考点：$30 + 20 - 12 = 38$：至少参加一科 $38$ 人。

解析：两科都参加的 $12$ 人被 $30$、$20$ 各数一次，多算一份，减去。

排除法：选 $50$ 的人没减交；选 $62$ 的人把交错当加；选 $42$ 的人减成了单科值。

考点：三集并公式（C3）。

（C3）考点：$|A \cup B \cup C| = \sum|单| - \sum|两两交| + |三交|$：先加回、多减的加回、又多加的再减——交错修正。

解析：单看某元素属于 $s$ 个集合，它被数 $1 + (s-1)$ 次后净剩 $1$ 次；交错符号保证恰好计一次。

排除法：加两交的人方向反；只加单集的人重叠区域多数；加减三交的人漏了中间层修正。

考点：三并数值（C4）。

（C4）考点：$20 + 15 + 10 - 8 - 6 - 5 + 3 = 29$。

解析：三步走：单集和 $45$、减两两交和 $19$ 得 $26$、加回三交 $3$ 得 $29$。

排除法：选 $45$ 的人只加了单集；选 $33$ 的人漏加三交；选 $26$ 的人漏了最后的 $+3$。

考点：补集思想（C5）。

（C5）考点："至少一个"难数时数补集"一个都没有"，总数减之——正难则反。

解析：补集法与容斥是一体两面：当"至少"条件多且杂时，反面"全不满足"往往一刀切齐。

排除法：硬枚举的人在条件多时指数爆炸；只数最大集合的人漏并；相乘的人无据。

考点：都不发生（C6）。

（C6）考点：喜欢篮球或足球的 $= 40 + 30 - 15 = 55$；都不喜欢 $= 100 - 55 = 45$。

解析：两步：先容斥求并、再补集求都不；"总 $-$ 并"是德摩根律的直接运用（C12）。

排除法：选 $55$ 的人答成了"至少喜欢一个"；选 $30$ 的人只减了一科；选 $15$ 的人答成交集。

考点：棋盘两格容斥（C7）。

（C7）考点：任选两格 $C(16,2) = 120$，减同行 $4 \times C(4,2) = 24$、减同列 $24$：$120 - 48 = 72$。（2020 年 CSP-S 单选真题）

解析："不同行不同列"= 全选 $-$ 同行 $-$ 同列（同行同列互斥，无需加回）；两减各自用 $C(4,2)$ 数一行/列内的两格。

排除法：选 $60$ 的人只减了一类；选 $86$ 的人减成了 $120 - 34$；选 $64$ 的人按 $8 \times 8$ 乱配。

考点：文氏图区域（C8）。

（C8）考点：两个集合的文氏图有 $3$ 块互不重叠区域：只在 $A$、只在 $B$、同时在 $A$ 和 $B$。

解析：每块元素被"是否属于各集合"唯一刻画；容斥计算本质是给各块配正确的系数。

排除法：选 $2$ 的人漏了交；选 $4$ 的人多算了一块外区域（题目问集合划分的块）；选 $6$ 的人那是三集合的 $7$ 块口径错记。

考点：至少一个（C9）。

（C9）考点：含 $1$ 或含 $2$：$C(9,2) + C(9,2) - C(8,1) = 36 + 36 - 8 = 64$。

解析：含 $1$ 的：定 $1$ 再从其余 $9$ 个选 $2$，$36$；含 $2$ 同理 $36$；同时含 $1,2$ 的被数两遍，减 $C(8,1) = 8$。

排除法：选 $84$ 的人没减交（$36+36+12$ 类乱加）；选 $112$ 的人减错对象；选 $56$ 的人答成了"都不含"。

考点：错排容斥式（C10）。

（C10）考点：$D_n = n!\left(\dfrac{1}{0!} - \dfrac{1}{1!} + \cdots \pm \dfrac{1}{n!}\right)$：全排列减"至少一个归位"各类，交叠交错修正。

解析：固定某 $k$ 个元素归位的排法有 $(n-k)!$ 种，除以 $k!$ 组合选取——逐层容斥得交错和；与递推式（J 卷学过）互为表里。

排除法：选 $n!-(n-1)!$ 的人只减了"1 归位"没管交叠；选递推式的人答的是另一形态（题问容斥式）；选 $n!/2$ 的人无据。

考点：错排值验证（C11）。

（C11）考点：$D_4 = 24\left(1 - 1 + \dfrac{1}{2} - \dfrac{1}{6} + \dfrac{1}{24}\right) = 9$。

解析：$24 - 24 + 12 - 4 + 1 = 9$，与递推式 $D_4 = 9$ 相互印证。

排除法：选 $24$ 的人第一项后没继续减；选 $12$ 的人算到第三项停笔；选 $8$ 的人交错号错了一个。

考点：德摩根与容斥（C12）。

（C12）考点："都不喜欢" $=$ 总 $-$ 至少喜欢一个，依据是德摩根律 $\overline{A \cup B} = \overline{A} \cap \overline{B}$。

解析：补的并等于交的补——容斥求并后取补，正是这条集合律在计数里的投影。

排除法：分配律/吸收律/幂等律都不刻画"补与并交的转换"。

考点：间接法与容斥关系（C13）。

（C13）考点：J 卷"总数减都不满足"的间接法是容斥的补集特例：单条件一减即得；多条件时需完整容斥交错加减。

解析：条件越多交叠层越多——间接法是一层容斥，完整容斥是它的多层推广。

排除法：选"毫无关系"的人没看到补集结构；选"错误推广"的人方向反；选"只适用概率"的人计数同样适用。

考点：容斥综合（C14）。

（C14）考点：$1 \sim 100$ 被 $2$ 或 $3$ 整除：$\lfloor 100/2 \rfloor + \lfloor 100/3 \rfloor - \lfloor 100/6 \rfloor = 50 + 33 - 16 = 67$。

解析：被 $2$ 整除 $50$ 个、被 $3$ 整除 $33$ 个、被 $6$ 整除（同时）$16$ 个——减去多算的 $16$。

排除法：选 $83$ 的人没减 $16$；选 $88$ 的人乱配数；正确值是 $67$（$50+33-16$）；选 $16$ 的人只答了交集。

考点：不相邻选择公式（D1）。

（D1）考点：$n$ 个排位选 $k$ 个互不相邻：$C(n-k+1, k)$。

解析：直觉"先选再查相邻"会乱；公式的钥匙是变换法（D3）——把不相邻化归普通组合。

排除法：选 $C(n,k)$ 的人没管相邻；选 $C(n-k,k)$ 的人差一位；选 $C(n-1,k-1)$ 的人那是"含指定元素"公式。

考点：公式代入计算（D2）。

（D2）考点：$n=8, k=3$：$C(8-3+1, 3) = C(6,3) = 20$。

解析：代入时"减 $k$ 加一"别丢一：$8-3+1=6$；$C(6,3)=20$。

排除法：选 $56$ 的人没做变换（$C(8,3)$）；选 $10$ 的人多减了；选 $35$ 的人算成 $C(7,3)$。

考点：变换法证明思路（D3）。

（D3）考点：把选中的 $k$ 个位置各"吃掉"身后一个空位，$n$ 个位置缩成 $n-k$ 个，原不相邻方案与"$n-k$ 个位置中任选 $k$ 个"一一对应——双射证明。

解析：缩位后不再有相邻约束；双射两边计数相等即公式成立；这是"化归"思想的典型一课。

排除法：枚举排除的人在 $n$ 大时失效；容斥逐步减的人绕远；"没有直观解释"的人没见过缩位映射。

考点：k 等于 1 边界（D4）。

（D4）考点：$k=1$：$C(n-1+1, 1) = C(n,1) = n$——与直觉吻合，公式自洽。

解析：选 $1$ 个无所谓相邻，公式自动退化；用边界情形体检公式是数学惯例。

排除法：选 $n-1$ 不吻合的人把公式记成了 $C(n-k,k)$；选 $1$、$n+1$ 的人代入错位。

考点：8 苹果不相邻（D5）。

（D5）考点：选 $1 \sim 4$ 个不相邻之和：$C(8,1) + C(7,2) + C(6,3) + C(5,4) = 8 + 21 + 20 + 5 = 54$。（2021 年 CSP-S 单选真题）

解析：逐个 $k$ 套公式再求和；$k$ 最大到 $4$（$8$ 个位置最多塞 $4$ 个互不相邻）。

排除法：选 $36$ 的人漏了高 $k$ 项；选 $48$ 的人某项算错；选 $64$ 的人按 $2^6$ 乱猜。

考点：至少一个的求和（D6）。

（D6）考点：$54$ 的构成：$C(8,1)=8$、$C(7,2)=21$、$C(6,3)=20$、$C(5,4)=5$——注意每项的 $n-k+1$ 在变。

解析：求和式的每一项都按各自的 $k$ 换公式参数；别用同一个 $C$ 值重复加。

排除法：选 $8+28+56+70$ 的人全部按 $C(8,k)$ 没做变换；选 $8+21+15+10$ 的人后两项减多；选 $C(8,4)$ 的人只算了 $k=4$。

考点：5 红 5 蓝插空（D7）。

（D7）考点：红球无区别排好后，$6$ 个空位（含两端）选 $5$ 个放蓝（同色无序）：$C(6,5) = 6$。（2025 年 CSP-S 单选真题）

解析：同色球先排一种"骨架"、空位插另一色——红球排列数是 $1$（全同），只剩插空选择。

排除法：选 $25$ 的人按 $5 \times 5$ 算；选 $30$ 的人按 $C(6,5) \times 5$ 多乘；选 $120$ 的人按全排列算（球同色不可区分）。

考点：插空两端空间（D8）。

（D8）考点：$5$ 个红球排成一排，空位 $=$ 球间 $4$ 个 $+$ 两端 $2$ 个 $= 6$ 个。

解析：$n$ 个元素产生 $n+1$ 个空位（含两端）——插空法的第一步就是数清空位。

排除法：选 $4$ 的人漏了两端；选 $5$ 的人数成了球数；选 $7$ 的人多数一端。

考点：与捆绑法对比（D9）。

（D9）考点：必须相邻 $=$ 捆绑成一个整体参与外层排列；互不相邻 $=$ 先排其他、往空隙里插——两个方向相反的构造法。

解析：捆绑"合"、插空"分"；复杂题里两法连用（某组内捆绑、组间要求与其他元素不相邻）。

排除法：都用插空的人没区分约束方向；方向安反的人恰好说反。

考点：不相邻综合（D10）。

（D10）考点：$6$ 人排一排、甲乙不相邻：总数 $6! = 720$ 减相邻的（捆成一体的 $5! \times 2 = 240$）：$720 - 240 = 480$。

解析：不相邻的人事排列用"总数减捆绑相邻"——与 D5 的"位置选取插空"是两种场景两种打法。

排除法：选 $720$ 的人没排除相邻；选 $240$ 的人答成了相邻数；选 $600$ 的人减成了 $5!$。

考点：格路计数（E1）。

（E1）考点：$(0,0)$ 到 $(3,2)$：$5$ 步中选 $3$ 步向右（其余向上）：$C(5,3) = 10$。

解析：路径由"哪几步向右"唯一决定；右步位置定了，上步自动填满其余。

排除法：选 $5$ 的人按步数算；选 $6$ 的人按 $\binom{4}{2}$ 错位；选 $25$ 的人按 $5^2$ 猜。