錯排公式:遞推公式,容斥原理,二項式反演,簡化公式,

問題：十本不同的書放在書架上。現重新擺放，使每本書都不在原來放的位置。有幾種擺法？

這個問題推廣一下，就是錯排問題，是組合數學中的問題之一。考慮一個有n個元素的排列，若一個排列中所有的元素都不在自己原來的位置上，那么這樣的排列就稱為原排列的一個錯排。 n個元素的錯排數記為D(n)。研究一個排列錯排個數的問題，叫做錯排問題或稱為更列問題。

錯排問題最早被尼古拉·伯努利和歐拉研究，因此歷史上也稱為伯努利-歐拉的裝錯信封的問題。這個問題有許多具體的版本，如在寫信時將n封信裝到n個不同的信封里，有多少種全部裝錯信封的情況？又比如四人各寫一張賀年卡互相贈送，有多少種贈送方法？自己寫的賀年卡不能送給自己，所以也是典型的錯排問題。

基本介紹

中文名：錯排公式
外文名：Staggered formula
所屬類別：組合數學
學科類型：數學
日文名：せい併公式
韓文名：미스 공식

遞推公式,容斥原理,二項式反演,簡化公式,

遞推公式

當n個編號元素放在n個編號位置，元素編號與位置編號各不對應的方法數用D(n)表示，那么D(n-1)就表示n-1個編號元素放在n-1個編號位置，各不對應的方法數，其它類推.

第一步，把第n個元素放在一個位置，比如位置k，一共有n-1種方法；

第二步，放編號為k的元素，這時有兩種情況：⑴把它放到位置n，那么，對於剩下的n-1個元素，由於第k個元素放到了位置n，剩下n-2個元素就有D(n-2)種方法；⑵第k個元素不把它放到位置n，這時，對於這n-1個元素，有D(n-1)種方法；

綜上得到

D(n) = (n-1) [D(n-2) + D(n-1)]

特殊地，D(1) = 0, D(2) = 1.

下面通過這個遞推關係推導通項公式：

為方便起見，設D(k) = k! N(k), k = 1, 2, …, n,

則N(1) = 0, N(2) = 1/2.

n ≥ 3時，n! N(n) = (n-1) (n-1)! N(n-1) + (n-1)! N(n-2)

即 nN(n) = (n-1) N(n-1) + N(n-2)

於是有N(n) - N(n-1) = - [N(n-1) - N(n-2)] / n = (-1/n) [-1/(n-1)] [-1/(n-2)]…(-1/3) [N(2) - N(1)] = (-1)^n / n!.

因此

N(n-1) - N(n-2) = (-1)^(n-1) / (n-1)!,

N(2) - N(1) = (-1)^2 / 2!.

相加，可得

N(n) = (-1)^2/2! + … + (-1)^(n-1) / (n-1)! + (-1)^n/n!

因此

D(n) = n! [(-1)^2/2! + … + (-1)^(n-1)/(n-1)! + (-1)^n/n!].

此即錯排公式。

容斥原理

用容斥原理也可以推出錯排公式：

正整數1, 2, 3, ……, n的全排列有 n! 種，其中第k位是k的排列有 (n-1)! 種；當k分別取1, 2, 3, ……, n時，共有n*(n-1)!種排列是至少放對了一個的，由於所求的是錯排的種數，所以應當減去這些排列；但是此時把同時有兩個數不錯排的排列多排除了一次，應補上；在補上時，把同時有三個數不錯排的排列多補上了一次，應排除；……；繼續這一過程，得到錯排的排列種數為

D(n) = n! - n!/1! + n!/2! - n!/3! + … + (-1）^n*n!/n! = ∑(k=2~n) (-1)^k * n! / k!,

即D(n) = n! [1/0! - 1/1! + 1/2! - 1/3! + 1/4! + ... + (-1)^n/n!].

其中，∑表示連加符號，k=2~n是連加的範圍；0! = 1，可以和1!相消。