[总结] 二项式反演学习笔记

其实就是两个式子:
\[ 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 \]
和更一般的式子(这个是至少和恰好的关系?:
\[ 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_k=\sum_{i=k}^n {i\choose k} g_i\Leftrightarrow g_k=\sum_{i=k}^n (-1)^{i-k} {i\choose k} f_i \]
证明的话暴力把一个代入另一个就行了。

至少和恰好的例子就是错排

至多和恰好的例子就是 球染色问题:

\(n\) 个球排成一行,你有 \(k\) 种颜色,要求给每一个球染色,相邻两个球颜色不可以相同,并且每种颜色至少使用一次

这是经常在高中数学组合那个部分见到的一个问题,只不过高中题目中数都很小

还是和刚刚的想法一样,如果没有每种颜色至少一次这个条件,那么问题很简单,答案是 \(k(k−1)^{n−1}\)。这些方案是由恰好使用了 \(i(i=0,1,2,⋯,k)\) 种颜色的方案组成的,那么设 \(f_i\)恰好使用了 \(i\) 种颜色的方案数,可以得到
\[ k(k-1)^{n-1} = \sum_{i=0}^k {k \choose i} f_i \]
反演得到
\[ f_k = \sum_{i=2}^k (-1)^{k+i} {k \choose i} i(i-1)^{n-1} \]

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/zgydww.html