贺卡问题的一个解答

同室四人,各写一张贺卡,先集中起来,然后每人从中拿一张别人送的贺卡,问四张贺卡的不同分配方式有几种?这称之谓“贺卡问题”.这是1993年的一道高考题.若将题中的“四人”推广到“n人”,则有几种不同的分配方式?许多数学同仁对此作出了研究和解答.我在这里也提供这个问题的一个解答.为了研究方便,不妨设贺卡张数为2、3、4、……n时,分配方式分别有f（2）、f（3）、f（4）、……f（n）种.容易推知:f（2）=1,f（3）=2,f（4）=9……首先,我们来证明递推公式:f（n）=（n-1）[f（n-1）+f（n-2）].当n=4时,显然有f（4）=3[f（3）+f（2）].人数为n时,不失一般性,n人用A1、A2、A3……An表示,对应的各自的贺卡用a1,a2,