其实就是两个式子:
\[
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}
\]