【数学归纳法 组合数学】容斥原理

问题提出

有n个条件，要求不重复统计满足一到n个条件的所有可能数。

容斥原理

要计算几个集合并集的大小，我们要先将所有单个集合的大小计算出来，然后减去所有两个集合相交的部分，再加回所有三个集合相交的部分，再减去所有四个集合相交的部分，依此类推，一直计算到所有集合相交的部分。

cnt[m] 记录所有 满足m个条件的可能数。

下面来证明：

其本质是：集合求并。

贡献法

相关知识点

帕斯卡法则

分别对应n选择m的两种情况：

第一个物品没选择 和第一个物品选择。

二项式定理

二项式定理（英语：binomial theorem），又称牛顿二项式定理。

下面用数学归纳法证明。

当n=1是

下面来证明n=m成立，则n=m+1也成立。

测试环境

操作系统：win7 开发环境： VS2019 C++17

或者 操作系统：win10 开发环境： VS2022 C++17

如无特殊说明，本算法用**C++**实现。