Number of permutations with a certain number of fixpoints

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
ACBD
DBCA


I tried to find a solution by creating a recurrence relation, but I failed. Does anybody know a solution?

-
first try to compute the number of elements in the group of permutations of $n$ elements that don't fix any element (i.e. the case where $k=0$). –  Louis La Brocante May 29 '12 at 22:47

This could be answered by the formula of derangements. Choose the points that are going to be fixed, then choose a derangement of the others. There are $\binom nk$ ways to choose the fixed points, and there are precisely $!(n-k)$ (the "de Montmort" numbers are noted !n instead of n! for the factorial, which precisely count the number of derangements), hence you are looking at

$$\binom nk \times !(n-k).$$ http://en.wikipedia.org/wiki/Derangement

A formula to compute $!n$ is given by

$$!n = n! \sum_{i=0}^{n} \frac{(-1)^i}{i!}.$$

Hope that helps,

-
There are many other formulas to compute derangements, and the problem is well-known and extensively studied. –  Patrick Da Silva May 29 '12 at 22:52