錯(cuò)排問(wèn)題公式

錯(cuò)排問(wèn)題

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

求解方法

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

當(dāng)n=1時(shí)，只有一種排列情況且不是錯(cuò)排，D1=0；

當(dāng)n=2時(shí)，全排列有兩種，1、2和2、1，后者是錯(cuò)排，D2=1；

當(dāng)n=3時(shí)，全排列有3！=6種，錯(cuò)排有兩種，D3=2；

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

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

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

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

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

所以對(duì)于每一種確定的k值，有Dn=Dn-1+Dn-2，又由于k有n-1個(gè)符合的值，所以最終結(jié)論是

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