錯位排列公式的D是什么？公式是d[n]=（n-1）（d[n-1]d[n-2]）假設(shè)n個數(shù)字從1到n，n個位置（或封套）從P1到PN。數(shù)字分為兩類：1~（n-1）和n.第一類分為（n-1）個數(shù)字。對于每

錯位排列公式的D是什么？

公式是

d[n]=（n-1）（d[n-1]d[n-2]）

假設(shè)n個數(shù)字從1到n，

n個位置（或封套）從P1到PN。

數(shù)字分為兩類：1~（n-1）和n.

第一類分為（n-1）個數(shù)字。對于每個數(shù)字，考慮幾個排列。假設(shè)現(xiàn)在考慮的是k

顯然，k不能放在pK上（否則就不滿足位錯的要求）

公式的第一部分

考慮把k放在PN上，把N放在pK上，這樣N和k就滿足位錯的要求了。

在這種情況下，有多少個排列？因為N個數(shù)中有兩個是固定的，它等價于剩余N-2個數(shù)的置換數(shù)：D[N-2

]公式的第二部分

這部分有點難理解。

同樣，K仍然放在PN上，但此時n也不允許放在PK上，也就是說，n也放在剩余的n-2個數(shù)字上交錯排列。此時，存在d[n-1]個組合。

這里的關(guān)鍵是n-1數(shù)字排列錯誤。所謂錯誤排列的數(shù)字有對應(yīng)的對（原始位置）。除K外，其它數(shù)的原位置都是它們的數(shù)。但是N的初始位置在哪里呢？

在K處。也就是說，在這種情況下，數(shù)字n不允許出現(xiàn)在K的位置上。

這有兩種含義：

在這種情況下，它與D[n-1

]的情況完全一致。這樣，n就不允許出現(xiàn)在K處，這與公式第一部分的量不重復(fù)。同時，它與第一種情況是完全互補(bǔ)的

merge

因為有n-1（公式的第一部分，公式的第二部分），最后的公式是

d[n]=（n-1）（d[n-1]d[n-2]）