递推的方法推导错排算法:
当n个编号元素放在n个编号位置,元素编号与位置编号各不对应的方法数用
M(n)表示,
那么
M(n-1)就表示n-1个编号元素放在n-1个编号位置,各不对应的方法数,其它类推.
第一步：把第n个元素放在一个位置,比如位置k,一共有
n-1种方法;
第二步：放编号为k的元素,这时有两种情况.
①把它放到位置n,那么,对于剩下的n-2个元素,就有
M(n-2)种方法;
②不把它放到位置n,这时,对于这n-1个元素,有
M(n-1)种方法。
综上得到
|
M(n) = ( n - 1 ) [ M ( n - 2 ) + M ( n - 1 ) ]
特殊地，M ( 1 ) = 0 , M ( 2 ) = 1
|