容斥原理

容斥原理

容斥原理用于计算若干有限集合并集中的元素个数。对于两个集合： |A ∪ B| = |A| + |B| − |A ∩ B|；推广到三个集合时，奇数项相加、偶数项相减， 即 |A ∪ B ∪ C| = |A| + |B| + |C| − |A∩B| − |A∩C| − |B∩C| + |A∩B∩C|。 下方可按步骤查看每一项对总数的贡献。