浅谈容斥原理

容斥原理

定理:

设有 $n$ 个集合,第 $i$ 个集合为 $A_i$,则所有集合的并集可以表示成如下形式:
$$
|A_1\cup A_2\cup \cdots\cup A_n|=\sum_{i=1}^n (-1)^{i-1}\sum|A_1\cap A_2\cap\cdots\cap A_i|
$$

证明:

假设元素 $a$​ 被 $x$​ 个集合包含,显然左式中该元素的贡献为 $1$,因为在并集内一个元素仅计算一次。

考虑其对于右式的贡献,显然它会被这个 $x$ 个集合中所有子集中被计算到,其贡献为:
$$
\sum_{i=1}^xC_x^i(-1)^{i-1}=1-\sum_{i=0}^xC_x^i(-1)^i=1
$$
由于所有元素对于左右两式的贡献均为 $1$,综上即可证得等式成立。

应用

容斥系数一般为 $(-1)^{|S|}$。

容斥的一些模型:

  1. 所有情况 $-$ 至少有一个 $+$ 至少有两个 $-\dots = $ 一个都没
  2. 全部都有 $-$ 一个也没 $=$ 至少有一个
  3. 至少有 $k$ 个 $- C_{k+1}^k \times $ 至少有 $k+1$ 个 $+ C_{k+2}^k\times $ 至少有 $k+2$ 个 $\dots = $ 恰好有 $k$ 个
  4. 补集转化
  5. $\min-\max$​ 容斥
  6. 容斥原理

评论

  1. too_late
    Windows Chrome 89.0.4389.90
    1月前
    2021-8-18 6:43:51

    真的挺浅的……

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