包除原理

ある事象の場合の数を直接数えにくい場合に、より小さくてシンプルな数え上げに分割して解く問題分割。部分事象が排反である時は単なる足し算だが、そうでなくても、共通部分が求められるなら包除原理が使える。

$|A\cup B|=|A|+|B|-|A\cap B|$

• https://ja.wikipedia.org/wiki/包除原理

バイナリ素性の組み合わせで表現するという解釈もできる。

• 000を求めたいが直接求めることが困難である時に、*** - (1** + 1 + 1) + (11 + 11 + *11) - (111) を計算する
• 特に1の個数kによって集合のサイズf(k)が決まる場合
  • ${\sum }_k-1^k\left(\genfrac{}{}{0ex}{}{n}{k}\right)f(k)$
• https://twitter.com/opt_cp/status/1298569230439157762
• $|{\bigcap }_{i\in V}{A}_i|={\sum }_{S\subseteq V}(-1{)}^{|S|}|{\bigcap }_{i\in S}{A}_i^{\mathsf{c}}|$

• |A or B| = |A| + |B| - |A and B|と考えるのではなく|¬A and ¬B| = |U| - |A| - |B| + |A and B|と考えると楽 src ABC172E

  • $|A\cup B|=|A|+|B|-|A\cap B|$
  • $|A^{\mathsf{c}}\cap B^{\mathsf{c}}|=|U|-|A|-|B|+|A\cap B|$

• 事象にちゃんと名前をつけて式変形をする・どの事象が簡単に計算できるかを意識する

  • 今回のN=3とした場合を考える．#()で事象の要素数を表すとする．

  • Pi = (Ai=Biとなる事象)として，求めたいのは#(¬P1 ∧ ¬P2 ∧ ¬P3)で，簡単に計算できるのは#(P1)とか#(P1 ∧ P2)とか．#(¬P1 ∧ ¬P2)とかは扱いにくいので，ドモルガンで#(¬(P1 ∨ P2 ∨ P3))に直して包除原理，と考えると簡単

  • https://twitter.com/oinori1197/status/1276894798209679360

包除原理 解ける数え上げの範囲を広げよう tsutaj

• https://compro.tsutaj.com//archive/181015_incexc.pdf
• 小さければ全探索
• 対称性によって組み合わせに帰着
  • O(2^N)がO(N)になる
• 部分集合それぞれについて包除原理を使うときO(3^N)
  • なぜ？ →部分集合の部分集合の数の和
  • これは重いI
  • 高速メビウス変換はこれをO(N2^N)にできる

関連

• 二項係数
• メビウス変換
• 完全順列
• https://twitter.com/sugarknri/status/1290212350696415233
• オイラー標数 https://twitter.com/kaitou_ryaku/status/1239816691523051520