关于容斥原理 / P5505题解

标签：方案 题解 P5505 容斥 合法 小球 binom 钦定

发现很多题解连容斥原理的“钦定”和“至少”的区别都讲不清楚，误导萌新，所以写一下这两个东西的区别

“钦定”这个东西是会算重的，而“至少”不会。

举个例子吧，比如 \(1\ 2\ 3\) 三个位置不合法，如果我说“钦定”两个位置不合法，那么这里计算方案的时候这个不合法的方案会被计算三次，分别是钦定 \(1\ 2\) 不合法、\(2\ 3\) 不合法，\(1\ 3\) 不合法，而“至少”有两个位置不合法这个方案只会被算一次。

某容斥入门题P5505的题解里面几乎没一个能看的，都在说“至少”，为了更清楚理解一下这个东西到底啥意思就从容斥原理的公式出发来推一下这题

题意是有 \(n\) 个盒子，\(m\) 种不同颜色的小球，每种小球有 \(k\) 个，问每个盒子里至少有一个小球(不论种类)有多少种放法

设 \(U\) 中元素有 \(n\) 种不同的属性，而第 \(i\) 种属性称为 \(P_i\)，拥有属性 \(P_i\) 的元素构成集合 \(S_i\)，那么

\[\begin{aligned} \left|\bigcup_{i=1}^{n}S_i\right|=&\sum_{i}|S_i|-\sum_{i<j}|S_i\cap S_j|+\sum_{i<j<k}|S_i\cap S_j\cap S_k|-\cdots\\ &+(-1)^{m-1}\sum_{a_i<a_{i+1} }\left|\bigcap_{i=1}^{m}S_{a_i}\right|+\cdots+(-1)^{n-1}|S_1\cap\cdots\cap S_n| \end{aligned} \]

考虑怎么算不合法方案数，假设 \(P_i\) 指的是第 \(i\) 个盒子没有放小球，\(S_i\) 指的是所有第 \(i\) 个盒子没有放小球的方案的集合
假设至少有 \(i\) 个位置不合法，从一开始放的时候就不考虑这 \(i\) 个盒子就好，也就是所有的球放方案的时候都不考虑这 \(i\) 个，也就是说有

\[\prod_{j=1}^{m}\binom{n+a_j-1-i}{n-1-i} \]

然而我们是要钦定 \(i\) 个位置不合法，那么这 \(i\) 个位置就有 \(\binom {n}{i}\) 种钦定法
最终如果钦定 \(i\) 个位置不合法的方案数就是

\[\binom{n}{i}\prod_{j=1}^{m}\binom{n+a_j-1-i}{n-1-i} \]

实际上用上面的 \(P_i\) 和 \(S_i\) 的定义考虑容斥的第 \(i\) 项很简单就推出来了，很容易发现如果要容斥一定是指定 \(i\) 个位置的 \(P_i\) 为真，然后把这几个 \(S_i\) 并起来，一共有 \(\binom{n}{i}\) 种并法，实际上就是 \(\binom{n}{i}\) 个钦定法
那么就有了不合法方案的公式

\[\sum_{i=1}^{n-1}(-1)^{i-1}\binom{n}{i}\prod_{j=1}^{m}\binom{n+a_j-1-i}{n-1-i} \]

所有方案插板法算算就好

\[\prod_{i=1}^{m}\binom{n+a_i-1}{n-1} \]

如果把答案的公式写在一起就是大部分题解的那个写法

所以基本上所有题解里面写的“至少”都是错的，考虑容斥原理的公式，“钦定”才是对的

标签：方案,题解,P5505,容斥,合法,小球,binom,钦定
From： https://www.cnblogs.com/lostintianyi/p/17369860.html