基本反演推论
对于 \(|F|=n,|G|=m\),要证明 \(F[x] = \sum_\limits{i=0}^{+\infin} A[x,i] G[i] \iff G[x]=\sum_\limits{i=0}^{+\infin} B[x,i] F[i]\)。
\(F\) 为 \(G\) 的前缀和,
\(F[x]=\sum_\limits{i=0}^{+\infin} [i\leq x]G[i] , G[x] = \sum_\limits{i=0}^{\infin} [i=x]F[i] - [i=x-1]F[i]\)
\((A*B)[x,y] = \sum_\limits{i=0}^{+\infin} A[x,i] B[i,y] = \sum_\limits{i=0}^x B[i,y] = \sum_\limits{i=0}^x [y=i]-[y=i-1] = [x=y]\) (注意,这里 \(i,y\) 的顺序)。
\(-1\) 的幂的移动:乘上你需要的,根据条件来。
二项式反演
代数:
要证 \(F(x) = \sum_\limits{i=0}^x (-1)^i\dbinom {x} {i} G(i) \iff \cdots(对称)\),那么有 \(A[x,i]=B[x,i](-1)^i \dbinom {x} {i}\) ,即证明 \(A*B=I\)。
\[\begin{aligned} (A*B)[x,y] & = \sum_\limits{i=0}^{+\infin} A[x,i] B[i,y] \\ & = \sum_\limits{i=0}^{+\infin} (-1)^i \dbinom {x} {i} (-1)^y \dbinom {i} {y} \\ & = \sum_\limits{i=0}^x (-1)^i \dbinom {x} {i} (-1)^y \dbinom {i} {y} \\ & = \sum_\limits{i=0}^x (-1)^{i+y} \dbinom {x} {i} \dbinom {i} {y} \\ & = \sum_\limits{i=y}^x (-1)^{i+y} \dbinom {x} {y} \dbinom {x - y} {i - y} \\ & = \dbinom {x} {y} \sum_\limits{i=y}^x (-1)^{i+y} \dbinom {x - y} {i - y} \\ & = \dbinom {x} {y} \sum_\limits{i=0}^{x-y} (-1)^{i+2y} \dbinom {x - y} {i} \\ & = \dbinom {x} {y} (1-1)^{x-y} \\ & = [x=y] \end {aligned} \]考虑移动 \(-1\) 的幂。
\[(A*B)[x,y] = \textcolor{red}{\sum_\limits{i=0}^{+\infin} (-1)^i \dbinom {x} {i} (-1)^y \dbinom {i} {y}} = [x=y] \\ \begin{aligned} \textcolor{red}{RED} & = \sum_\limits{i=0}^{+\infin} \dbinom {x} {i} (-1)^{y+i} \dbinom {i} {y} \\ \end {aligned} \]组合意义(这块结合题目理解):
错位排列:
钦定法考虑 \(|p|=n,f(n,k):\sum [p_i=i]=k,g(n,k):钦定k个,剩下随便\)。
考虑每个 \(g(n,k)\) 究竟统计到了哪些。
\[\begin{aligned} g(n,k)=\sum_\limits{i=k}^n \dbinom {i} {k} f(n,i) \iff f(n,k)&=\sum_\limits{i=k}^n (-1)^{i-k}\dbinom {i} {k} g(n,i) \\ & = \sum_\limits{i=k}^{n} (-1) ^ {i-k} \dbinom {i} {k} \dbinom {n} {i} (n-i)! \\ & = \sum_\limits{i=k}^{n} (-1) ^ {i-k} \dbinom {i} {k} \frac {n!} {i!} \end{aligned} \] 标签:aligned,dbinom,limits,sum,infin,反演,二项式 From: https://www.cnblogs.com/TongKa/p/18531115