一
假设 \(f(x)\) 代表恰好满足 \(x\) 个性质的方案数。钦定代表至少 \(x\) 个。
假设 \(g(x)\) 代表至多满足 \(x\) 个性质的方案数。
显然有
\[g(n)=\sum_{i=0}^n\left(\begin{matrix}n\\i\end{matrix}\right)f(i) \]并且有
\[f(n)=\sum_{i=0}^n\left(\begin{matrix}n\\i\end{matrix}\right)(-1)^{n-i}g(i) \]证明：
方式一：打小样例感性理解，找规律（归纳与总结。
方式二：
\[\begin{aligned} f(n)&=\sum_{i=0}^n\left(\begin{matrix}n\\i\end{matrix}\right)(-1)^{n-i}g(i) \\ &=\sum_{i=0}^n\left(\begin{matrix}n\\i\end{matrix}\right)(-1)^{n-i}\sum_{j=0}^i\left(\begin{matrix}i\\j\end{matrix}\right)f(j) \\ &=\sum_{i=0}^n\sum_{j=0}^i\left(\begin{matrix}n\\i\end{matrix}\right)\left(\begin{matrix}i\\j\end{matrix}\right)(-1)^{n-i}f(j) \\ &=\sum_{j=0}^nf(j)\sum_{i=j}^n\left(\begin{matrix}i\\j\end{matrix}\right)\left(\begin{matrix}n\\i\end{matrix}\right)(-1)^{n-i} \end{aligned} \] 标签：begin,right,end,matrix,sum,笔记,反演,二项式,left From： https://www.cnblogs.com/WindChime/p/18628462