信件错排

题目描述：有 N 个 信 和 信封，它们被打乱，求错误装信方式的数量。

有n个信和信封一一对应，现将n个信分别装入n个信封中，一直他们都没有装入应该装入的信封中，问：有多少种装法？

遗憾的是我目前还没有解得一个给n，就能立刻算出装法数的答案，但还是取得了一定的进展，在此分享。

设n个信和信封有A(n)种装法。形成数列{A(n)}

显而易见的是A(1)=0,A(2)=1

而n+1个信和信封的每一种装错装法都可以看作两种情况：

1.是n个信和信封的装错装法，将第n+1封信与前n封中的某一封对调

2.是n个信和信封中，某一个装对了，其余n-1个信和信封的装错装法，再将将第n+1封信与前n封中的装对的那一封对调

1.有n*A(n)种情况

2.有n*A(n-1)种情况

所以

A(n+1)=n*A(n)+n*A(n-1)=n*(A(n)+A(n-1))