容斥原理

设S是一个有限集，a1,a2,……,an是n种性质

记N(ai)为S中有ai性质的元素的数量。特殊的，记N(1)=|S|。

记N(1-ai)为S中没有ai性质的元素的数量。

N(aj1,aj2,……,ajk)为S中同时有aj1,aj2,……,ajk性质的元素的数量

记N(a+b)=N(a)+N(b)  N(a-b)=N(a)-N(b)

则容斥原理可以写成：

当直接求一个问题不是特别容易的时候我们可以考虑他的对立面，然后利用容斥原理来求解，往往会使得问题变得简单。