关于简单容斥的一个奇怪推理
  • 板块学术版
  • 楼主Albert_van
  • 当前回复2
  • 已保存回复2
  • 发布时间2022/7/26 19:54
  • 上次更新2023/10/27 18:16:26
查看原帖
关于简单容斥的一个奇怪推理
326780
Albert_van楼主2022/7/26 19:54

RT。简单容斥的基本形态是这样的:

对于全集 UU,给定 nn 个性质,满足第 ii 个性质的元素集合为 AiA_i,设

ans=UA1A2Anans=|U\cap \overline{A_1}\cap \overline{A_2}\cap\cdots\cap \overline{A_n}|

UU不满足任何一个性质的元素个数。有一条公式是这样说的

ans=SA(1)SUS1S2SSans=\sum_{S\subseteq A} (-1)^{|S|}|U\cap S_1\cap S_2\cap\cdots\cap S_{|S|}|

然而本人口胡出来另一个公式,即 UU满足至少一个性质的元素个数

ans=SA(1)S+1US1S2SSans'=\sum_{S\subseteq A}(-1)^{|S|+1}|U\cap S_1\cap S_2\cap\cdots\cap S_{|S|}|

显然 ans=Uansans=|U|-ans',然而本人刚做到一道题目,用第一条公式算出来的 ansans 和用 Uans|U|-ans' 算出来的 ansans 不一样,把两个柿子代进去甚至会得出 ans+ans=0ans+ans'=0 的奇怪结论,错得非常离谱。

以上推理过程纯属瞎扯,一定有什么地方有一个甚至不止一个SB错误,望路过的大佬帮忙指正,不胜感激!

2022/7/26 19:54
加载中...