3
$\begingroup$

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?

  • 0
    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$).2012-05-29

1 Answers 1

1

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,

  • 0
    There are many other formulas to compute derangements, and the problem is well-known and extensively studied.2012-05-29