Java教程

二项式反演

本文主要是介绍二项式反演,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

二项式反演

定理 \(1\):\(F(n)=\sum_{i=0}^{n}{{n\choose i}G(i)}\Leftrightarrow G(n)=\sum_{i=0}^{n}{(-1)^{n-i}{n\choose i}F(i)}\)

证明:

提取系数有 \(F[n]=\sum_{i=0}^{n}{{n\choose i}G[n]}\)

\(\displaystyle \to \frac{F[n]}{n!}=\sum_{i=0}^{n}{\frac{1}{(n-i)!}\frac{G[i]}{i!}}\)

构造指数生成函数 \(\displaystyle f(n)=\sum_{i=0}^{\infty}{\frac{F[i]}{i!}x^i},g(n)=\sum_{i=0}^{\infty}{\frac{G[i]}{i!}x^i}, E(x)=e^x=\sum_{i=0}^{\infty}{\frac{x^i}{i!}}\)

可以发现卷积形式:\(f=g\ast E\)

于是,\(g=f\ast E^{-1}=f\ast e^{-x}\)

所以可以得到 \(\displaystyle g[n]=\frac{G[n]}{n!}=\sum_{i=0}^{n}f[i]\times (-1)^{n-i}\frac{1}{(n-i)!}\)

整理得:\(\displaystyle \frac{G[n]}{n!}=\sum_{i=0}^{n}{\frac{F[i]}{i!}\times (-1)^{n-i}\frac{1}{(n-i)!}}\)

证毕。

稍微变换一下,可以得到二项式反演的另一种形式。

定理 \(2\): \(F(n)=\sum_{i=0}^{n}{(-1)^i{n\choose i}G(i)}\Leftrightarrow G(n)=\sum_{i=0}^{n}{(-1)^{i}{n\choose i}F(i)}\)

非常的对称唉。可以发现这只在定理 \(1\) 移动了 \(-1\) 的次幂。

定理 \(3\): \(\displaystyle F(n)=\sum_{i=n}{{n\choose i}G(i)}\Leftrightarrow G(n)=\sum_{i=n}{(-1)^{n-i}{n\choose i}F(i)}\)

由对定理 \(2\) 关系矩阵进行转置可知。

定理 \(2,3\) 的证明可以戳这里 反演原理

定理 \(4\): 移动定理 \(3\) 中 \(-1\) 的次幂,可得 \(\displaystyle F(n)=\sum_{i=n}{(-1)^i{n\choose i}G(i)}\Leftrightarrow G(n)=\sum_{i=n}{(-1)^i+{n\choose i}F(i)}\)

错排问题与二项式反演:

问题:设 \(a_{1\sim n}\) 是 \(1\sim n\) 的一个排列,且 \(\forall i\in (1,n),a_i\neq i\) 。

求满足条件的排列的方案数。

解:

设 \(D[n]\) 表示 \(n\) 个数的错排方案数(即满足 \(a_i\neq i\) )。

那么有 \(n!=\sum_{i=0}^{n}{{n\choose i}D[i]}\) ,即:\(n\) 个数的全排列数 \(=\) \(\sum_{i=0}^{n}\) 选择 \(i\) 个数的错排方案数。

\(wc\),这不就是二项式定理的标准形式吗。

二项式反演一下得到,\(\displaystyle D[n]=\sum_{i=0}^{n}{(-1)^{n-i}{\frac{n!}{(n-i)!}}}\)

\(\displaystyle \to D[n]=n!\sum_{i=0}^{n}{\frac{(-1)^i}{i!}}\)

这样,就求得了错排公式 \(\displaystyle D[n]=n!\sum_{i=0}^{n}{\frac{(-1)^i}{i!}}\)

应用

若记 \(f(n,k)\) 表示:\(n\) 个数钦定选 \(k\) 个 \(p_i=i\) ,其余的任意排列;记 \(g(n,k)\) 表示 \(n\) 个数恰好选 \(k\) 个,其余的都满足 \(a_i\neq i\)

那么对于任意的 \(f(n,k)\) 有 \(f(n,k)=\sum_{i=k}^{n}{{i\choose k}g(n,i)}\)

使用二项式反演得 \(\sum_{i=k}^{n}{}\)

在实际题目中,构造这样的 \(g\) 和 \(f\) 即可运用二项式反演解决问题。

练习题

[MtOI2018]情侣?给我烧了! - 洛谷

题解:LuoguP4921 情侣?给我烧了

这篇关于二项式反演的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!