先看一道例題:

A,B,C三人寫了a,b,c三張賀卡，要求每人拿不到自己的賀卡，求分配方法總數(shù)

樸實(shí)無(wú)華的想法:

A?b c B?c a C?c b 所以符合題意的分配方法總數(shù)為2種

非常簡(jiǎn)單的題目。同理，如果是四個(gè)人寫了四張賀卡，我們可以數(shù)得是九種。但是當(dāng)五個(gè)人寫了五張，六個(gè)人寫了六張乃至一百個(gè)人寫了一百?gòu)垥r(shí)，事情開(kāi)始不太好處理了。

怎么辦呢？

以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中的一個(gè)必然替換了a，放在A的下面，這一替換有四種情況

挑其中一種情況分析:

假設(shè)d替換了a,放在A的下面

那么問(wèn)題就集中在了BCDE這四人中:怎么在他們中分配b,c,a,e這四張賀卡？

再次分類:

1.若a賀卡給了D

此時(shí)情況就簡(jiǎn)單了，問(wèn)題變成B,C,E三人如何分配b,c,e三張賀卡

在這里，假設(shè)三個(gè)人符合題意的分配方式總數(shù)為a3，n個(gè)人符合題意的分配方式總數(shù)為an

很明顯，這一情況有a3種分配方法

2.若a賀卡沒(méi)有給D

我們來(lái)看看a賀卡在B,C,D,E中此時(shí)具有的性質(zhì)吧:

①不能給D ②要給B,C,E中的任意一個(gè)

再創(chuàng)立一個(gè)情境Q:有B,C,D,E四個(gè)人寫了b,c,d,e四張賀卡，要求每人拿不到自己的賀卡

很明顯這一情境的分配方法數(shù)為a4

我們也來(lái)看看d賀卡在此情境Q下的性質(zhì):

①不能給D ②要給B,C,E中的任意一個(gè)

很容易發(fā)現(xiàn)，討論情況2中的a和情境Q中的d在同一環(huán)境下（都是BDE三人寫了bde三張賀卡）具有相同的性質(zhì)，完全可以認(rèn)為討論情況2就是情境Q

所以情況2有a4種情況

合在一起，總共就有4（a3+a4）種情況

以此類推

n個(gè)人寫了n張賀卡，要求每人拿不到自己的賀卡，分配方法總數(shù)an可推得

an=（n-1）(a

n-2

+a

n-1

)