「排列组合」错排公式
APJifengc
·
2021-07-14 18:46:23
·
个人记录
什么是错排公式？
求有多少序列 A 满足下列条件：
对于任意一个位置 i ，满足 A_i\ne i.
太长不看版： 设 d(n) 为长度为 n 的序列错排数量，则有
d(n)=\left\{
\begin{aligned}
&1&(n=0)\\
&0&(n=1)\\
&(n-1)\times (d(n-1)+d(n-2))&(n\ge1)
\end{aligned}
\right.
证明
我们首先来考虑，首先将 m 放置在 k 位置上，显然 k 的取值有 (n-1) 个.
接下来考虑 k 放置的位置：
则接下来要对剩下的 $n-2$ 个数进行错排，即 $d(n-2)$ 种情况， 此时第一种情况的个数为 $(n-1)\times d(n-2)$.
那么显然 $i$ 不能等于 $k$ ， 所以 $k$ 也是进行错误排序，即对剩余的 $(n-1)$ 个数进行错排，有 $d(n-1)$ 种情况，则第二种情况的个数为 $(n-1)\times d(n-1)$.
综上所述，
\begin{aligned}
d(n)&=(n-1)\times d(n-2)+(n-1)\times d(n-1)\\
&=(n-1)\times (d(n-2)+d(n-1))
\end{aligned}
考虑边界情况，当 n=0 时，即空序列，只有一种情况，即 d(0)=1.
当 n=1 时， 唯一的这一个元素只能放在这个位置，所以没有办法进行错排，即 d(1)=0.
练习： P4071
错排公式还有通项公式和简化公式，不过我太菜了就没看，如果你想看就去百度吧