标签：le text sum 容斥 beta 广义 alpha 原理

广义容斥原理

概念

广义容斥原理解决的是：计算所有至少满足 \(k\) 个性质的方案数之和。
同样的，我们可以通过计算所有至少满足 \(k\) 个性质的方案数之和来计算恰好满足 \(k\) 个性质的方案数。

方法

设 \(\alpha(k)\) 表示所有至少满足 \(k\) 个性质的方案数之和。
容易得到：

\[\alpha(0)=|\text{U}|\\ \alpha(1)=\sum_{i}{|a_i|}\\ \alpha(2)=\sum_{i,j}{|a_i\cap a_j|}\\ \cdots\\ \alpha(k)=\sum_{\text{S}\subseteq \text{U},|\text{S}|=k}{|\bigcap_{i\in\text{S}}{a_i}|} \]

我们可以发现 \(\alpha(k)\) 将具有 \(t\) 个性质的元素计算了 \(\binom{k}{t}\)

设 \(\beta(k)\) 代表恰好有 \(k\) 个元素的方案数，则：

\[\beta(k)=\alpha(k)-\sum_{k+1\le i \le n}{\binom{i}{k}\beta(i)} \]

还有一个公式：

\[\beta(k)=\sum_{k\le i \le n}{(-1)^{i-k}\binom{i}{k}\alpha (i)} \]

标签：le,text,sum,容斥,beta,广义,alpha,原理
From： https://www.cnblogs.com/legendcn/p/18312312