Principle of Inclusion-Exclusion (PIE)容斥原理

When counting elements in the union of multiple sets, naive summation causes overcounting (elements in intersections counted multiple times). PIE corrects this by alternately adding and subtracting intersections to ensure each element is counted exactly once.

2.2 Formula Derivation

Two sets:

$$\mathrm{\mid }A\cup B\mathrm{\mid }=\mathrm{\mid }A\mathrm{\mid }+\mathrm{\mid }B\mathrm{\mid }-\mathrm{\mid }A\cap B\mathrm{\mid }$$∣A∪B∣=∣A∣+∣B∣−∣A∩B∣

Explanation: Add $\mathrm{\mid }A\mathrm{\mid }$∣A∣ and $\mathrm{\mid }B\mathrm{\mid }$∣B∣, but $A\cap B$A∩B counted twice → subtract once.

Three sets:

$$\begin{array}{rl}{\displaystyle \mathrm{\mid }A\cup B\cup C\mathrm{\mid }=}& {\displaystyle \mathrm{\mid }A\mathrm{\mid }+\mathrm{\mid }B\mathrm{\mid }+\mathrm{\mid }C\mathrm{\mid }}\\ {\displaystyle }& {\displaystyle -\mathrm{\mid }A\cap B\mathrm{\mid }-\mathrm{\mid }A\cap C\mathrm{\mid }-\mathrm{\mid }B\cap C\mathrm{\mid }}\\ {\displaystyle }& {\displaystyle +\mathrm{\mid }A\cap B\cap C\mathrm{\mid }}\end{array}$$∣A∪B∪C∣= ​∣A∣+∣B∣+∣C∣−∣A∩B∣−∣A∩C∣−∣B∩C∣+∣A∩B∩C∣​

Explanation:

1. Add single sets
2. Subtract pairwise intersections (each counted twice in step 1)
3. Add back triple intersection (subtracted too many times in step 2)

General form for n sets:

$$\mid \bigcup _{i=1}^n{A}_i\mid =\sum _{k=1}^n(-1{)}^{k+1}(\sum _{1\le i_1<\cdots <i_k\le n}\mathrm{\mid }{A}_{i_1}\cap \cdots \cap A_{i_k}\mathrm{\mid })$$​i=1⋃n​Ai​​=k=1∑n​(−1)k+1(1≤i1​<⋯<ik​≤n∑​∣Ai1​​∩⋯∩Aik​​∣)

Equivalently (complement form, useful for “none of” problems):

$$\mid \bigcap _{i=1}^n\overline{A_i}\mid =\mathrm{\mid }U\mathrm{\mid }-\sum \mathrm{\mid }{A}_i\mathrm{\mid }+\sum \mathrm{\mid }{A}_i\cap A_j\mathrm{\mid }-\cdots +(-1{)}^n\mathrm{\mid }{A}_1\cap \cdots \cap A_n\mathrm{\mid }$$​i=1⋂n​Ai​​​=∣U∣−∑∣Ai​∣+∑∣Ai​∩Aj​∣−⋯+(−1)n∣A1​∩⋯∩An​∣

2.3 Combinatorial Justification

Consider an element $x$x belonging to exactly $m$m sets ($1\le m\le n$1≤m≤n). Its total contribution in PIE is:

$$\left(\genfrac{}{}{0px}{}{m}{1}\right)-\left(\genfrac{}{}{0px}{}{m}{2}\right)+\left(\genfrac{}{}{0px}{}{m}{3}\right)-\cdots +(-1{)}^{m+1}\left(\genfrac{}{}{0px}{}{m}{m}\right)=1$$(1m​)−(2m​)+(3m​)−⋯+(−1)m+1(mm​)=1

Proven by binomial theorem: $(1-1{)}^m={\sum }_{k=0}^m(-1{)}^k\left(\genfrac{}{}{0px}{}{m}{k}\right)=0$(1−1)m=∑k=0m​(−1)k(km​)=0.

Solved Examples

Example 1: Basic Two-Set Problem

