-
錯排公式
鎖定
問題： 十本不同的書放在書架上。現重新擺放，使每本書都不在原來放的位置。有幾種擺法？
這個問題推廣一下，就是錯排問題，是組合數學中的問題之一。考慮一個有n個元素的排列，若一個排列中所有的元素都不在自己原來的位置上，那麼這樣的排列就稱為原排列的一個錯排。 n個元素的錯排數記為D(n)。 研究一個排列錯排個數的問題，叫做錯排問題或稱為更列問題。
錯排問題最早被尼古拉·伯努利和歐拉研究，因此歷史上也稱為伯努利-歐拉的裝錯信封的問題。這個問題有許多具體的版本，如在寫信時將n封信裝到n個不同的信封裏，有多少種全部裝錯信封的情況？又比如四人各寫一張賀年卡互相贈送，有多少種贈送方法？自己寫的賀年卡不能送給自己，所以也是典型的錯排問題。
- 中文名
- 錯排公式
- 外文名
- Staggered formula
- 所屬類別
- 組合數學
- 學科類型
- 數學
- 日文名
- せい併公式
- 韓文名
- 미스 공식
錯排公式遞推公式
當n個編號元素放在n個編號位置，元素編號與位置編號各不對應的方法數用
表示，那麼
就表示n-1個編號元素放在n-1個編號位置，各不對應的方法數，其它類推.
第一步，把第n個元素放在一個位置，比如位置k，一共有n-1種方法；
第二步，放編號為k的元素，這時有兩種情況：⑴把它放到位置n，那麼，對於剩下的n-1個元素，由於第k個元素放到了位置n，剩下n-2個元素就有
種方法；⑵第k個元素不把它放到位置n，這時，對於這n-1個元素，有
種方法；
綜上得到
特殊地，D(1) = 0, D(2) = 1.
下面通過這個遞推關係推導通項公式：
為方便起見，設
則
,
.
即
於是有
.
因此將
代入並將這些式子相加，可得
因此
此即錯排公式。
錯排公式容斥原理
用容斥原理也可以推出錯排公式：
正整數1, 2, 3, ……, n的全排列有 n! 種，其中第k位是k的排列有 (n-1)! 種，由於所求的是錯排的種數，所以應當減去這些排列；但是此時把同時有兩個點放對位置的排列多排除了一次，應補上；在補上時，把同時有三個數不錯排的排列多補上了一次，應排除；……；繼續這一過程，得到錯排的排列種數為
即
.
其中，
表示連加符號，k=2~n是連加的範圍；0! = 1，可以和1!相消。
錯排公式二項式反演
利用二項式反演我們更為簡便的推導出一個通項公式。
考慮令
表示
個數字任意放的方案數，
表示
個數字都不放在自己位置上的方案數，通過枚舉不在自己位置上的數字的個數容易得到
錯排公式簡化公式
證明：
由於
,
其中
是餘項，等於
，且u∈(-1, 0).
所以，
, u∈(-1, 0).
而
，可知對
，該餘項（的絕對值）均小於1/2。
因此，無論
是正是負，
的整數部分都一定與
相同。
對於比較小的n，結果及簡單解釋如下：
