错位排列问题

错位排列问题:编号为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/

(0)
上一篇 2021年2月10日 01:39
下一篇 2021年2月10日

相关推荐

  • 2023年四省联考数学第16题

    【2023年四省联考数学第16题】下图为一个开关阵列,每个开关只有“开”和“关”两种状态,按其中一个开关\(1\)次,将导致自身和所有相邻的开关改变状态.例如,按\((2,2)\)…

    2023年4月12日
    1660
  • 分组分配的变异情况

    【例】将编号为1,2,3,4,5的5个小球全部放入A、B、C三个盒子内,若每个盒子不空,且放在同一个盒子内的小球编号不相连,则不同的方法种数有(    ) A.42        …

    2021年2月9日
    3981