错位重排递推公式推导

错位重排递推公式是一个经典的组合数学公式，用于计算 n 个不同元素的错排数，即所有排列中，恰好有一个元素与其原始位置相同的排列数。错排数记为 D(n)。

首先，考虑 n 个元素的全排列数为 n!。假设我们要求 n 个元素的错排数，那么我们可以考虑将第 n 个元素放到任意一个位置。根据错排数的定义，此时有两种情况

1. 第 n 个元素放到原始位置上，其余 n-1 个元素的错排数为 D(n-1)。

2. 第 n 个元素不放到原始位置上，此时有 n-1 个位置可以放置第 n 个元素，其余 n-1 个元素的错排数为 D(n-2)。

因此，根据加法原理，n 个元素的错排数可以表示为以下递推公式

D(n) = (n-1) [D(n-1) + D(n-2)]

其中，D(1) = 0，D(2) = 1。

这个递推公式的意义是，将第 n 个元素放置到任意一个位置，可以得到 (n-1) 种不同的情况。对于每种情况，要么第 n 个元素与原始位置相同，此时需要计算 n-1 个元素的错排数；要么第 n 个元素不与原始位置相同，此时需要计算 n-2 个元素的错排数。

通过递推公式，我们可以计算出 n 个元素的错排数。