In a class of 40 students, 25 like math, 20 like physics, and 10 like both. How many like at least one subject? How many like neither?

Solution:

• Let $M$M = math lovers, $P$P = physics lovers
• $\mathrm{\mid }M\mathrm{\mid }=25,\mathrm{\mid }P\mathrm{\mid }=20,\mathrm{\mid }M\cap P\mathrm{\mid }=10$∣M∣=25, ∣P∣=20, ∣M∩P∣=10
• At least one: $\mathrm{\mid }M\cup P\mathrm{\mid }=25+20-10=35$∣M∪P∣=25+20−10=35
• Neither: $40-35=5$40−35=5 students

Example 2: Three-Set Divisibility Problem

Among integers 1 to 1000, how many are divisible by at least one of 2, 3, or 5?

Solution:

• $A=\{x\mid 2\mathrm{\mid }x\},B=\{x\mid 3\mathrm{\mid }x\},C=\{x\mid 5\mathrm{\mid }x\}$A={x∣2∣x}, B={x∣3∣x}, C={x∣5∣x}
• $\mathrm{\mid }A\mathrm{\mid }=\lfloor 1000\mathrm{/}2\rfloor =500$∣A∣=⌊1000/2⌋=500
• $\mathrm{\mid }B\mathrm{\mid }=\lfloor 1000\mathrm{/}3\rfloor =333$∣B∣=⌊1000/3⌋=333
• $\mathrm{\mid }C\mathrm{\mid }=\lfloor 1000\mathrm{/}5\rfloor =200$∣C∣=⌊1000/5⌋=200
• Pairwise intersections (using LCM):
  • $\mathrm{\mid }A\cap B\mathrm{\mid }=\lfloor 1000\mathrm{/}6\rfloor =166$∣A∩B∣=⌊1000/6⌋=166
  • $\mathrm{\mid }A\cap C\mathrm{\mid }=\lfloor 1000\mathrm{/}10\rfloor =100$∣A∩C∣=⌊1000/10⌋=100
  • $\mathrm{\mid }B\cap C\mathrm{\mid }=\lfloor 1000\mathrm{/}15\rfloor =66$∣B∩C∣=⌊1000/15⌋=66
• Triple intersection: $\mathrm{\mid }A\cap B\cap C\mathrm{\mid }=\lfloor 1000\mathrm{/}30\rfloor =33$∣A∩B∩C∣=⌊1000/30⌋=33
• Union size:$$\begin{array}{rl}{\displaystyle \mathrm{\mid }A\cup B\cup C\mathrm{\mid }}& {\displaystyle =500+333+200-166-100-66+33}\\ {\displaystyle }& {\displaystyle =734}\end{array}$$∣A∪B∪C∣​=500+333+200−166−100−66+33=734​
• Not divisible by any: $1000-734=266$1000−734=266

Example 3: Non-Square Non-Cube Counting

Count integers from 1 to 10000 that are neither perfect squares nor perfect cubes.

Solution:

• Universal set $U=\{1,\dots ,10000\},\mathrm{\mid }U\mathrm{\mid }=10000$U={1,…,10000}, ∣U∣=10000
• Squares: $\mathrm{\mid }A\mathrm{\mid }=\lfloor \sqrt{10000}\rfloor =100$∣A∣=⌊10000​⌋=100
• Cubes: $\mathrm{\mid }B\mathrm{\mid }=\lfloor \sqrt[3]{10000}\rfloor =21$∣B∣=⌊310000​⌋=21
• Sixth powers (both square and cube): $\mathrm{\mid }A\cap B\mathrm{\mid }=\lfloor {10000}^{1\mathrm{/}6}\rfloor =4$∣A∩B∣=⌊100001/6⌋=4
• Neither:$$\mathrm{\mid }\bar{A}\cap \bar{B}\mathrm{\mid }=10000-100-21+4=9883$$∣A∩B∣=10000−100−21+4=9883

Example 4: Derangements (Classic PIE Application)

In how many ways can 5 letters be placed into 5 envelopes such that no letter goes into its correct envelope?

Solution:

