这是两个本质不同的东西。
多步容斥是“至少或至多选若干个”到“恰好选若干个”的变换。而二项式反演是“钦定选若干个”到“恰好选若干个”的变换。二项式反演虽然形式上和多步容斥极为相似,但它们并不等价,只是习惯上很多人把他们都称之为多步容斥。
在二项式反演的组合意义上,记 \(f(n)\) 表示 “钦定选 \(n\) 个”,\(g(n)\) 表示 “恰好选 \(n\) 个”,则对于任意的 \(i\ge n\),\(g(i)\) 在 \(f(n)\) 中被计算了 \(\binom in\) 次,故有
\[f(n)=\sum_{i=n}^m\binom ing(i) \]其中 \(m\) 是数目上界。
十分值得注意的是,在定义中,\(f(n)\) 表示先钦定 \(n\) 个,再统计钦定情况如此的方案数,其中会包含重复的方案,因为一个方案可以有多种钦定情况。具体地,对于恰好选择 \(i\) 个,钦定情况数为 \(\binom in\),故 \(g(i)\) 在 \(f(n)\) 中被计算了 \(\binom in\) 次。切勿将 \(f(n)\) 理解为普通的后缀和。
举个例子,错排数 \(D_n\) 的一个公式是
\[D_n=\sum_{k=0}^n(-1)^k\binom nk(n-k)! \]这个公式是对的,然而从容斥的角度看毫无疑问是似是而非的。如果把 \((-1)^k\) 理解为容斥系数,这个式子的意思似乎是先选定至少 \(k\) 个位置使得 \(a_i=i\),剩下的随意排,也就是至少 \(k\) 个位置不错位的方案数,但仔细想想并不是这样的。
考虑 \(n=3,k=1\) 时公式给出方案数为 \(6\),而实际上只有下面四种方案:
\[123,132,321,213 \]这是因为 \(123\) 被计算了 \(3\) 次,毫无疑问这里从容斥原理的角度看是算重复了。但是重二项式反演的角度看则刚刚好:设 \(f_i\) 表示恰好有 \(i\) 个 \(a_k=k\) 的排列数,\(g_i\) 表示钦定有 \(i\) 个 \(a_k=k\) 的排列数,那么
\[g_i=\sum_{j\geq i} \binom jif_j \]二项式反演得到
\[f_i=\sum_{j\geq i} (-1)^{j-i} \binom jig_j \]我们要求的就是 \(f_0\)。
标签:多步,钦定,容斥,反演,binom,二项式 From: https://www.cnblogs.com/szdytom/p/note-binomial-inversion-vs-inclusion-exclusion.html