二项式反演代数证明

àì夳堔傛蜴生んèń 2021-11-05 01:00 231阅读 0赞

前几天学了一下二项式反演的证明，咕了几天后觉得还是发一篇博客比较好。  
  
二项式反演，就是这么个式子：  
\\(f(n) = \\sum \_ \{i = 0\} ^ \{n\} C\_\{n\} ^ \{i\} g(i) \\Leftrightarrow g(n) = \\sum \_ \{i = 0\} ^ \{n\} (-1) ^ \{n - i\}C\_\{n\} ^ \{i\} f(i)\\)。  
代数证明如下：  
\\\[\\begin\{align\*\} g(n) &= \\sum \_ \{i = 0\} ^ \{n\} (-1) ^ \{n - i\} C\_\{n\} ^ \{i\} \\sum \_ \{j = 0\} ^ \{i\} C\_\{i\} ^ \{j\} g(j) \\\\\\ &= \\sum \_\{i = 0\} ^ \{n\} \\sum \_ \{j = 0\} ^ \{i\} C\_\{n\} ^ \{i\} C\_\{i\} ^ \{j\} g(j)(-1) ^ \{n - i\} \\\\ \\end\{align\*\}\\\]  
其中\\(C\_\{n\} ^ \{i\} C\_\{i\} ^ \{j\} = C\_\{n\} ^ \{j\} C \_\{n - j\} ^ \{i - j\}\\)，这个展开成阶乘形式就会发现两侧相等。  
\\\[ \\begin\{align\*\} g(n) &= \\sum \_\{i = 0\} ^ \{n\} \\sum \_ \{j = 0\} ^ \{i\} C\_\{n\} ^ \{j\} C\_\{n - j\} ^ \{i - j\} g(j) (-1) ^ \{n - i\} \\\\ &= \\sum \_ \{j = 0\} ^ \{n\} g(j)C\_\{n\} ^ \{j\} \\sum \_ \{i = j\} ^ \{n\} C\_\{n - j\} ^ \{i - j\}(-1) ^ \{n - i\} \\end\{align\*\} \\\]  
对于\\(\\sum \_ \{i = j\} ^ \{n\} C\_\{n - j\} ^ \{i - j\}(-1) ^ \{n - i\}\\)，当\\(j = n\\)时，该式子等于\\(1\\)，否则等于\\(0\\)。当\\(j = n\\)时代入得证；当\\(j \\neq n\\)时，后面的\\(\\sum\\)就是杨辉三角第\\(n - j\\)行的偶数项之和减去奇数项之和（或者反过来），根据二项式定理可知，偶数项之和等于奇数项之和，那么得证。  
于是原式\\(=g(n)\\)。  
  
二项式反演还有另一种形式，也比较常见：  
\\(f(k) = \\sum \_ \{i = k\} ^ \{n\} C\_\{i\} ^ \{k\} g(i) \\Leftrightarrow g(k) = \\sum \_ \{i = k\} ^ \{n\} (-1) ^ \{i - k\} C\_\{i\} ^ \{k\} f(i)\\)  
证明方法类似：  
\\\[\\begin\{align\*\} g(k) &= \\sum \_ \{i = k\} ^ \{n\} (-1) ^ \{i - k\} C\_\{i\} ^ \{k\} \\sum \_ \{j = i\} ^ \{n\} C\_\{j\} ^ \{i\} g(j) \\\\ &= \\sum \_ \{i = k\} ^ \{n\} \\sum \_ \{j = i\} ^ \{n\} (-1) ^ \{i - k\} C\_\{j\} ^ \{k\} C\_\{j - k\} ^ \{i - k\} g(j) \\\\ &= \\sum \_ \{j = k\} ^ \{n\} C\_\{j\} ^ \{k\} g(j) \\sum \_ \{i = k\} ^ \{j\} (-1) ^ \{i - k\} C\_\{j - k\} ^ \{i - k\} \\end\{align\*\}\\\]  
然后后面的式子也是只有当\\(j = k\\)时为\\(1\\)，否则为\\(0\\)。  
  
最后推一道例题：[luogu P4859 已经没有什么好害怕的了][luogu P4859]

转载于:https://www.cnblogs.com/mrclr/p/10980495.html

[luogu P4859]: https://www.luogu.org/problemnew/show/P4859