高中数学:错排问题

先看一道例题:

A,B,C三人写了a,b,c三张贺卡，要求每人拿不到自己的贺卡，求分配方法总数

朴实无华的想法:

A b c B c a C c b 所以符合题意的分配方法总数为2种

非常简单的题目。同理，如果是四个人写了四张贺卡，我们可以数得是九种。但是当五个人写了五张，六个人写了六张乃至一百个人写了一百张时，事情开始不太好处理了。

怎么办呢？

以A,B,C,D,E五人分别写了a,b,c,d,e五张贺卡为例:

A B C D E a b c d e 首先，我们知道，a不能放在A的下面，这意味着b,c,d,e中的一个必然替换了a，放在A的下面，这一替换有四种情况

挑其中一种情况分析:

假设d替换了a,放在A的下面

那么问题就集中在了BCDE这四人中:怎么在他们中分配b,c,a,e这四张贺卡？

再次分类:

1.若a贺卡给了D

此时情况就简单了，问题变成B,C,E三人如何分配b,c,e三张贺卡

在这里，假设三个人符合题意的分配方式总数为a3，n个人符合题意的分配方式总数为an

很明显，这一情况有a3种分配方法

2.若a贺卡没有给D

我们来看看a贺卡在B,C,D,E中此时具有的性质吧:

①不能给D ②要给B,C,E中的任意一个

再创立一个情境Q:有B,C,D,E四个人写了b,c,d,e四张贺卡，要求每人拿不到自己的贺卡

很明显这一情境的分配方法数为a4

我们也来看看d贺卡在此情境Q下的性质:

①不能给D ②要给B,C,E中的任意一个

很容易发现，讨论情况2中的a和情境Q中的d在同一环境下（都是BDE三人写了bde三张贺卡）具有相同的性质，完全可以认为讨论情况2就是情境Q

所以情况2有a4种情况

合在一起，总共就有4（a3+a4）种情况

以此类推

n个人写了n张贺卡，要求每人拿不到自己的贺卡，分配方法总数an可推得

an=（n-1）(a

n-2

+a

n-1

)