问题: 十本不同的书放在书架上。现重新摆放,使每本书都不在原来放的位置。有几种摆法?这个问题推广一下,就是错排问题,是组合数学中的问题之一。考虑一个有n个元素的排列,若一个排列中所有的元素都不在自己原来的位置上,那么这样的排列就称为原排列的一个错排。n个元素的错排数记为D(n)。

公式:d(n)=(n-1)*(d(n-1)+d(n-2))

推导:

第一步:将元素1排入,共(n-1)种方法,假设排入了位置k。

第二步:排元素k,这里分两种情况。

1.元素k排入位置1,则这样的话其余n-2个元素和n-2个位置共d(n-2)种错排。

2.元素k不排入位置1,然后这样考虑:先把位置k及其上的元素1撤去,然后认为元素k原本在位置1,这样的话共n-1个位置n-1个元素共d(n-1)中错排。

认为元素k原本在位置1 这实际上是作了一个映射,不改变其他元素及位置的关系。这个需要好好画图理解一下。实际上我们容易想象的是初始元素k排在位置k,实际上初始完全可以打乱,比如位置1~5分别对应元素23514,然后5个元素分别映射到【元素new】12345,位置和【元素new】的每一个排列都一一对应原位置及元素。要求元素2不在位置1…元素4不在位置5就相当于【元素new】 k不在位置k。

参考
https://baike.baidu.com/item/错排公式

https://www.cnblogs.com/ECJTUACM-873284962/p/7620370.html