• Total permutations: $5!=120$5!=120
• Let $A_i$Ai​ = arrangements where letter $i$i is correctly placed
• Target: $\mathrm{\mid }\overline{A_1}\cap \cdots \cap \overline{A_5}\mathrm{\mid }$∣A1​​∩⋯∩A5​​∣
• By PIE:$$\begin{array}{rl}{\displaystyle D_5}& {\displaystyle =5!-\left(\genfrac{}{}{0px}{}{5}{1}\right)4!+\left(\genfrac{}{}{0px}{}{5}{2}\right)3!-\left(\genfrac{}{}{0px}{}{5}{3}\right)2!+\left(\genfrac{}{}{0px}{}{5}{4}\right)1!-\left(\genfrac{}{}{0px}{}{5}{5}\right)0!}\\ {\displaystyle }& {\displaystyle =120-120+60-20+5-1=44}\end{array}$$D5​​=5!−(15​)4!+(25​)3!−(35​)2!+(45​)1!−(55​)0!=120−120+60−20+5−1=44​
• General derangement formula:$$D_n=n!\sum _{k=0}^n\frac{(-1{)}^k}{k!}\approx \frac{n!}{e}$$Dn​=n!k=0∑n​k!(−1)k​≈en!​

Example 5: Olympiad-Style Problem (CMO Level)

Select maximum number of integers from 1 to 2021 such that the difference between any two selected numbers is neither 4 nor 7.

Solution Sketch (mod 11 classification):

• If $a-b=4$a−b=4 or $7$7, then $a\equiv b+4(\mathrm{m}\mathrm{o}\mathrm{d}11)$a≡b+4(mod11) or $a\equiv b+7(\mathrm{m}\mathrm{o}\mathrm{d}11)$a≡b+7(mod11)
• Partition into 11 residue classes mod 11
• Conflict graph forms an 11-cycle (since $4+7\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}11)$4+7≡0(mod11))
• Maximum independent set in 11-cycle has size 5
• Class sizes: 183 or 184 elements each
• Optimal selection: 5 classes with 184 elements → $5\times 184=920$5×184=920
• Answer: 920

---

IV. Problem-Solving Strategies

1. Recognizing PIE scenarios:
   • “At least one” → compute $\mathrm{\mid }{A}_1\cup \cdots \cup A_n\mathrm{\mid }$∣A1​∪⋯∪An​∣
   • “None” → compute $\mathrm{\mid }\overline{A_1}\cap \cdots \cap \overline{A_n}\mathrm{\mid }$∣A1​​∩⋯∩An​​∣
   • “Exactly k” → $\mathrm{\mid }\text{at least }k\mathrm{\mid }-\mathrm{\mid }\text{at least }k+1\mathrm{\mid }$∣at least k∣−∣at least k+1∣
2. Intersection computation:
   • Divisibility: $\mathrm{\mid }{A}_i\cap A_j\mathrm{\mid }=\lfloor N\mathrm{/}\mathrm{l}\mathrm{c}\mathrm{m}(d_i,d_j)\rfloor$∣Ai​∩Aj​∣=⌊N/lcm(di​,dj​)⌋
   • Digit properties: Use Chinese Remainder Theorem for simultaneous congruences
3. Common pitfalls:
   • ❌ Forgetting higher-order intersections
   • ❌ Sign errors (should alternate $+-+-\cdots$+−+−⋯)
   • ❌ Confusing $\gcd$gcd with $\mathrm{l}\mathrm{c}\mathrm{m}$lcm in divisibility problems
4. Optimization techniques:
   • Symmetry: Group identical terms when sets are symmetric
   • Recurrence: Derangements satisfy $D_n=(n-1)(D_{n-1}+D_{n-2})$Dn​=(n−1)(Dn−1​+Dn−2​)

容斥原理（Inclusion-Exclusion Principle）

2.1 基本思想

当计算多个集合的并集元素个数时，直接相加会导致重复计数（重叠部分被多次计算）。容斥原理通过”加-减-加-减…”的交替方式修正重复，确保每个元素恰好被计数一次。

