错位排列公式的D是什么

公式是D[n] = (n-1)(D[N-1] + D[n-2])假设n个数是从1到n，n个位置（或者说信封）是从p1到pn。

将数字分为两种1~(n-1)，和n。第一种分有(n-1)个数，针对每个数考虑有几种排列，假设当前考虑的是数字k显然数字k不能放在pk上（否则不符合错位的要求）公式第一部分考虑将k放在pn上，将n放在pk上，这样n和k就满足了错位的要求。那么在这种情况下，有多少种排列呢？因为n个数字中；2个数字固定，所以相当于剩下n-2个数字的错排数量：D[n-2]公式第二部分这一部分稍难理解。同样，k还是放在pn上，但是此时同样也不允许n放在pk上，也就是将n也放入剩下的n-2个数字中进行错排，此时有D[n-1]种组合。这里的关键点在于，n-1个数错排，所谓错排，就有相应的对排(原位置)，除k以外，其他数字原位置就是她们的数字位置，但数字n的原位置在哪呢？在k。即这种情况下k的位置出现数字n是不允许的。这有两层含义：这种情况下，就完全符合D[n-1]的情况这样n不允许在k处，也就和公式第一部分数量不重复。同时又和第一种情况完全互补合并由于有n-1个（公式第一部分+公式第二部分），所以最后公式为D[n] = (n-1)(D[N-1] + D[n-2])