关于错位排列的问题

一、错位重排定义：

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

这是排列组合中的一个非常特殊的题型，一般需要我们记住对应的结论。（很难受）

二、错位重排的结论

如果有n个对象，则错位重排的情况数用Dn表示，需要大家了解的是：

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

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

扩展资料：

基本出题形式

1、标准题型

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

A.2

B.9

C.20

D.44

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

2、变形：部分贴错

例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种。

参考资料：

根据错排公式计算5个元素的错排就是44。

一个元素的错排为0个。两个元素的错排为1个，三个元素的错排为2个，四个元素的错排为9，五个元素的错排为44。错排具有简单的计算公式：D(n) = (n-1) [D(n-2) + D(n-1)]。

错位重排问题就比较特殊，因为该题型特征明显，错位重排问题也叫装错信封问题，这是源自于伯努利和欧拉在相互写信过程中所发现的，题目就是需要求出错位的方法数。只要大家理解推导过程，记住基本公式，就可以轻松解题。

错位重排问题：

基本公式：Dn =(n-1)×(Dn-2 +Dn-1)，其中D1=0，D2=1。

Dn表示n个数的错位重排的方法数。

公式推导：若有n个人，n个座位，错位重排。

(1)若n=1，1个人对应1个座位，无法错位，故D1=0。

(2)若n=2，2个人，2个座位，要实现错位，只能是如下的方式，故D2=1。

(3)对于n个人，n个座位，要实现错位，分步来操作。

第一步，先安排第1个的座位，第1个人选择的是第i个座位，有(n-1)种坐法。

第二步，安排剩下(n-1)个人的座位，分类来操作。

第一类，若第i个人选择第1个座位，有一种坐法，剩下的(n-2)个人，有(n-2)个座位错位重排，有Dn-2种坐法，共有1×Dn-2= Dn-2种坐法。

第二类，若第i个人选择不是第1个座位，即相当于除了第1 个人外，其余的(n-1)个人，(n-1)个座位，错位重排，共有Dn-1种坐法。

综上所述，根据计数原理可得，共有(n-1)×(Dn-2+ Dn-1)种坐法，即Dn =(n-1)×(Dn-2 +Dn-1)，其中D1=0,D2=1。