反演魔术---二项式反演

$f(n) = \sum_{i = 0}^na_{ni}g(i)\g(n) = \sum_{i=0}^nb_{ni}f(i)$

• 二项式反演
• 斯特林反演
• 莫比乌斯反演
• 单位根反演

二项式反演

形式一:

$\ F(n)=\sum\limits_{i=0}^n(-1)^i\dbinom{n}{i}G(i)\G(n)=\sum\limits_{i=0}^n(-1)^i\dbinom{n}{i}F(i)$

形式二:

$\ F(n)=\sum\limits_{i=0}^n\dbinom{n}{i}G(i)\G(n)=\sum\limits_{i=0}^n(-1)^{(n-i)}\dbinom{n}{i}F(i)$

形式三:

$\ F(n)=\sum_{i=n}^N(-1)^i\dbinom{n}{i}G(i)\G(n)=\sum_{i=0}^N(-1)^i\dbinom{n}{i}F(i)$

形式四:

$\ F(n)=\sum_{i=n}^N\dbinom{n}{i}G(i)\G(n)=\sum_{i=0}^N(-1)^{i-n}\dbinom{n}{i}F(i)$

下面证明形式二为例

引理:

$\dbinom{n}{j}\dbinom{j}{i}\=\large{\frac{n!}{j!(n-j)!}\frac{j!}{i!(j-i)!}}\=\large{\frac{n!}{i!(n-i)!}\frac{(n-i)!}{(n-j)![(n-i)-(n-j)]!}}\=\large{\dbinom{n}{i}\dbinom{n-i}{n-j}}\$

$\ F(n)=\sum_{i=0}^n\dbinom{n}{i}G(i)\\sum_{i=0}^n(-1)^{(n-i)}\dbinom{n}{i}F(i)\=\sum_{i=0}^n(-1)^{(n-i)}\dbinom{n}{i}\sum_{j=0}^i\dbinom{i}{j}G(j)\=\sum_{i=0}^nG(i)\sum_{j=i}^n(-1)^{(n-j)}\dbinom{n}{j}\dbinom{j}{i}\=\sum_{i=0}^nG(i)\sum_{j=i}^n(-1)^{(n-j)}\dbinom{n}{i}\dbinom{n-i}{i-j}\=\sum_{i=0}^n\dbinom{n}{i}G(i)\sum_{j=i}^n(-1)^{(n-j)}\dbinom{n-i}{i-j}\=\sum_{i=0}^n\dbinom{n}{i}G(i)\sum_{j=0}^{n-i}(-1)^{n-i-j}\dbinom{n-i}{j}\=\sum_{i=0}^n\dbinom{n}{i}G(i)(1-1)^{(n-i)}\=G(n)$

应用: 错位排列

$$f(i)$$为恰好有i位错位的方案数, $g(i) = i!$
$\large{g(n) = n! = \sum_{i=0}^n}f(i) \dbinom ni$

$f(n) = \sum_{i=0}^n(-1)^{n-i}\dbinom ni g(i)\=\sum_{i=0}^n(-1)^{n-i} \frac {n!}{(n-i)!}\=n!\sum_{i=0}^n\frac{(-1)^i}{i!}$

(0)
(0)