包除原理 - メモ

■いわゆる包除原理
$|\cup_{i\in S} A_i|=\sum_{\emptyset\neq T \subset S} (-1)^{|T|+1} |\cap_{i\in T}A_i|$
$|\cap_{i\in S} A_i|=\sum_{\emptyset\neq T \subset S} (-1)^{|T|+1} |\cup_{i\in T}A_i|$
N個の条件を全て満たすものの個数を求めてください→N個の条件いずれかに違反するものの個数を求めてください、と読み替えて包除しがち
2乗のDPになりがち

■min・max
$\max(S)=\sum_{\emptyset\neq T \subset S} (-1)^{|T|+1}\min(T)$
$\min(S)=\sum_{\emptyset\neq T \subset S} (-1)^{|T|+1}\max(T)$
期待値とかで使うらしい。ところでいわゆる包除原理とどういう関係にあるんですか？

■ゼータ変換・メビウス変換系（束上の累積和/imos・メビウスの反転公式）
累積和・imosは包除原理！（素振り）
・自然数の自然な大小関係に関する順序に対してやるやつ
・集合の包含関係に関する順序に対してやるやつ
・自然数の整除関係に関する順序に対してやるやつ
・分割の細分に関する順序に対してやるやつ

■逆行列を掛けるやつ
二項係数
$G(s) = \sum_{t=0}^s \binom{s}{t} F(t) \Longleftrightarrow F(s) = \sum_{t=0}^s (-1)^{s-t} \binom{s}{t} G(t)$
スターリング数
$G(s) = \sum_{t=0}^s {s \brace t} F(t) \Longleftrightarrow F(s) = \sum_{t=0}^s (-1)^{s-t} {s \brack t} G(t)$
$G(s) = \sum_{t=0}^s {s \brack t} F(t) \Longleftrightarrow F(s) = \sum_{t=0}^s (-1)^{s-t} {s \brace t} G(t)$
係数がs-tのみで決まるなら畳み込み逆元だがそうではないので……？
追記：
これって集合の包含関係に関する順序についての反転、分割の細分に関する順序についての反転らしい。
集合の包含関係に関する順序についての反転は
$G(S)=\sum_{T\subset S}F(T) \Longleftrightarrow F(S)=\sum_{T\subset S}(-1)^{|S|-|T|}G(T)$
で、もしここで $|S|=|T| \Longrightarrow F(S)=F(T)$ が成り立つなら、シグマの部分を $\sum_{t=0}^{|S|}\sum_{T\subset S, |T|=t}$ と分解するとさっきの式が出てくる。知らなかったそんなの……

■主客転倒
これ包除じゃなくない？　でもメビウス関数とかでてきたら実質包除だろ（ガバ判定）
・N以下のsquare-free numberの数え上げを $\sum_{d\leq \sqrt{N}}\lfloor\frac{N}{d^2}\rfloor\mu(d)$ でやるやつ
[x=1]を $(\zeta*\mu)(x)=\sum_{d|x}\mu(d)$ と読み替えるのが本質。（畳み込みはDirichlet convolution）
包除じゃなくない？
・累積和の変形
$\sum_{x\leq N}F(x)=\sum_{x \leq N}(\mu*F)(x)\lfloor\frac{N}{x}\rfloor$
（畳み込みはDirichlet convolution）
これは本当に主客転倒してるだけ。包除なんも関係ない