错位排列问题：编号为1、2、3、…、n的n个元素放到编号为1、2、3、…、n的n个位置，要使元素与位置的编号各不相同，这种问题称为错位排列问题。设n个元素的错位排列数为\( a_n \)
解题步骤：
第一步：将元素1放入2-n中的某个位置，共有n-1种方法，不妨放入2号位置；
第二步：考虑元素2的放法，分类
（1）若元素2放在位置1，则剩下的3、4、…、n进行错位排列，其错位排列数为\( a_{n-2} \)
（2）若元素2不放在位置1，则把元素2改名为1，则1不放1、3不放3、…、n不放n，相当于n-1个元素的错位排列，其方法数为\( a_{n-1} \)
从而\( a_n=(n-1)(a_{n-2}+a_{n-1}) \)
【应用】
2个元素的错位排列数\( a_2=1 \)；
3个元素的错位排列数\( a_3=2 \)；
4个元素的错位排列数\( a_4=3(a_1+a_2)=9 \)；
5个元素的错位排列数\( a_5=4(a_3+a_4)=44 \)
原创文章，作者：leopold，如若转载，请注明出处：https://www.math211.com/2021/02/10/55/
