錯排問題

錯排問題是組合數(shù)學中的問題之一。一個含有n個元素的排列，若這個排列中所有的元素都不在自己原來的位置上，那么這樣的一個排列就是原排列的一個錯排。

求解方法

對于情況較少的排列，可以使用枚舉法。

當n=1時，只有一種排列情況且不是錯排，D1=0；

當n=2時，全排列有兩種，1、2和2、1，后者是錯排，D2=1；

當n=3時，全排列有3！=6種，錯排有兩種，D3=2；

D4=9、D5=44、D6=265……

對于排列數(shù)比較多時，枚舉的方法就不合適了，可以用遞推思想推導。

當n>=3時，我們假設數(shù)字n在第k個位置上，這時k必須滿足1≤k≤n-1。此時有兩種情況：

1.數(shù)字k在第n個位置上時，n和k唯一確定了，且滿足錯排條件。剩下n-2個數(shù)字，即Dn-2；

2.數(shù)字k不在第n個位置上，此時有n-1個數(shù)字的錯排情況，即Dn-1；

所以對于每一種確定的k值，有Dn=Dn-1+Dn-2，又由于k有n-1個符合的值，所以最終結論是

Dn=(n-1)*(Dn-1+Dn-2)。