错位排列问题

错位排列问题:编号为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:显性条件和目标信息如何翻译? 如\(OA \bot OB\)翻译成:\({k_{OA}}…

    2021年2月10日
    4440
  • 如何当堂掌握知识

    总有一些同学觉得学习很吃力,其实,这些同学是因为没有掌握科学的学习方法。就说上课吧,有的同学上课以听懂为满足,认为记忆是课后的事。但是课下作业一多,专门复习的机会就很少了。还有些同…

    2021年11月20日
    8130