Given a set of $n$ mutually distinct elements, how many permutations are there such that exactly $k$ of the permuted elements stay at the same place?
Example
Let's take the set $\{A,B,C,D\}$. The original permutation is $A,B,C,D$. There are $5$ permutations where exactly $2$ elements remain at their place:
ABDC ADCB ACBD DBCA CBAD
I tried to find a solution by creating a recurrence relation, but I failed. Does anybody know a solution?