设是集合的两个不同子集,若使得不是的子集,也不是的子集,则不同的有序集合对的组数为。
分数写 a/b,根号写 √ 或 sqrt,π 写 pi 也可以。
把互不包含看成同时避开两个坏关系,再对坏关系做容斥。
也可固定其中一个集合,分别要求另一个集合取到外部元素并漏掉内部元素,用这两个选择条件核对方向是否正确。
全部有序子集对有个,每个元素可属于两者、仅A、仅B或均不属于。若,去掉“仅A”状态,有个;同理。两者同时成立当且仅当,有个。容斥扣去可比较对子得,不相等条件自动满足。
固定 时, 要从 外至少选一个元素,并在 内至少漏掉一个元素,故有 种。对 的所有大小求和得 。 或5时贡献均为0,符合空集、全集与任何子集都可比较的事实。
“互不包含”适合转为两个包含事件的补集。两个事件的交集是集合相等,容斥时必须加回;只扣一次相等或把有序对视为无序,都会改变结果。
需识别并应用包含关系;逐元素容斥模型
核心工具:各步独立选择的乘法原理、补集与容斥
已记下,谢谢!