首页 > 其他分享 >容斥原理

容斥原理

时间:2023-02-27 16:00:30浏览次数:30  
标签:limits mathscr sum 容斥 倍数 集合 原理 empty

容斥原理

在1到100的整数中,我们想数出“既不是2的倍数,也不是3的倍数,也不是5的倍数”的数的个数。我们发现,我们很容易数出2的倍数的个数、3的倍数的个数、5的倍数的个数,但是由于这些个数之间有重叠,所以如果把100减去这些个数的总和,就多减了一点。为了弥补多减的部分,我们依次把同时是2和3的倍数的、同时是2和5的倍数的、同时是3和5的倍数的给加回来。但接着又发现加回来的太多了。如果这时我们再把同时是2、3、5的倍数的数的个数给减掉,就恰好得到了正确的答案。

以上这个过程可以在韦恩图上比较清晰的表达出来。把这个问题描述的对象抽象出来,我们发现我们在解决这样一个问题:我们的元素有一些性质,我们想要统计“不满足所有这些性质”的元素个数,但是这不容易计算。然而,“满足”其中几条性质的元素个数却是容易计算的。为了叙述方便,由于我们想要求出的是所有性质都不满足的元素,所以满足某条性质就是件“坏事”。所有满足某条性质的元素的集合就是一个“坏集合”。相反,所有性质都不满足的元素就是“好的”。坏集合以及坏集合的交是容易计算的。我们想要通过一种方法把各种坏集合的交集加加减减来求出好集合的大小,这就是容斥原理。

在给定的一个大集合\(U\)中,设坏集合为\(A_1,\cdots,A_m\)。已知\(|\bigcap\limits_{i=1}^{k}A_{p_i}|\)是容易计算的。目标就是计算出\(|\bigcap\limits_{i=1}^{m} \bar{A_i}|\)。

为了方便理解,我们引入记号。把坏集合的集合记为\(\mathscr{A}=\{A_1,\cdots,A_m\}\)。设\(J\)是\(\mathscr{A}\)的一个子集,即\(J\)是某几个坏集合组成的集合。定义

\(N_=(J)=|\{x \in U | \forall A_i \in J, x \in A_i 且 \forall A_i \in \mathscr{A} \backslash J, x \notin A_i\}|\)

即\(N_=(J)\)表示全集和所有\(J\)中坏集合的交集,抠掉所有的剩下坏集合里的元素。比如在刚才的例子中,\(N_=(\{2,5\})\)就表示所有又是2的倍数又是5的倍数,但不是3的倍数的数。注意到,\(N_=(\empty)\)就表示不在任何坏集合里的元素,也就是“好元素”,就是我们要的答案。

\(N_=(J)\)往往是难求的。而根据我们的设定,\(N_\geq (J)=|\{x \in U | \forall A_i \in J, x \in A_i\}|\),即全集和\(J\)中的坏集合的交集,是容易求出的。其中\(N_\geq(\empty)=U\)。

容斥原理就是指出:

\(N_=(\emptyset) = \sum\limits_{J\subseteq \mathscr{A}} (-1)^{|J|}N_\ge(J)\)

根据定义,等式左侧即为\(|\bigcap\limits_{i=1}^{m} \bar{A_i}|\),而右侧可以改写为\(\sum\limits_{j=0}^m (-1)^j \sum\limits_{J\in\binom{\mathscr{A}}{j}} N_\ge(J)\)。我们考虑每个元素的贡献。如果\(x \in N_=(\empty)\),将在左侧贡献1。这意味着\(x\)不属于任何坏集合,因此它在右侧只会在\(j=0\)时(即\(J=\empty\))时被统计到,刚好在\(N_\geq(\empty)\)中贡献1次;如果\(x \notin N_=(\empty)\),那么左侧贡献0。\(x\)出现在了某个或某几个坏集合中,不妨设出现在\(A_{i_1},\cdots,A_{i_t}\)中,那么当且仅当\(J \subseteq \{A_{i_1},\cdots,A_{i_t}\}\)时(包括空集)右侧才会贡献,总的贡献恰好为\(\sum\limits_{j=0}^{t}(-1)^j \dbinom{t}{j}=\sum\limits_{j=0}^{t}\dbinom{t}{j}(-1)^j (1)^{t-j}=(-1+1)^t=0\)。证毕。

应用

错位排列通项

一个排列是错位排列当且仅当\(a_i \neq i\)恒成立。我们把\(a_i=i\)看作坏事件\(A_i\)。那么容易求出\(N_\geq(\{A_{i_1},\cdots,A_{i_t}\})=(n-t)!\)

代入容斥原理的公式,\(N_=(\empty)=\sum\limits_{j=0}^n (-1)^j \sum\limits_{J\in\binom{\mathscr{A}}{j}} (n-j)!=\sum\limits_{j=0}^n (-1)^j \dbinom{n}{j} (n-j)!\)

