错位重排递推公式推导
- 来源：互联网
- 发布时间：2026-04-29 19:04:41
你好，错位重排递推公式是一个经典的组合数学公式，用于计算 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 个元素的错排数。
