Skip to content

容斥原理

2021-09-06

INFO

若无特殊说明,本章涉及的变量皆为正整数。

简介

容斥原理是一种不重不漏的计数原理。

例,A,B,C 三人竞选扫黄队长:

  • 15 人投给 A
  • 16 人投给 B
  • 17 人投给 C
  • 2 人同时投给 A,B,C
  • 4 人同时投给 A,B
  • 5 人同时投给 A,C
  • 6 人同时投给 B,C

问共有多少人参与投票。

A,B,C 三人的得票情况以用韦恩图描述:

  • |A|=15
  • |B|=16
  • |C|=17
  • |ABC|=2
  • |AB|=4
  • |AC|=5
  • |BC|=6

求的是投票人数,即 |ABC|

|ABC|=|A|+|B|+|C||AB||AC||BC|+|ABC|

将上述问题推广到普遍情况,就是容斥原理。

公式

并集

对于 n 个集合 S1,S2Sn|S| 表示集合 S 的元素数,则:

|i=1nSi|=i|Si|i<j|SiSj|+i<j<k|SiSjSk|+(1)n+1|i=1nSi|

xSa1,Sa2,,Sam,根据公式,|i=1nSi| 中包含元素 x 的个数为:

cnt(x)=m(m2)+(m3)+(1)n+1(mm)=(m0)i=0m(1)i(mi)

根据 二项式定理 有:

(11)m=i=0m(mi)1mi(1i)=i=0m(1)i(mi)cnt(x)=(m0)(11)m=1

每个元素只出现一次,等价于并集,证毕。

交集

对于 n 个集合 S1,S2Sn,已知全集为 U

|i=1nSi|=|U||i=1nSi|

其中 |i=1nSi| 套用 并集 的公式计算即可。

多重集的排列数

  • 普通集合:不允许有相同的元素;
  • 多重集:相同的元素可以出现多次。

S={n1a1,n2a2,,nkak} 是由 n1a1n2a2nkak 组成的多重集。

n=i=1kni

S 的全排列个数为:

n!n1!n2!nk!
证明

n 个不同元素的全排列有 n! 种。

若有 j 个元素相同,则 n! 种排列中有 j! 种排列应算作同一种。排列数为:

nj!

根据 乘法原理,多重集的全排列个数为:

n!n1!n2!nk!

多重集的组合数 1

S={a1,a2,,ak},从 S 中任取 λ 个元素的方案数为:

(k+λ1k1)
证明

原问题等价于求以下方程非负整数解的个数:

x1+x2++xk=λ

解的个数用插板法计算:

λ1 之间插 k1 块板,使其分为 k 个区间。第 i 个区间的和代表 xi。这样就构造出了一组解。

需要注意,板插在两端或同一个空隙中是允许的。

最初有 λ+1 个空隙。插第一块板有 λ+1 种方法,第二块有 λ+2 种,第三块有 λ+3k1 块有 λ+k1 种。根据 乘法原理,总的方案数为:

(λ+1)(λ+2)(λ+3)(λ+k1)=Aλ+k1k1

但是插板的顺序与答案无关。这么算显然会包含一些重复情况:

每一个方案都有 (k1)! 种不同的插板顺序,故答案为:

Aλ+k1k1(k1)!=(k+λ1k1)

多重集的组合数 2

S={n1a1,n2a2,,nkak},从 S 中任取 λ(λini) 个元素的方案数为:

(k+λ1k1)i(k+λni2k1)+i<j(k+λninj3k1)+(1)k(k+λinik1k1)
证明

考虑容斥原理:合法方案数 = 总方案数 不合法方案数。

总方案数 =(k+λ1k1),详见 多重集的组合数 1

于是问题转化为求不合法方案数。

  • Tiai 超标的多重集。先取 ni+1ai,再任取 λni1 个元素,加入 Ti。不同 Ti 的数量为 (k+λni2k1)
  • Tijai,aj 超标的多重集。先取 ni+1ainj+1aj,再任取 λninj2 个元素,加入 Tij。不同 Tij 的数量为 (k+λninj3k1)
  • ...

依次类推,由容斥原理可得,不合法的方案数为:

|{T}|=i(k+λni2k1)i<j(k+λninj3k1)++(1)k+1(k+λinik1k1)

于是合法的方案数为:

(k+λ1k1)|{T}|