正文

集合A = { 1 , 2 , . . . , n } 它含有n 个元素，可以说这个集合的基数是n ，记做

所谓基数，是表示集合中所含元素多少的量。如果A 的基数是n ，也可以记做∣ A ∣ = n，显然空集的基数是0 ，即∣ ∅ ∣ = 0

文氏图

设AA为集合，若存在自然数n ，使得 则称A 为又穷集，否则称A为无穷集

例如，{ a , b , c 为又穷集，而N , Z , Q ,为无穷集。其中有穷集的计数问题可以使用文氏图很方便地解决。

容斥定理(包含排斥定理)

设S 是有穷集，p 1 , p 2分别代表两种性质，对于S 中的任何一个元素s ，只能处于以下4种情况之一：

只具有性质p 1

只具有性质p 2

同时具有性质p 1 , p 2

不具有性质p 1 , p 2 中的任何一种

令P 1 , P 2 分别表示S中具有性质p 1 , p 2  的元素的集合，可以得到：

这便是容斥定理的一种简单形式

如果涉及三条性质，则包含排斥原理的公式变为：

以此类推，可以得到容斥定理的一般形式：

容斥定理表示S中不具有性质p 1 , p 2 , . . . , p m 的元素数量为

因此，与之对应的，在S 中至少具有p 1 , p 2 , . . . , p m 其中一条性质的元素数量为:

即：