错位重排递推公式推导

2026-04-29

你好，错位重排递推公式是一个经典的组合数学公式，用于计算 n 个不同元素的错排数，即所有排列中，恰好有一个元素与其原始位置相同的排列数。错排数记为 D(n)。 首先，考虑 n 个元素的全排列数为 n!。假设我们要求 n 个元素的错排数，那么我们可以考虑将第 n 个元素放到任意一个位置。根据错排数的定义，此时有两种情况： 1. 第 n 个元素放到原始位置上，其余 n-1 个元素的错排数为 D(n-1)。 2. 第 n 个元素不放到原始位置上，此时有 n-1 个位置可以放置第 n 个元素，其余...

错排问题公式

2026-04-29

错排问题 错排问题是组合数学中的问题之一。一个含有n个元素的排列，若这个排列中所有的元素都不在自己原来的位置上，那么这样的一个排列就是原排列的一个错排。 求解方法 对于情况较少的排列，可以使用枚举法。 当n=1时，只有一种排列情况且不是错排，D1=0； 当n=2时，全排列有两种，1、2和2、1，后者是错排，D2=1； 当n=3时，全排列有3！=6种，错排有两种，D3=2； D4=9、D5=44、D6=265…… 对于排列数比较多时，枚举的方法就不合适了，可以用递推思想推导。 当n>=3时...