2.2 公式推导

两个集合：

$$\mathrm{\mid }A\cup B\mathrm{\mid }=\mathrm{\mid }A\mathrm{\mid }+\mathrm{\mid }B\mathrm{\mid }-\mathrm{\mid }A\cap B\mathrm{\mid }$$∣A∪B∣=∣A∣+∣B∣−∣A∩B∣

解释：先加 $\mathrm{\mid }A\mathrm{\mid }$∣A∣ 和 $\mathrm{\mid }B\mathrm{\mid }$∣B∣，但 $A\cap B$A∩B 被加了两次，需减去一次。

三个集合：

$$\begin{array}{rl}{\displaystyle \mathrm{\mid }A\cup B\cup C\mathrm{\mid }=}& {\displaystyle \mathrm{\mid }A\mathrm{\mid }+\mathrm{\mid }B\mathrm{\mid }+\mathrm{\mid }C\mathrm{\mid }}\\ {\displaystyle }& {\displaystyle -\mathrm{\mid }A\cap B\mathrm{\mid }-\mathrm{\mid }A\cap C\mathrm{\mid }-\mathrm{\mid }B\cap C\mathrm{\mid }}\\ {\displaystyle }& {\displaystyle +\mathrm{\mid }A\cap B\cap C\mathrm{\mid }}\end{array}$$∣A∪B∪C∣= ​∣A∣+∣B∣+∣C∣−∣A∩B∣−∣A∩C∣−∣B∩C∣+∣A∩B∩C∣​

解释：

1. 先加单个集合：$\mathrm{\mid }A\mathrm{\mid }+\mathrm{\mid }B\mathrm{\mid }+\mathrm{\mid }C\mathrm{\mid }$∣A∣+∣B∣+∣C∣
2. 减去两两交集（每对交集被多加一次）
3. 加回三重交集（在第2步中被多减了一次）

n个集合的一般形式：

$$\mid \bigcup _{i=1}^n{A}_i\mid =\sum _{k=1}^n(-1{)}^{k+1}(\sum _{1\le i_1<i_2<\cdots <i_k\le n}\mathrm{\mid }{A}_{i_1}\cap A_{i_2}\cap \cdots \cap A_{i_k}\mathrm{\mid })$$​i=1⋃n​Ai​​=k=1∑n​(−1)k+1(1≤i1​<i2​<⋯<ik​≤n∑​∣Ai1​​∩Ai2​​∩⋯∩Aik​​∣)

或等价地（补集形式，常用于”至少一个”问题）：

$$\mid \bigcap _{i=1}^n\overline{A_i}\mid =\mathrm{\mid }U\mathrm{\mid }-\sum \mathrm{\mid }{A}_i\mathrm{\mid }+\sum \mathrm{\mid }{A}_i\cap A_j\mathrm{\mid }-\sum \mathrm{\mid }{A}_i\cap A_j\cap A_k\mathrm{\mid }+\cdots +(-1{)}^n\mathrm{\mid }{A}_1\cap \cdots \cap A_n\mathrm{\mid }$$​i=1⋂n​Ai​​​=∣U∣−∑∣Ai​∣+∑∣Ai​∩Aj​∣−∑∣Ai​∩Aj​∩Ak​∣+⋯+(−1)n∣A1​∩⋯∩An​∣

2.3 容斥原理的组合解释

考虑一个元素 $x$x 属于 $m$m 个集合（$1\le m\le n$1≤m≤n），它在容斥公式中的总贡献为：

$$\left(\genfrac{}{}{0px}{}{m}{1}\right)-\left(\genfrac{}{}{0px}{}{m}{2}\right)+\left(\genfrac{}{}{0px}{}{m}{3}\right)-\cdots +(-1{)}^{m+1}\left(\genfrac{}{}{0px}{}{m}{m}\right)=1$$(1m​)−(2m​)+(3m​)−⋯+(−1)m+1(mm​)=1

由二项式定理 $(1-1{)}^m=0$(1−1)m=0 可证，确保每个元素恰好被计数一次。

---

