系统分析师-数学与经济管理-容斥原理与鸽巢原理PPT讲义

第三章 容斥原理和鸽巢原理
§1 容斥原理引论

例 [1，20]中2或3的倍数的个数
[解] 2的倍数是：2，4，6，8，10，
12，14，16，18，20。 10个

3的倍数是：3，6，9，12，15，
18。 6个
但答案不是10+6=16 个，因为6，
12，18在两类中重复计数，应减
去。故答案是：16-3=13

容斥原理研究有限集合的交或并
的计数。
[DeMorgan定理] 论域U，补集