求助容斥
  • 板块学术版
  • 楼主BugGod
  • 当前回复1
  • 已保存回复1
  • 发布时间2023/12/27 22:02
  • 上次更新2023/12/28 13:08:17
查看原帖
求助容斥
541254
BugGod楼主2023/12/27 22:02

rt,关于证明公式:∣⋂i=1nAi∣=∑S≠∅,S⊆{x∣1≤x≤n,x∈N+}(−1)∣S∣+1∣⋃i∈SAi∣|\bigcap_{i=1}^nA_i|=\sum_{S\neq\varnothing,S\subseteq \lbrace x|1\le x\le n,x\in \mathbb{N}_+\rbrace}(-1)^{|S|+1}|\bigcup _{i\in S}A_i|。

有一个证明思路:证明等式左边每个元素对右边贡献为 11 次,不属于左边的每个元素对右边贡献为 00,但是在证明后者时出现问题,设 aa 在原来 nn 个集合中出现了 kk 次(k≠nk\neq n),则贡献为 Ck1−Ck1+⋯+(−1)k+1Ck1C_k^1-C_k^1+\cdots+(-1)^{k+1}C_k^1,不一定为 00,求纠错。

2023/12/27 22:02
加载中...