三、典型例题详解

例题1：基础两集合问题

某班40名学生，25人喜欢数学，20人喜欢物理，10人两科都喜欢。问：至少喜欢一科的学生有多少人？两科都不喜欢的有多少人？

解：

• 设 $M$M = 喜欢数学的学生集合，$P$P = 喜欢物理的学生集合
• $\mathrm{\mid }M\mathrm{\mid }=25,\mathrm{\mid }P\mathrm{\mid }=20,\mathrm{\mid }M\cap P\mathrm{\mid }=10$∣M∣=25, ∣P∣=20, ∣M∩P∣=10
• 至少喜欢一科：$\mathrm{\mid }M\cup P\mathrm{\mid }=25+20-10=35$∣M∪P∣=25+20−10=35
• 两科都不喜欢：$40-35=5$40−35=5 人

例题2：三集合问题（经典竞赛题）

1~1000中，能被2、3、5整除的数各有多少？能被其中至少一个整除的数有多少个？

解：

• 设 $A=\{x\mid 2\mathrm{\mid }x\},B=\{x\mid 3\mathrm{\mid }x\},C=\{x\mid 5\mathrm{\mid }x\}$A={x∣2∣x}, B={x∣3∣x}, C={x∣5∣x}
• $\mathrm{\mid }A\mathrm{\mid }=\lfloor 1000\mathrm{/}2\rfloor =500$∣A∣=⌊1000/2⌋=500
• $\mathrm{\mid }B\mathrm{\mid }=\lfloor 1000\mathrm{/}3\rfloor =333$∣B∣=⌊1000/3⌋=333
• $\mathrm{\mid }C\mathrm{\mid }=\lfloor 1000\mathrm{/}5\rfloor =200$∣C∣=⌊1000/5⌋=200
• 两两交集：
  • $\mathrm{\mid }A\cap B\mathrm{\mid }=\lfloor 1000\mathrm{/}6\rfloor =166$∣A∩B∣=⌊1000/6⌋=166 （LCM(2,3)=6）
  • $\mathrm{\mid }A\cap C\mathrm{\mid }=\lfloor 1000\mathrm{/}10\rfloor =100$∣A∩C∣=⌊1000/10⌋=100 （LCM(2,5)=10）
  • $\mathrm{\mid }B\cap C\mathrm{\mid }=\lfloor 1000\mathrm{/}15\rfloor =66$∣B∩C∣=⌊1000/15⌋=66 （LCM(3,5)=15）
• 三重交集：$\mathrm{\mid }A\cap B\cap C\mathrm{\mid }=\lfloor 1000\mathrm{/}30\rfloor =33$∣A∩B∩C∣=⌊1000/30⌋=33 （LCM(2,3,5)=30）
• 至少被一个整除：$$\begin{array}{rl}{\displaystyle \mathrm{\mid }A\cup B\cup C\mathrm{\mid }}& {\displaystyle =500+333+200-166-100-66+33}\\ {\displaystyle }& {\displaystyle =734}\end{array}$$∣A∪B∪C∣​=500+333+200−166−100−66+33=734​
• 都不被整除：$1000-734=266$1000−734=266 个

例题3：非平方非立方数计数（高阶应用）

求1~10000中，既不是完全平方数也不是完全立方数的整数个数。

解：

