新浪博客

小学奥数专题讲解之排列与组合中错排问题

2015-02-23 17:10阅读：

http://blog.sina.cn/dpool/blog/u/1248232937

小学奥数专题讲解之排列与组合中错排问题
本文来自雪帆奥数学习博客：http://blog.sina.com.cn/aoshu

甲，乙，丙，丁，戊，五个人各自分别制作了一份新年贺卡，然后各自送给这五个人中的一个而不是自己，且最

后谁都能得到贺卡，共有多少种送出的方法？


雪帆奥数王老师分析与提示：
这种题一般都采用树形图结合枚举处理。

枚举方法如下（为了方便起见，A对着1，B对着2，依次类推）
A对着2，3，4，5，种类是一样的，所以只要枚举其中一类，然后乘以4即可。

A-2 （A-3，4，5，这四种是对称的，只枚举一种情况，到时候乘以4即可）
B-1
B-3，4，5（这三种也是对称的，可以只枚举B-3，到时候乘以3即可）
C-4，5，×2 ） C-1 C-4 （C-5 ， ×2）
D-5 D-5 D-5
E-3 E-4 E-1
所以方法为
【（1×2）+（1+1×2）×3】×4=44 种

但是人数较多怎么办呢？能不能找到一定的规律呢？
探讨方法如下：
先从1个人开始讨论，如果是一个人制作了一份新年贺卡，很显然只能是0种

如果是两个人，那么他们可以互相交换，1种方法，
如果是三个人，通过枚举，也只有2种方法，继续讨论递推关系

设n个不同元素分别标号1，2，3，……，n，要求它们分别被放入标号为1，2，3，……，n的位置上，一个位置

有且只有一个元素，且元素的标号与位置的标号不能相同，记其方法数为 （排列与组合）错排问题

从中任取一个元素，不妨取1号元素，还剩n-1个元素，再从这n-1个元素对应的位置中选一个，共n-1种方法

假设选取的位置是2号位，以下分两种情况

第一种，1号元素放入2号位置且2号元素也放入1号位置，此时剩下n-2个元素继续错排，共 （排列与组合）错排问题种方法

第二种，1号元素放入2号位置但2号元素不放入1号位置，既然2号元素不放入1号位置，不妨把2号元素看作1号元

素，于是等价于新的1号元素不放入1号位置（雪帆老师提示：好好理解这句话的意思），那么剩下n-1个元素继续错排，共 （排列与组合）错排问题种方法

于是得到递推式 （排列与组合）错排问题

（排列与组合）错排问题
所以，三个元素错排是(3-1)(0+1)=2（种）方法，四个元素错排是(4-1)(1+2)=9（种）方法，四个元素错排有
五个元素错排是(5-1)(2+9)=44（种）方法，……

错排递推公式
F（n）=（n-1）（F（n-1）+F（n-2）） F表示方法。F（n）表示n个物体错排的种类

练习题：
糊涂的课代表发作业，某个小组6个同学都拿到了自己组里别人的作业，问：他们之间作业的分配方式有（）种？


如有问题请留言，如需上课请联系王老师，授人以渔 13683301267 网络课一对一，加qq 87982671 注明我要学奥数。。


我的更多文章

下载客户端阅读体验更佳

APP专享