鸽巢原理

如果用 n 个鸽巢容纳 n+1 或更多只鸽子，那么至少有一个鸽巢容纳了不止一只鸽子。 广义的鸽巢原理是：- 如果用 n 个鸽巢容纳 kn+1 或更多只鸽子，其中 k 是一个正整数，那么至少有一个鸽巢容纳了 k+1 或更多只鸽子。

例1： 确定一个班级中至少有多少名学生，才能确保其中有三名学生是同月出生的。

解： 这里 n = 12 个月是鸽巢
                    而且 k + 1 = 3
                    K = 2

例2： 证明如果在一个房间里聚集了13个人，那么至少有两个人必须在同一个月过生日。

解： 我们将每个人分配到他出生的那个月的年份。 由于一年有 12 个月。

因此，根据鸽巢原理，必须至少有两个人被分配到同一个月。

容斥原理

设 A₁,A₂......A_r 是全集 U 的子集。 那么 U 的任何子集 A₁,A₂......A_r 中未出现的元素数量 m。

例： 设 U 为不超过 1000 的正整数集合。那么 |U|= 1000 求 |S|，其中 S 是不被 3、5 或 7 整除的整数集合？

解： 设 A 为可被 3 整除的整数子集
                设 B 为可被 5 整除的整数子集
                设 C 为可被 7 整除的整数子集

则 S = A^c ∩ B^c∩ C^c ，因为 S 的每个元素都不能被 3、5 或 7 整除。

根据整数除法，

          |A|= 1000/3 = 333
          |B|= 1000/5 = 200
          |C| = 1000/7 = 142
          |A∩B|=1000/15=66
          |B∩C|=1000/21=47
          |C∩A|=1000/35=28
          |A∩B∩C|=1000/105=9

因此，根据包含-排除原理

          |S|=1000-(333+200+142)+(66+47+28)-9
          |S|=1000-675+141-9=457