容斥问题公式是什么?


容斥问题公式是什么?

文章插图
容斥问题3个公式如下:
1、标准型: |A∪B∪C | = | A | + | B | + | C | - | A∩B | - | B∩C | - | C∩A | + | A∩B∩C | 。
2、非标准型:|A∪B∪C | = | A | + | B | + | C | -只满足两个条件的- 2×三个都满足的 。
3、列方程组:|A∪B∪C | =只满足一个条件的+只满足两个条件的+三个都满足的 。
三集合公式:
1、总数=满足条件A+满足条件B+满足条件C-满足条件AB-满足条件AC-满足条件BC+条件ABC都满足+条件ABC都不满足 。
2、总数=满足条件A+满足条件B+满足条件C-满足两个条件-2×三个条件都满足+三个条件都不满足 。
3、总数=满足一个条件+满足两个条件+三个条件都满足+三个条件都不满足 。
容斥公式:A∪B=A+B-A∩B 。先不考虑重叠的情况,把包含于某内容中的所有对象的数目先计算出来,然后再把计数时重复计算的数目排斥出去,使得计算的结果既无遗漏又无重复,这种计数的方法称为容斥原理 。
【容斥问题公式是什么?】对于容斥原理我们可以利用数学归纳法证明,数学归纳法是一种数学证明方法,通常被用于证明某个给定命题在整个自然数范围内成立 。除了自然数以外,广义上的数学归纳法也可以用于证明一般良基结构 。这种广义的数学归纳法应用于数学逻辑和计算机科学领域,称作结构归纳法 。

    推荐阅读