包除の原理 The inclusion-exclusion principle



(-1)^kを係数とする包除の原理。どうして(-1)^kなんだろう。もちろん、そうだからそうなのだけれども、集合は2進法的な構造だからなんだろうか、とか、そういう意味で、どうしてなんだろう、と思う。

P(¥cup_{i=1}^nA_i)=¥sum_{i=1}^nP(A_i)-¥sum_{i<j}P(A_i¥cap P_j)

+¥sum_{i<j<k}P(A_i¥cap A_j ¥cap A_k)- ... +(-1)^{n+1}P(A_1¥cap A_2 ¥cap ... ¥cap A_n)