广义容斥定理杂谈
概念
用语言描述，容斥原理求的是不满足任何性质的方案数，我们通过计算所有至少满足 \(k\) 个性质的方案数之和来计算。
同样的，我们可以通过计算所有至少满足 \(k\) 个性质的方案数之和来计算恰好满足 \(k\) 个性质的方案数。这样的容斥方法我们称之为广义容斥原理。
形式
我们设 \(\alpha(k)\) 表示至少满足 \(k\) 个性质的方案数，\(\beta(k)\) 表示满足恰好 \(k\) 个性质的方案数。
我们有
\[\beta(k)=\sum\limits^{n}_{i=k}{(-1)^{i-k}\binom{i}{k}\alpha(i)}
\]
证明
我们令 \(\operatorname{tot}(p)\) 为恰好满足 \(p\) 个性质的方案数的被统计次数。
于是有
\[\operatorname{tot}(p)=\sum\limits_{i=k}^{p}{(-1)^{i-k}\binom{i}{k}\binom{p}{i}}
\]
因为 \(\binom{r}{m}\binom{m}{k}=\binom{r}{k}\binom{r-k}{m-k}\)，所以
\[=\sum\limits_{i=k}^{p}{(-1)^{i-k}\binom{p}{k}\binom{p-k}{i-k}}
\]
\[=\sum\limits_{i=0}^{p-k}{(-1)^{i}\binom{p}{k}\binom{p-k}{i}}
\]
提出常数，得
\[=\binom{p}{k}\sum\limits_{i=0}^{p-k}{(-1)^{i}\binom{p-k}{i}}
\]
根据二项式定理，可得
\[=\binom{p}{k}(1-1)^{p-k}=[p=k]
\]