错排公式

题目

错排公式
第一步,把第n个元素放在一个位置,比如位置k,一共有n-1种方法;
第二步,放编号为k的元素,这时有两种情况.1,把它放到位置n,那么,对于剩下的n-2个元素,就有M(n-2)种方法;2,不把它放到位置n,这时,对于这n-1个元素,有M(n-1)种方法;
第二步中的第2中情况不是包含把k号元素放在n的位置上了吗,也就是第二步的第1种情况,

答案

1 ） k 号元素排在第 1
个位置,留下的 n - 2 个元素在与它们的编号集相等的位置集上“错排”,有 f(n -2)
种方法；
（ 2 ） k 号元素不排第 1 个位置,这时可将第 1 个位置“看成”第 k
个位置,于是形成（包括 k 号元素在内的） n - 1 个元素的“错排”,有 f(n - 1)
种方法.据加法原理,完成第二步共有 f(n - 2)+f(n - 1) 种方法.