贺卡问题的一个解答

同室四人,各写一张贺卡,先集中起来,然后每人从中拿一张别人送的贺卡,问四张贺卡的不同分配方式有几种?这称之谓“贺卡问题”.这是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)=3f(3) f(2)].人数为n时,不失一般性,n人用A_1、A_2、A_3……A_n表示,对应的各自的贺卡用a_1,a_2,