错排问题的一些思考及递推公式推导

发表于 更新于 阅读次数： 本文字数： 776

首先，先让我们了解一下什么是错排问题：“错排问题（Derangement Problem），又称错位排列问题，是组合数学中的一个经典问题。它指的是将n个元素进行排列，使得没有一个元素出现在它原本的位置上。这样的问题在密码学、计算机科学和统计学等领域都有应用。” （来自文心一言）

递推公式

错排问题的最常见计算方法就是递推法，以下是推导过程

首先我们定义f[i][j]为前i个元素，有j个元素出现在它原本的位置上的排列数

那么便会有 式1：f[i][0] = (i - 1) * f[i - 1][0] + f[i - 1][1]

和 式2：f[i][1] = i * f[i - 1][0]

式1

表示前i个元素，有0个元素出现在它原本的位置上的排列数有且仅有两种情况

证明存在性

第一类 ：表示前i - 1个元素，有1个元素出现在它原本的位置上，那么第i个元素就可以和那个元素调换位置

第二类 ：表示前i - 1个元素，有0个元素出现在它原本的位置上，那么第i个元素就可以和前i - 1个元素中任意一个调换位置

证明唯一性

我们将一个合法的错排数列的最后一个位置上的数和这一位置原来的数调换位置

易得有且仅有两种情况 1 除最后一位外有且仅有一个元素，即被调换的那个处在原来的位置上 2 除最后一位外没有一个元素处在原来的位置上

这两种情况与上文两种情况对应

式2

表示前i个元素，有1个元素出现在它原本的位置上的排列数等于某一特定元素处在其原来位置上的排列数乘上可最为那特定元素的元素个数（i）

而前i个元素，某一特定元素处在其原来位置上的排列数即为第i个元素处在其原来位置上的排列数，即为前i - 1个元素，有0个元素出现在它原本的位置上的排列数

由此证毕

公式化简

将式1与式2进行简单的代换即可获得最常见的错排问题递推公式形式

f[i][0] = (i - 1)(f[i - 1][0] + f[i - 2][0])

或写作

$Di = (i - 1)(D{i - 1} + D_{i - 2})$