错位重排 如何计算-错位重排 如何计算

错位重排是一种在序列中重新排列元素的位置，使得某些特定的子序列能够保持不变。对一个长度为n的序列，它的所有毛病排列的数量可以通过使用组合数学中的星号和错位操作来计算。

具体来讲，我们可使用以下步骤：

1、 将所有的毛病排列看做是由n个“*”字符组成的字符串，其中每一个字符表示一个位置可以被任何其他位置取代。

2、 使用组合数学中的星号和错位操作，将字符串中的每一个“*”字符替换为其左侧的一个字符，或将其右侧的一个字符替换为其左侧的一个字符。这样就能够得到一个新的毛病排列。

例如，如果原始序列是1 2 3 4 5，那末其所有毛病排列可以通过下面的步骤计算出来：

1、 将所有毛病排列看做是由n=5个“*”字符组成的字符串，即“****”，“****”，“**”，“*”，“*”。

2、 将字符串中的每一个“*”字符替换为其左侧的一个字符，或将其右侧的一个字符替换为其左侧的一个字符。得到的新字符串分别是“12**”，“12***”，“12**”，“1*”，“1*”。

因此，这个序列的所有毛病排列数量为6个。

错位重排公式是什么

错位重排公式是：Dn=(n-1)(Dn-1+Dn-2)，其中，D1=0，D2=1，D3=2，D4=9，D5=44。

要想理解错位重排，我们先来看一个简单的例子：三只鸽子对应各自的鸽笼，有一天每只鸽子都没有飞进自己的笼子，各自没有回各自的“家”，有三只鸽子分别为A、B、C，它们对应的笼子分别为a、b、c，题目的要求其实就是相互连线，但是A-a，B-b，C-c不能连接，这样的模型就叫做错位重排模型。

举例说明

一、四位厨师聚餐时各做了一道拿手菜。现在要求每个人去品尝一道菜，但不能尝自己做的那道菜。问共有几种不同的尝法。

解析：题目要求4个厨师品尝菜，但每个厨师都不能品尝自己的那道菜，符合错位重排模型。求解的是D4，利用公式或者直接查找前面总结的数据，D4=9。

二、某集团企业5个分公司分别派出一人去集团总部参加培训，培训后再将5人随机分配到这5个分公司，每个分公司只分配1人，问5个参加培训的人中，有且仅有1人在培训后返回原公司的方式有几种。

解析：此题总共是5个人，但最终是只有一个人回到原公司，所以先从5个人中选出1个人返回原单位，然后4个人错位重排就可，结果＝C(1，5)×9=45。

错排公式1到9的计算公式为D(n)=(n-1)*(D(n-1)+D(n-2)。

错排问题，是组合数学中的问题之一。考虑一个有n个元素的排列，若一个排列中所有的元素都不在自己原来的位置上，那么这样的排列就称为原排列的一个错排。

现代数学集合论中，元素是组成集的每个对象。换言之，集合由元素组成，组成集合的每个对象被称为组成该集合的元素。例如：集合{1，2，3}中1，2，3都是集合的一个元素。

错排公式

问题： 十本不同的书放在书架上。现重新摆放，使每本书都不在原来放的位置。有几种摆法？

这个问题推广一下，就是错排问题，是组合数学中的问题之一。考虑一个有n个元素的排列，若一个排列中所有的元素都不在自己原来的位置上，那么这样的排列就称为原排列的一个错排。 n个元素的错排数记为D(n)。

研究一个排列错排个数的问题，叫作错排问题或称为更列问题。

错排问题最早被尼古拉·伯努利和欧拉研究，因此历史上也称为伯努利-欧拉的装错信封的问题。这个问题有许多具体的版本，如在写信时将n封信装到n个不同的信封里，有多少种全部装错信封的情况？

又比如四人各写一张贺年卡互相赠送，有多少种赠送方法？自己写的贺年卡不能送给自己，所以也是典型的错排问题。

简化公式

错排公式的原形为D(n) = n! (1/0! - 1/1! + 1/2! - 1/3! - ..... + (-1)^n!)，当n很大时计算就很不方便。一个供参考的简化后的公式是D(n) = [n!/e+0.5] ，其中e是自然对数的底，[x]为x的整数部分。

证明：

由于1/e = e^(-1) = 1/0! - 1/1! + 1/2! - 1/3! - ..... + (-1)^n! + Rn(-1),

其中Rn(-1)是余项，等于(-1)^(n+1) * e^u / (n+1)!，且u∈(-1, 0).

所以，D(n) = n! * e^(-1) - (-1)^(n+1) * e^u / (n+1), u∈(-1, 0).

而|n! Rn| = |(-1)^(n+1) * e^u / (n+1)| = e^u / (n+1) ∈ (1/[e(n+1)], 1/(n+1))，可知即使在n=1时，该余项（的绝对值）也小于1/2。

因此，无论n! Rn是正是负，n! / e + 1/2的整数部分都一定与M(n)相同。

对于比较小的n，结果及简单解释是：

D(0) = 0（所有的元素都放回原位、没有摆错的情况）

D(1) = 0（只剩下一个元素，无论如何也不可能摆错）

D(2) = 1（两者互换位置）

D(3) = 2（ABC变成BCA或CAB）

D(4) = 9

D(5) = 44

D(6) = 265

D(7) = 1854

D(8) = 14833

D(9) = 133496

D(10) = 1334961

以上内容参考百度百科：错排公式