错位重排递推公式推导，错位重排数公式

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

错位排列问题就是指一种很难理解的复杂数学模型是伯努利和欧拉在错装信封时帽盯发现的，因为这个原因又称伯努利-欧拉装错信封问题。表达为：编号是1、2、…、n的n封信，装入编号为1、2、…、n的n个信封，要求每封信和信封的编号不一样塑菊帽，问有多少种装法？对这种类型问题有一个固定的递推公式，记n封信的错位重排数为Dn。



设1，2，...，n的全排列b1，b2，...，bn的集合为A,而使bi=i的全排列的集合记为Ai(1=i=n)，则Dn=|A|-|A1∪A2∪.

故此，Dn=n!-|A1∪A2∪.

注意到|Ai|=(n-1)!，|Ai∩Aj|=(n-2)!，...，|A1∩A2∩...



排列组合长期以来都是公务员考试行测科目中数量关系部分的一个难点，这种类型试题给人感觉比较复杂，感觉不知道怎么开始。其实就是常说的有一组元素有明确的固定位置，打乱顺序后重新排列，错位重排就是指重新排列后元素与固定位置均未能一一对应，求方式的总数。

1、D（1）=0

2、D（2）=1

3、D（3）=2

4、D（4）=9

5、D（5）=44

6、D（6）=265

7、D（7）=1854

【由来】：

错位重排问题是一种很难理解的复杂数学模型是伯努利和欧拉在错装信封时发现的，因为这个原因又称伯努利-欧拉装错信封问题。

错位重排问题的通项公式：

已经D1=0，D2=1，Dn=（n-1）（Dn-2+Dn-1），求Dn。

Dn = (n-1)Dn-1 + (n-1)Dn-2

Dn-nDn-1 = -[Dn-1 - (n-1)Dn-2]

设Dn-nDn-1=Cn

Cn=(-1)^n

则 Dn = (-1)^n + nDn-1

两边同除(-1)^n

设Dn/(-1)^n=Bn

Bn = 1 - nBn

两边同除n!

设Bn/n!=An

An+An-1=1/n!..................(1)

An-1+An-2=1/(n-1)!.........(2)

............

A2+A1=1/2!......................(n-1)

A1=D1=0..........................(n)

(1)-(2)+(3)..............(n)得

一个元素没有全错位排列，两个元素的全错位排列有一种，三个元素的全错位排列有两种，四个元素的全错位排列有九种，五个元素的全错位排列有44种

f(n)=(n-1){f(n-1)+f(n-1)}

错位重排是指把元素和位置的对应关系重新排列且不可以恢复原本的位置关系。如：把编号是1、2、…、n的n封信，装入编号为1、2、…、n的n个信封，要求每封信和信封的编号不一样，有多少种装法。

一、错位重排定义：

举个栗子，假设有4个人，每个人有一个书包，现4人从这4个书包中随机背起一个，结果恰好每人背的都不是自己的书包，即为错位重排。（即把每个人都排到了和以前不一样的位置上）

这是排列组合中的一个很特殊的题型，大多数情况下需我们记住对应的结论。（超级难受）

二、错位重排的结论

假设有n个对象，则错位重排的情况数用Dn表示，需各位考生了解的是：

D2=1，D3=2，D4=9，D5=44。

（公务员没有考过超越5个对象的情况）

扩展资料：

基本出题形式

1、标准题型

【例题一】现有5瓶不一样浓度的溶液和相对应的5个标签，小明随意的把5个标签分别贴到了5瓶溶液上，王教授发现恰好都贴错了，贴错的可能情况数有多少种？

A.2

B.9

C.20

D.44

【分析】是n=5的错位重排，D5=44。

2、变形：部分贴错

【例题二】现有5瓶不一样浓度的溶液和相对应的5个标签，小明随意的把5个标签分别贴到了5瓶溶液上，王教授发现恰好贴错了3个，贴错的可能情况数有多少种？

A.2

B.9

C.20

D.44

【分析】先从5个瓶子中选出贴错的3个，有C（5，3）=10种，贴错的这3个满足错位重排，即D3=2，故共有10×2=20种。

参考资料：