N个人分N个贺卡,每人拿一个,不拿自己的,有几种分法.

问题描述:

N个人分N个贺卡,每人拿一个,不拿自己的,有几种分法.

这个叫全错排列问题,最早是由欧拉给出的答案.我们不妨设N个人的拿法为f(N),则f(N)=(N-1)[f(N-1)+f(N-2)].f(0)=0,f(1)=1.这个递推公式是很容易证明的. 证明如下: 设N个人为a,b,c,d...,N张卡为A,B,C,D... 若a拿b的卡B,...