包除・Möbius反転で重複を補正する

概要

集合上の包除原理

条件集合の交差をsubsetごとに数え、交互符号で「少なくとも一つ」「全てを避ける」対象を重複なく数える。

考え方

禁止事象のunionを直接数えにくいとき、複数事象を同時に満たす交わりを交互符号で足す。ある対象がk事象に入るならΣ_{j=1}^k(−1)^(j+1)C(k,j)=1となり重複が補正される。

全体集合Uと禁止事象A_0,…,A_(m−1)を定義し、I(S)=|∩_{i∈S}A_i|、I(空集合)=|U|と置く。「全てを避ける」個数はΣ_{S⊆[m]}(−1)^|S| I(S)。「少なくとも一つを満たす」個数は空集合を除いてΣ_{S≠空集合}(−1)^(|S|+1) I(S)である。禁止条件を一つも満たさない対象は前者へ一回寄与し、k>0個満たす対象の係数はΣ_{j=0}^k(−1)^j C(k,j)=(1−1)^k=0。対象ごとの係数を調べると符号と空集合の意味を確認できる。

実装はm条件の選択maskを0から2^m−1まで列挙し、同時に満たす対象数I(mask)を計算して、popcountが偶数なら加算、奇数なら減算する。I(mask)の計算が本体であり、元の対象を列挙できなくても連立条件・共通の許可文字・固定要素数などから求められるかを考える。集合がbitmaskで明示されるなら、全体集合から選択した条件のANDを取る手順を有界全列挙で使う。整数maskの大小をそのまま集合の包含関係と解釈しない。

成立条件と計算量

m事象の素朴法は2^m個の交わり評価。対称性や同じ交わりをまとめられる場合だけ圧縮できる。空の選択の寄与と禁止事象の定義を固定し、modの減算を正規化する。

下位単元

問題一覧

各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。

関連問題

前提・学習成果・出典

習得対象の目安: 水色(1200–1599)。条件の共通部分を数え、交互符号が重複を打ち消す理由を説明する。

対象色の読み方は本書の読み方を参照してください。

概念上の親: 組合せ・多項式・線形代数。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-inclusion-exclusion

習得する技能

  • 条件集合の重なり構造を特定し、包除またはMöbius反転の符号と範囲を正しく設定できる。

前提と範囲

共通前提: prereq-abc-advanced-v1 (1.0.0)。

直接の前提単元: なし。

このUnitを直接前提とする単元: subset zeta・Möbius変換。

単純に足すと重複する条件を交差構造ごとに補正し、包除・Möbius反転へ一般化する。

このUnitでは扱わないもの

  • 選択順を二項係数だけで式化する数え上げ。

根拠