第二类斯特林数通项

\(k\)个球\(n\)个箱子,球不同箱子不同至少一个,答案是\(\left\{\begin{array}{l} k \\ n \end{array}\right\}n!\)。而不从分组的角度而从球的角度看,相当于求从\([k]\)到\([n]\)的满射的个数。那么利用容斥原理,把\(i\)没有被射到看作坏事件\(A_i\),那么有\(N_\geq(\{A_{i_1},\cdots,A_{i_t}\})=(n-t)^k\)。于是有\(N_=(\empty)=\sum\limits_{j=0}^n (-1)^j \sum\limits_{J\in\binom{\mathscr{A}}{j}} (n-j)^k=\sum\limits_{j=0}^n (-1)^j \dbinom{n}{j} (n-j)^k\)。

综上有\(\left\{\begin{array}{l} k \\ n \end{array}\right\}=\dfrac{1}{n!}\sum\limits_{j=0}^n (-1)^j \dbinom{n}{j} (n-j)^k\)

二分图完美匹配

通过邻接矩阵,完美匹配的方案数可以写成积和式\(\text{perm}A=\sum\limits_{\sigma}\prod\limits_{i=1}^{n}A_{i,\sigma(i)}\)。复杂度\(O(n! \cdot n)\)

利用容斥原理,把右侧的节点\(i\)没有被匹配上看作坏事件\(A_i\),那么\(N_\geq(J)=\prod\limits_{i=1}^{n}\left(\sum\limits_{j \in [n] \backslash J}A_{i,j}\right)\)。于是有\(N_=(\empty)=\sum\limits_{J\in\mathscr{A}}(-1)^{|J|} \prod\limits_{i=1}^{n}\left(\sum\limits_{j \in [n] \backslash J}A_{i,j}\right)\)。复杂度由枚举全排列转化为了枚举子集,复杂度\(O(2^n \cdot n)\)。可以证明,在渐进意义下这是最优复杂度了。

标签:limits,mathscr,sum,容斥,倍数,集合,原理,empty
From: https://www.cnblogs.com/qixingzhi/p/17160015.html

相关文章

  • webpack模块化的原理
    commonjs在webpack中既可以书写commonjs模块也可以书写es模块,而且不用考虑浏览器的兼容性问题,我们来分析一下原理。首先搞清楚commonjs模块化的处理方式,简单配置一下webp......
  • 彻底搞懂React-hook链表构建原理
    写在前面的小结每一个hook函数都有对应的hook对象保存状态信息useContext是唯一一个不需要添加到hook链表的hook函数只有useEffect、useLayoutEffect以及us......
  • 从实现一个React到深度理解React框架核心原理
    前言这篇文章循序渐进地介绍实现以下几个概念,遵循本篇文章基本就能搞懂为啥需要fiber,为啥需要commit和phases、reconciliation阶段等原理。本篇文章又不完全和原文一致,这......
  • 《分布式技术原理与算法解析》学习笔记Day24
    分布式缓存在计算机领域,缓存是一个非常重要的、用来提升性能的技术。什么是分布式缓存?缓存技术是指用一个更快的存储设备存储一些经常用到的数据,供用户快速访问。分布......
  • docker 镜像原理
    文件系统docker的镜像是由多个只读的文件系统叠加在一起形成的。每启动一个容器的时候,会加载只读层并在栈顶增加一个读写层。增删改查都是在读写层操作的。在docker中,只......
  • 4.7-Catche的基本原理
    存储系统中的Catche视图Cache的功能:缓解快速CPU与慢速的主存之间的速度差异Cache的理论基础:局部性原理Cache的工作过程读操作如何判断数据造Cache中?Cache中的数......
  • 4.4-动态存储器的工作原理
    SRAM存储单元的不足晶体管过多存储密度低功耗大DRAM存储单元的基本结构解决SRAM不足采取的方法:去掉两个负载管:T3,T4提升存储密度降低功耗降低成本利用栅极分布......
  • 03_16_JavaWeb||day19_Filter&Listener||day19_Filter&代理模式(23种设计模式之一:用来
    今日内容*Servlet,Filter,Listener被称为JavaWeb三大组件1.Filter:过滤器2.Listener:监听器1.Filter:过滤器概念:生活中的过滤器:净水器,空气净化器,土匪、web中的过滤器:当......
  • 4.3-静态存储器的工作原理
    静态存储单元结构(SRAM存储单元结构)(内存指的是断电信息就没有了)工作管:工作管构成的稳定互锁状态来保存信息负载管:为工作管提供电流门控管:控制存储单元与外界的通断写......
  • 开关电源的控制类型和原理
    关于半桥llc谐振式变换器的基本原理?首先它属于正激式变换器,包含两个谐振电感和一个谐振电容,由于高频变压器一次绕组存在漏感Lp0和功率开关管存在输出电容Coss的缘故,半......