排容原理

维基百科,自由的百科全书
跳转至: 导航搜索
三個集的情況

容斥原理又称排容原理,在組合數學裏,其說明若, ..., 有限集,則

其中表示基數。例如在兩個集的情況時,我們可以透過將相加,再減去其交集的基數,而得到其并集的基數。

概率论中的容斥原理[编辑]

概率论中,对于概率空间中的事件A1,……,An,当n = 2时容斥原理的公式为:

n = 3时,公式为:

一般地:

也可以写成:

对于一般的测度空间(S,Σ,μ)和有限测度的可测子集A1,……,An,上面的恒等式也成立,如果把概率测度换为测度μ

特殊情况[编辑]

如果在容斥原理的概率形式中,交集AI的概率只与I中元素的个数有关,也就是说,对于{1, ..., n}中的每一个k,都存在一个ak,使得:

,对于每一个

则以上的公式可以简化为:

这是由于二项式系数的组合解释。

类似地,如果对有限集合A1,……,An的并集的元素个数感兴趣,且对于{1, ..., n}中的每一个k,交集

的元素个数都相同,例如ak = |AI|,与{1, ..., n}的k元素子集I无关,则:

在一般的测度空间(S,Σ,μ)和有限测度的可测子集A1,……,An的情况中,也可以进行类似的简化。

容斥原理的证明[编辑]

欲证明容斥原理,我们首先要验证以下的关于指示函数的等式:

至少有两种方法来证明这个等式:

第一种方法 我们只需证明对于A1,……,An的并集中的每一个x,等式都成立。假设x正好属于m个集合(1 ≤ m ≤ n),不妨设它们为A1,……,Am。则x处的等式化为:

m元素集合中的k元素子集的个数,是二项式系数 的组合解释。由于 ,我们有:

把所有的项移到等式的左端,我们便得到(1 – 1)m的二项式展开式,因此可以看出,(*)对x成立。

第二种方法A表示集合A1,……,An的并集。于是:

这是因为对于不在A内的x,两边都等于零,而如果x属于其中一个集合,例如Am,则对应的第m个因子为零。把右端的乘积展开来,便可得到等式(*)。

其它形式[编辑]

有时容斥原理用以下的形式来表述:如果

那么:

在这种形式中可以看出,它是A的所有子集的偏序集合指标代数莫比乌斯反演公式

应用[编辑]

在许多情况下,容斥原理都可以给出精确的公式(特别是用埃拉托斯特尼筛法计算素数的个数时),但是用处不大,这是因为它里面含有的项太多。即使每一个单独的项都可以准确地估计,误差累积起来仍然意味着容斥原理不能直接应用。在数论中,这个困难由维戈·布朗解决。开始时进展很慢,但他的想法逐渐被其他数学家所应用,于是便产生了许多各种各样的筛法。这些方法是尝试找出被“筛选”的集合的上界,而不是一个确切的公式。

乱序排列[编辑]

容斥原理的一个著名的应用,是计算一个有限集合的所有乱序排列的数目。一个集合A乱序排列,是从AA的没有不动点的双射。通过容斥原理,我们可以证明,如果A含有n个元素,则乱序排列的数目为[n! / e],其中[x]表示最接近x的整数。

这也称为n子阶乘,记为!n。可以推出,如果所有的双射都有相同的概率,则当n增大时,一个随机双射是乱序排列的概率迅速趋近于1/e

交集的计算[编辑]

容斥原理与德·摩根定理结合起来,也可以用于计算集合的交集中元素的数目。设表示Ak关于全集A补集,使得对于每一个k,都有。于是,我们有:

这样便把计算交集的问题化为计算并集的问题。

参见[编辑]

参考文献[编辑]

  • Klaus Dohmen: Improved Bonferroni Inequalities via Abstract Tubes - Inequalities and Identities of Inclusion-Exclusion Type, Springer-Verlag, 2003, ISBN 3-540-20025-8.
  • Stasys Jukna: Extremal Combinatorics, Springer, 2001, ISBN 3-540-66313-4.

本條目含有来自PlanetMathprinciple of inclusion-exclusion》的材料,版权遵守乃遵守知识共享协议:署名-相同方式共享协议