誰も自分の出したプレゼントを貰わない場合の数をa(n)通り、
逆に誰かが貰ってしまう場合の数をb(n)通りとすると
a(n)+b(n)=n!が成り立つ
んで
n!=(n-1){(n-1)!+(n-2)!}
a(n)=(n-1){a(n-1)+a(n-2)}が成り立つから
b(n)=(n-1){b(n-1)+b(n-2)}も成り立つ

逆の場合も同じ漸化式が成り立つのは綺麗