• 全集 $U=\{1,2,\dots ,10000\},\mathrm{\mid }U\mathrm{\mid }=10000$U={1,2,…,10000}, ∣U∣=10000
• $A$A = 平方数集合：$\mathrm{\mid }A\mathrm{\mid }=\lfloor \sqrt{10000}\rfloor =100$∣A∣=⌊10000​⌋=100（因为 ${100}^2=10000$1002=10000）
• $B$B = 立方数集合：$\mathrm{\mid }B\mathrm{\mid }=\lfloor \sqrt[3]{10000}\rfloor =21$∣B∣=⌊310000​⌋=21（因为 ${21}^3=9261,{22}^3=10648>10000$213=9261, 223=10648>10000）
• $A\cap B$A∩B = 既是平方又是立方 = 六次方数：$$\mathrm{\mid }A\cap B\mathrm{\mid }=\lfloor \sqrt[6]{10000}\rfloor =\lfloor {10000}^{1\mathrm{/}6}\rfloor =4(\text{因为 }{4}^6=4096,5^6=15625>10000)$$∣A∩B∣=⌊610000​⌋=⌊100001/6⌋=4(因为 46=4096, 56=15625>10000)
• 既非平方也非立方：$$\mathrm{\mid }\bar{A}\cap \bar{B}\mathrm{\mid }=\mathrm{\mid }U\mathrm{\mid }-\mathrm{\mid }A\mathrm{\mid }-\mathrm{\mid }B\mathrm{\mid }+\mathrm{\mid }A\cap B\mathrm{\mid }=10000-100-21+4=9883$$∣A∩B∣=∣U∣−∣A∣−∣B∣+∣A∩B∣=10000−100−21+4=9883

例题4：错位排列（Derangement）— 容斥原理的经典应用

5封信装入5个信封，每封信都不装入对应编号的信封，有多少种装法？

解：

• 设全排列总数 $5!=120$5!=120
• 定义 $A_i$Ai​ = 第 $i$i 封信装对的排列集合（$i=1,2,3,4,5$i=1,2,3,4,5）
• 目标：求 $\mathrm{\mid }\overline{A_1}\cap \overline{A_2}\cap \cdots \cap \overline{A_5}\mathrm{\mid }$∣A1​​∩A2​​∩⋯∩A5​​∣
• 由容斥原理：$$\begin{array}{rl}{\displaystyle D_5}& {\displaystyle =5!-\left(\genfrac{}{}{0px}{}{5}{1}\right)4!+\left(\genfrac{}{}{0px}{}{5}{2}\right)3!-\left(\genfrac{}{}{0px}{}{5}{3}\right)2!+\left(\genfrac{}{}{0px}{}{5}{4}\right)1!-\left(\genfrac{}{}{0px}{}{5}{5}\right)0!}\\ {\displaystyle }& {\displaystyle =120-5\cdot 24+10\cdot 6-10\cdot 2+5\cdot 1-1}\\ {\displaystyle }& {\displaystyle =120-120+60-20+5-1=44}\end{array}$$D5​​=5!−(15​)4!+(25​)3!−(35​)2!+(45​)1!−(55​)0!=120−5⋅24+10⋅6−10⋅2+5⋅1−1=120−120+60−20+5−1=44​
• 一般公式（错位排列数 $D_n$Dn​）：$$D_n=n!\sum _{k=0}^n\frac{(-1{)}^k}{k!}=\lfloor \frac{n!}{e}+\frac{1}{2}\rfloor$$Dn​=n!k=0∑n​k!(−1)k​=⌊en!​+21​⌋

例题5：竞赛真题（CMO风格）

从1~2021中选取若干个数，使得任意两个数的差不等于4或7。最多能选多少个数？

解（模11分类 + 容斥思想）：

