错位排列问题

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

相关推荐

  • 分组分配的变异情况

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

    2021年2月9日
    3661
  • 导函参变可分离,特殊一般来讨论

    导函参变可分离,特殊一般来讨论。 解超不等造函数,单调零点把题解。 【例题】已知函数\(f(x) = \ln x + a{x^2} – (a + 2)x,a \in R…

    2021年2月10日
    3480
Insert math as
Block
Inline
Additional settings
Formula color
Text color
#333333
Type math using LaTeX
Preview
\({}\)
Nothing to preview
Insert