Question

容斥原理

Answer 1

有限集的阶

设 为非空有限集,非空集合 是 的一个子集族 ,且满足 则称子集族 : 是集合 的一个覆盖.

如何通过计算覆盖 : 中每个子集的阶来计算有限集 的阶.

一、加法原理

如果子集族 既是集合 的一个覆盖,又满足

, ,

那么覆盖 就是有限集M的一个 分划.

加法原理

设 为非空有限集, 是 的一个由非空子集构成的 分划,那么

加法原理是组合数学中一个基本的计数原理.

二、容斥原理的简单形式

如果不一定满足 , ,也就是说可能存在 ,使 时, 与 有什么关系呢?

定理1 (I)

证明 设 , , ,则 .

由加法原理知, , ,所以

定理2 设 、 是集合 的子集,则 .

证明 由摩根定律及加法原理有 .

又由定理1得 .

三、容斥原理的一般形式

定理3 .

证明

由定理1知, 时结论成立.

若 时结论成立,则

.

即 时结论成立.

由归纳原理知,对任意正整数 ,结论成立.

摩根定律

及公式 ( 为全集)

定理4 设 为全集,则

又叫筛法公式,一般用来计算不具有某几个性质中的任何一个性质的元素的个数.