• 观察：若 $a-b=4$a−b=4 或 $7$7，则 $a\equiv b+4(\mathrm{m}\mathrm{o}\mathrm{d}11)$a≡b+4(mod11) 或 $a\equiv b+7(\mathrm{m}\mathrm{o}\mathrm{d}11)$a≡b+7(mod11)
• 将1~2021按模11分为11类：$R_0,R_1,\dots ,R_{10}$R0​,R1​,…,R10​
• 每类中任意两数差为11的倍数，不会等于4或7
• 但不同类之间可能冲突：若选 $R_i$Ri​，则不能选 $R_{i+4}$Ri+4​ 和 $R_{i+7}$Ri+7​（模11）
• 构造图：11个顶点，边连接冲突的类（$i\leftrightarrow i+4,i\leftrightarrow i+7$i↔i+4, i↔i+7）
• 该图是11-圈（因为4和7互为模11的补数：$4+7\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}11)$4+7≡0(mod11)）
• 问题转化为：在11-圈中选最大独立集 → 最多选5个不相邻顶点
• 每类大小：$\lfloor 2021\mathrm{/}11\rfloor =183$⌊2021/11⌋=183，余数 $2021<mrow\; style="margin:\; 0px;\; padding:\; 0px;\; box-sizing:\; border-box;\; border-width:\; 0px;\; border-style:\; solid;\; border-color:\; currentcolor;\; font-family:\; KaTeX\_Main,\; "Times\; New\; Roman",\; serif\; !important;"><mi\; mathvariant="normal"\; style="margin:\; 0px;\; padding:\; 0px;\; box-sizing:\; border-box;\; border-width:\; 0px;\; border-style:\; solid;\; border-color:\; currentcolor;\; font-family:\; KaTeX\_Main,\; "Times\; New\; Roman",\; serif\; !important;">m</mi><mi\; mathvariant="normal"\; style="margin:\; 0px;\; padding:\; 0px;\; box-sizing:\; border-box;\; border-width:\; 0px;\; border-style:\; solid;\; border-color:\; currentcolor;\; font-family:\; KaTeX\_Main,\; "Times\; New\; Roman",\; serif\; !important;">o</mi><mi\; mathvariant="normal"\; style="margin:\; 0px;\; padding:\; 0px;\; box-sizing:\; border-box;\; border-width:\; 0px;\; border-style:\; solid;\; border-color:\; currentcolor;\; font-family:\; KaTeX\_Main,\; "Times\; New\; Roman",\; serif\; !important;">d</mi></mrow>11=8$2021mod11=8，前8类多1个元素
• 最优选择：选5个类，优先选前8类中的5个
• 最大数量：$5\times 184=920$5×184=920（若5个类都在前8类）或 $4\times 184+183=919$4×184+183=919
• 答案：920

---

四、解题技巧与注意事项

1. 识别容斥场景：
   • “至少一个” → 用并集 $\mathrm{\mid }{A}_1\cup \cdots \cup A_n\mathrm{\mid }$∣A1​∪⋯∪An​∣
   • “都不” → 用补集交集 $\mathrm{\mid }\overline{A_1}\cap \cdots \cap \overline{A_n}\mathrm{\mid }$∣A1​​∩⋯∩An​​∣
   • “恰好k个” → 先算”至少k个”，再减去”至少k+1个”
2. 交集计算技巧：
   • 整除问题：$\mathrm{\mid }{A}_i\cap A_j\mathrm{\mid }=\lfloor N\mathrm{/}\mathrm{l}\mathrm{c}\mathrm{m}(d_i,d_j)\rfloor$∣Ai​∩Aj​∣=⌊N/lcm(di​,dj​)⌋
   • 数字特征：利用中国剩余定理求同时满足多个同余条件的数
3. 避免常见错误：
   • ❌ 忘记加回高阶交集（如三集合问题漏加 $\mathrm{\mid }A\cap B\cap C\mathrm{\mid }$∣A∩B∩C∣）
   • ❌ 符号错误（应为 $+-+-\cdots$+−+−⋯ 交替）
   • ❌ 交集计算错误（如误用 $\gcd$gcd 代替 $\mathrm{l}\mathrm{c}\mathrm{m}$lcm）
4. 优化计算：
   • 对称性：若集合对称，可合并同类项
   • 递推：错位排列可用 $D_n=(n-1)(D_{n-1}+D_{n-2})$Dn​=(n−1)(Dn−1​+Dn−2​)

===========

例题 1（基础）
题目：1..100 中有多少个整数能被 2 或 3 整除？
解答：设 $A=\{ \text{可被2整除}\}, B=\{\text{可被3整除}\}$A={可被2整除},B={可被3整除}。
$|A|=\lfloor100/2\rfloor=50$∣A∣=⌊100/2⌋=50, $|B|=\lfloor100/3\rfloor=33$∣B∣=⌊100/3⌋=33, $|A\cap B|=\lfloor100/6\rfloor=16$∣A∩B∣=⌊100/6⌋=16.
所以 $|A\cup B| = 50+33-16 = 67$∣A∪B∣=50+33−16=67。
技巧：先求单条件，再减去重复计数。（计算每步按向下取整）

