Solve recurrence equation: $a_{n}=(n-1)(a_{n-1}+a_{n-2})$ Find and solve recurrence equation $a_{n}$, where $a_{n}$ is the number of derangement in permutation $\pi\in S_{n}$, and $\forall_{i\in \mathbb{N}_{n}}\pi(i)\ne i$.
I managed to find the equation:
$$
a_{n} =
\begin{cases}
1,  &amp; \text{if $n$ = 0} \\
0, &amp; \text{if $n$ = 1}  \\
(n-1)(a_{n-1}+a_{n-2}), &amp; \text{if $n\ge2$}
\end{cases},
$$
but I don't know how to solve it. Only managed to get to this:
$A(x) = 1+\sum^\infty_{n=0}{(n+1)a_{n+1}x^{n+2}}+\sum^\infty_{n=0}{(n+1)a_{n}x^{n+2}}$.
the solution is given by the Gamma-function, $$a(n)=\frac{\Gamma (n+1,-1)-\Gamma
   (2,-1) \Gamma (n+1)}{e-\Gamma
   (2,-1)}$$
the solution is given by the Gamma-function, $$a(n)=\frac{\Gamma (n+1,-1)-\Gamma
   (2,-1) \Gamma (n+1)}{e-\Gamma
   (2,-1)}$$