全错位排列的递推公式是如何推导的？

问题描述

精选答案

全错位排列的递推公式到底是怎么推导出来的呢？

什么是全错位排列

全错位排列指的是将$n$个元素重新排列，使得每个元素都不在原来的位置上。我们设$n$个元素的全错位排列的排列数为$D(n)$。

递推公式的推导

1. 初始情况 当$n=1$时，只有一个元素，它没有位置可以错排，所以$D(1)=0$；当$n=2$时，两个元素交换位置，只有一种错排方式，即$D(2)=1$。
2. 对于$n>2$的情况 假设我们已经有$n-1$个元素的全错位排列$D(n-1)$和$n-2$个元素的全错位排列$D(n-2)$。现在考虑加入第$n$个元素。 我们把第$n$个元素放在除了它原来位置的$n-1$个位置中的任意一个，假设放在了第$k$个位置（$1\leqk\leqn-1$）。
   • 情况一：将第$k$个元素放到第$n$个位置。此时剩下$n-2$个元素进行全错位排列，排列数为$D(n-2)$。因为第$k$个元素有$n-1$种选择（即可以放在$n-1$个非自身位置），所以这种情况下的排列数为$(n-1)D(n-2)$。
   • 情况二：将第$k$个元素不放到第$n$个位置。此时可以把第$n$个位置看作是第$k$个元素原来的位置，那么就相当于对除第$n$个元素外的$n-1$个元素进行全错位排列，排列数为$D(n-1)$。同样，第$k$个元素有$n-1$种选择，所以这种情况下的排列数为$(n-1)D(n-1)$。

综合这两种情况，可得全错位排列的递推公式：$D(n)=(n-1)(D(n-1)+D(n-2))$。

通过上述推导过程，我们就得出了全错位排列的递推公式。在实际应用中，利用这个递推公式，结合初始条件$D(1)=0$和$D(2)=1$，就可以逐步计算出$n$个元素的全错位排列数$D(n)$。