容斥原理
[igcup_{i = 1} ^ n A_i = sum_{k = 1} ^ n (-1)^{k + 1} egin{pmatrix} sumlimits_{1 leq i_1 < i_2< ... <i_k leq n} |A_{i_1} cap ... A_{i_k}|end{pmatrix}
]
证明
考虑每个元素对集合的贡献
元素 (i in A_{k_1}, A_{k_2}, A_{k_3}..., (sum A_i = k))
对于出现在 (m) 个集合内的情况 (i) 的系数 (= inom k m * (-1) ^ {m + 1})
(i) 的系数 (= sum_{i = 1} ^ k inom k i (-1) ^ {i + 1})
[(x + (-1))^k = sum_{i = 0} ^ k inom k i (-1) ^ i x
]
当 (x = 1) 时
[sum_{i = 1} ^ k inom k i (-1) ^ {i + 1} = -1 * (1 - 1)^k + inom k 0 = 1
]
所以每个元素最终的系数都是1
证毕