Every permutation has a representation as a product of disjoint cycles. With suitable consideration for the commutativity of factors, this representation is unique. Since a derangement is a permutation with no fixed points, i.e. in which each disjoint cycle has length greater than one, all derangements of $\{1,2,\ldots,n\}$ can be constructed from the partitions of the set having parts of size at least two.
Indeed, given such a partition, say having $m$ parts of sizes $k_1+k_2+\ldots+k_m=n$ and each $k_i\ge2$, there will be $\prod_{i=1}^m (k_i-1)! $ corresponding derangements.
Turning this observation into an explicit algorithm provides an opportunity to discuss both generating integer partitions of $n$ and generating set partitions of $\{1,2,\ldots,n\}$.
- Input positive integer $n$. If $n \lt 2$, exit (no derangements).
- Generate all the integer partitions of $n$ whose smallest part is at least two, i.e.: $$k_1+k_2+\ldots+k_m=n$$ where $k_1\ge k_2\ge \ldots \ge k_m \ge 2$.
- For each such integer partition of $n$, generate all the set partitions of $\{1,2,\ldots,n\}$ whose subsets have corresponding sizes $k_i$.
- For each such set partition of $\{1,2,\ldots,n\}$, generate all the disjoint cyclic decompositions where the cycles have the parts of the set partition as their underlying disjoint sets.
- Output such a permutation (derangement).
Each step between the first one and the fifth one can be accomplished in at least one and possibly in multiple ways. Since each step depends on the results of the previous step, we generate the outputs as leaves of a tree of dependent choices. To output all possible derangements requires backtracking through this tree of choices, i.e. when all possibilities for a given step are exhausted, control passes back the the previous step to continue generation.
To do: Notes on implementation of steps 2,3,4,5
We do not have to pick the last element. We can pick other element as well and the proof will still work.
If $j_n = n$, then it is not a derangement anymore. Hence $j_n = k$ where $k \neq n$.
We can change the proof.
You can pick a particular index $p \in \{ 1, \ldots, n\}$
For any derangement $(j_1, j_2, \ldots, j_n)$, we have $j_p \neq p$. Let $j_p = k$, where $k \in \{1, 2, \ldots, n\}\setminus \{p\}$. We now break the derangements on $n$ elements into two cases.
Case $1$: $j_k = p$
Case $2$: $j_k \neq p$.
Best Answer
Use the fact that $D_{n,k} = ^nC_k.D_{n-k,0}$ and $D_{n,0} = round (\frac{n!}{e})$.
So $D_{n,k} = {n\choose k} \times round (\frac{(n-k)!}{e})$