2011_排列组合(19)

排列组合

p19

排容原理

[说明]

「排容原理」是计数原理的第一步，通常我们会直接下去求我们所要得到的答案，但如果元素彼此之间有关连的时候，那我们就还得再考虑它们之间的关连有没有影响到我们得到的答案。而排容原理就是建立在这一个情形下的计数原理。现在就让我们考虑下面的问题：

问题一：试问 1 至 120 中，4 或 6 的倍数有几个？

要解这一个问题，我们首先求出 1 至 120 中 4 的倍数之个数，易知其共4

120 =30个。其次我们再求出6的倍数之个数，共有 6

120 =20个将4的倍数之个数和 6 的倍数之个数加起来即 30 + 20 = 50 个，但此时我们将同时是 4 及 6 的倍数之个数算了两次，因此必须将他们减掉，而在 1 至 120 中，同时为 4 跟 6 的倍数的数即为 12 的倍数，故共有

12

120=10个。因此，4 或 6 的倍数之个数为30+20-10=40个。

若令为 1 至 120 中 4 的倍数之集合，为 1 至 120 中 6 的倍数之集合，则A ∩B 是 12 倍数之集合，A ∪B 为 4 或 6 的倍数之集合，从上面的问题讨论中，我们可以得知 ∣A ∪B ∣=∣A ∣+∣B ∣－∣A ∩B ∣。我们也可以以下面的图形来说明，其中圆

表 4 的倍数的集合，圆表 6 的倍数的集合，而重迭的部分就是 12 的倍数的集合。

事实上，对任意的有限集合及中， ∣A ∪B ∣=∣A ∣+∣B ∣－∣A ∩B ∣仍成立，因为要计算属于或的元素个数，即∣A ∪B ∣，我们可先将集合及的元素个数加起来，及∣A ∣+∣B ∣，但此时既是也是的元素即，我们总共算了两次，所以必须再减掉，因此我们得到 ∣A ∪B ∣=∣A ∣+∣B ∣－∣A ∩B ∣这个式子。