鸽巢原理

如果n个鸽子洞被n + 1个或更多鸽子占据, 则至少一个鸽子洞被一个以上的鸽子占据。广义信鸽原理是：-如果n个信鸽被kn + 1个或更多的鸽子占据, 其中k是一个正整数, 那么至少一个信鸽被k + 1个或更多的鸽子占据。

示例1：找出班级中最少的学生人数, 以确保其中三个人在同一个月内出生。

解决方案：这里n = 12个月是鸽子洞, k +1 = 3 K = 2

示例2：表明如果一个房间里有13个人, 那么至少两个人必须在同一个月内过生日。

解决方案：我们为每个人分配了他出生的月份。由于一年有12个月。

因此, 根据信鸽原则, 必须至少有两个人分配给同一个月。

包含-排除原则

令A1, A2 …… Ar为通用集U的子集。则元素的数量m不会出现在U的任何子集A1, A2 …… Ar中。

示例：设U为不超过1000的正整数集。然后| U | = 1000查找| S |。其中S是不能被3、5或7整除的整数的集合？

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

那么S = Ac∩Bc∩Cc, 因为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