标签：sum 反演 iff choose 二项式 钦定
0. 二项式反演
0.1. 形式
\[F(n)=\sum_{i=0}^{n}(-1)^{i}{n \choose i}G(i) \iff G(n)=\sum_{i=0}^{n}(-1)^{i}{n \choose i}F(i)
\]
\[F(n)=\sum_{i=0}^{n}{n \choose i}G(i) \iff G(n)=\sum_{i=0}^{n}(-1)^{n-i}{n \choose i}F(i)
\]
\[F(x)=\sum_{i=x}^{n}(-1)^{i}{i \choose x}G(i) \iff G(x)=\sum_{i=x}^{n}(-1)^{i}{n \choose i}F(i)
\]
\[F(x)=\sum_{i=x}^{n}{i \choose x}G(i) \iff G(x)=\sum_{i=x}^{n}(-1)^{i-x}{i \choose x}F(i)
\]
0.2. 组合意义
二项式反演刻画了恰好和钦定之间的关系。设 \(F(n)\) 表示钦定 \(n\) 个物品满足性质的方案，\(G(n)\) 表示恰好 \(n\) 个物品满足性质的方案，则自然有 \(F(x)=\sum_{i=x}^{n}{i \choose x}G(i)\)，则套用上述形式 4 有 \(G(x)=\sum_{i=x}^{n}(-1)^{i-x}{i \choose x}F(i)\)。
标签：sum,
反演,
iff,
choose,
二项式,
钦定
From： https://www.cnblogs.com/Aria-Math/p/17912038.html