let $D_n$ be the number of permutations of $\{1,2,3,.....n\}$ which leave no element fixed. Let $n\geq2$ and let $D_n$ be the number of permutations of $\{1,2,3,\dots,n\}$ which leave no element  fixed. How to write an expression for $D_n$ in terms of $D_k$? I don't know how to start. Please help.
 A: There are several ways to express $D_n$ in terms of earlier $D_k$. We describe one of them.
Suppose that a permutation $\pi$ leaves no element of $\{1,2,\dots,n\}$ fixed. Then $\pi$ takes $n$ to some element $j\lt n$. There are $n-1$ choices for $j$.
Take a fixed choice $j$. Maybe $\pi$ sends $j$ to $n$. Then there are by definition $D_{n-2}$ permutations of our set minus $n$ and $j$ that leave no element fixed.
Or maybe $\pi$ takes $j$ to some object other than $n$. In that case, make a new permutation $\pi'$ of $\{1,2,\dots,n-1\}$ by removing $n$ and letting $\pi$ stay unchanged, except that whoever is mapped by $\pi$ to $n$ is now mapped to $j$. Every permutation of $\{1,2,\,\dots,n-1\}$ that leaves no element fixed is obtained in this way. Thus there are $D_{n-1}$ permutations of this type.
It follows that $D_n=(n-1)(D_{n-2}+D_{n-1})$.
A: I'm not very sure, but as per my calculations, I think the following holds as well:
$ 1 + [n(n-1)/2! ]D_2 + [n(n-1)(n-2)/3!]D_3 + ... + [n!/n!]D_n = n!$  

The explaination for LHS:
The first term : number of permutations with $n$ fixed element.  
The second term : number of permutations with  $n-2$ fixed elements.  
The third term : number of permutations with $n-3$ fixed elements.  
...  
The last term : number of permutations with $0$ fixed elements.  
