|
|
一個序列 $\{a_{n}\}$ 的二項式變換(binomial transform)是序列 $\{s_{n}\}$：
\begin{equation}\label1s_{n}=\sum _{k=0}^{n}(-1)^{k}{n \choose k}a_{k}.\end{equation}
再次应用binomial transform就获得原序列, 称为二项式反演:\begin{equation}\label2a_n=\sum_{k=0}^n (-1)^k {n\choose k} s_k.\end{equation}利用二项式反演可以计算错排数。
$n$个元素的排列数为$n!$，$n$个元素的错排数为$D_n$。
排列$n$个元素，选取$k$个元素有$n \choose k$种方法，使$k$个元素都不在原位有$D_k$种方法，其余$n-k$个元素都在原位有1种方法。对$k=0,\cdots,n$求和，
\begin{equation}\label3n!=\sum _{k=0}^{n}{n \choose k}D_{k}.\end{equation}
即\[n!=\sum _{k=0}^{n}(-1)^k{n \choose k}(-1)^kD_{k}.\]
对$n!$与$(-1)^nD_n$应用二项式反演得到\[(-1)^nD_n=\sum_{k=0}^n(-1)^k\frac{n!}{(n-k)!}\]
即\[D_n=n!\sum_{k=0}^n\frac{(-1)^{n-k}}{(n-k)!}\]
求和指标可以用$n-k$代$k$:\begin{equation}D_n=n!\sum_{k=0}^n\frac{(-1)^k}{k!}\label4\end{equation}
把\eqref{4}代入\eqref{3}得到的恒等式又见这帖11#和Finding a combinatorial proof of this identity
错位排列公式又见此帖与此帖 |
|