例题 2（常见三集合）
题目：1..100 中可被 2、3、5 中任一数整除的整数有多少？
解答：单项：50,33,20；两两：$\lfloor100/6\rfloor=16,\ \lfloor100/10\rfloor=10,\ \lfloor100/15\rfloor=6$⌊100/6⌋=16, ⌊100/10⌋=10, ⌊100/15⌋=6。三重：$\lfloor100/30\rfloor=3$⌊100/30⌋=3。
按三集合公式：$50+33+20-(16+10+6)+3=74$50+33+20−(16+10+6)+3=74。
补集（不被2,3,5任何一个整除）的数：$100-74=26$100−74=26。

例题 3（排斥原理计算“没有固定点”的排列 — 错排/Derangement）
题目：4 个不同物件的排列中，没有任何物件在原位的排列数（!4）是多少？
解答（容斥）：$$!n = n! \sum_{k=0}^n \frac{(-1)^k}{k!}.$$!n=n!k=0∑n​k!(−1)k​.

代入 $n=4$n=4：
$!4 = 4!\left(1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+\frac{1}{4!}\right) =24\left(0+\tfrac12-\tfrac16+\tfrac{1}{24}\right)=9.$!4=4!(1−1!1​+2!1​−3!1​+4!1​)=24(0+21​−61​+241​)=9.
技巧：把“固定点”视为集合 $A_i$Ai​（第 i 个元素处在原位），求没有固定点即全集减去任何固定点的并集。

例题 4（满射 / onto 函数计数）
题目：把 5 个不同元素放入 3 个标签不同的盒子，使每个盒子至少有一个元素，方法数？
解答（容斥）：总函数数 $3^5$35。减去至少有 1 个盒子空的情况，用 PIE：
答案 = $3^5 – \binom{3}{1}2^5 + \binom{3}{2}1^5 = 243 – 3\cdot32 + 3\cdot1 = 150.$35−(13​)25+(23​)15=243−3⋅32+3⋅1=150.
技巧：把“某些盒子空”当作集合条件来排斥。

例题 5（人数-属性交叉）
题目：在某班有 40 人，20 人会 A，18 人会 B，15 人会 C；会 A 和 B 的有 8 人，会 A 和 C 的有 6 人，会 B 和 C 的有 5 人，三种都会的有 2 人。问至少会一种语言的人数。
解答：用三集合公式：$20+18+15-(8+6+5)+2=36$20+18+15−(8+6+5)+2=36。

例题 6（复杂：条件并列）
题目：一个班级的学生参加数学、物理、化学竞赛，给出部分两两三重交集数量（略），求至少参加两项的人数（由单项与交集数据求取）。
解法提示：设按属于集合的个数分层：至少两项 = $\sum_{x: \text{属于至少两集合}}1$∑x:属于至少两集合​1；用 $|A\cap B|+|A\cap C|+|B\cap C| – 3|A\cap B\cap C|$∣A∩B∣+∣A∩C∣+∣B∩C∣−3∣A∩B∩C∣（注意重复计数的校正）。详细步骤见下方示例演算（如果你需要我可以把一个具体数值的实例展开）。

例题 7（抽屉/鸽巢原理与容斥混合）
题目：若 10 个球放入 3 个盒子，至少有一个盒子包含至少 4 个球吗？（直接用鸽巢）
解答：此题主用鸽巢原理（非容斥），但在某些限制条件下可与容斥联合使用以排除不合法分配。提示：鸽巢原理常与集合计数组合出现。

例题 8（计数证明题 — 使用指示函数）
题目/任务：证明容斥一般公式（使用指示函数或归纳）。
解法要点：给定元素 $x$x，设它属于 $t$t 个集合。计算右侧在 $x$x 上的贡献：$\sum_{k=1}^{t} (-1)^{k-1}\binom{t}{k}=1$∑k=1t​(−1)k−1(kt​)=1。对不属于任何集合的元素贡献为 0，从而完成证明。