2.计数问题

容斥原理与鸽笼原理

• 有穷集的计数（包含排斥原理）

  设 $S$ 是一个有穷集，$A,B,C$ 是 $S$ 的子集，则有：

  $|A\cup B|=|A|+|B|-|A\cap B|$

  $|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|$

  $|\overline{A}\cap \overline{B}\cap \overline{C}|=|S|-(|A|+|B|+|C|)+(|A\cap B|+|A\cap C|+|B\cap C|)-|A\cap B\cap C|$