Appearance
若无特殊说明,本章涉及的变量皆为正整数。
简介
容斥原理是一种不重不漏的计数原理。
例,
人投给 ; 人投给 ; 人投给 ; 人同时投给 ; 人同时投给 ; 人同时投给 ; 人同时投给 。
问共有多少人参与投票。
; ; ; ; ; ; 。
求的是投票人数,即
将上述问题推广到普遍情况,就是容斥原理。
公式
并集
对于
交集
对于
其中
多重集的排列数
- 普通集合:不允许有相同的元素;
- 多重集:相同的元素可以出现多次。
设
设
多重集的组合数 1
设
原问题等价于求以下方程非负整数解的个数:
解的个数用插板法计算:
在
需要注意,板插在两端或同一个空隙中是允许的。
最初有
但是插板的顺序与答案无关。这么算显然会包含一些重复情况:
每一个方案都有
多重集的组合数 2
设
考虑容斥原理:合法方案数
总方案数
于是问题转化为求不合法方案数。
- 设
为 超标的多重集。先取 个 ,再任取 个元素,加入 。不同 的数量为 ; - 设
为 超标的多重集。先取 个 和 个 ,再任取 个元素,加入 。不同 的数量为 ; - ...
依次类推,由容斥原理可得,不合法的方案数为:
于是合法的方案数为: