let $D_n$ be the number of permutations of $\{1,2,3,.....n\}$ which leave no element fixed.

Question

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.

Answer 1

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.

Answer 2

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})$.