Probability that n numbered objects placed in random order have p objects in the correct position 
Possible Duplicate:
How many fixed points in a permutation 

Suppose we have a collection of n objects, numbered from 1 to n.  These objects are placed in a random order.
What is the probability that p of the objects are in the position in the order corresponding to their order.  
For instance, 
For n=3, 1-2-3 has all objects in the correct position, p = 3, and has probability P(p=3) = 1/3! = 1/6.
However P(p=2) = 0
P(p=1) = 3/3! = 1/2.   (1-3-2, 3-2-1, 2-1-3)
P(p=0) = 2/3!. (2-3-1, 3-1-2)
 A: Let’s denote $P$ the random variable defined by $P = {}$ number of objects in correct position. We compute $\mathbb P(P = p)$ by counting the number of permutations "with $p$ fixed points" (just an other way to say "$p$ objects in correct position).


*

*You have a total of $n!$ permutations ;

*You have ${n \choose p}$ choices for the indices of the objects in correct position ;

*The remaining $n-p$ objects have to be permutated without fixed points. This kind of permutation is called a derangement. The number of derangement is denoted by $!(n-p)$ and is computable via an induction formula or with $!(n-p) = (n-p)!\sum_{i=0}^{n-p} {(-1)^i \over i!}$ (same reference).

*The probability $\mathbb P(P=p)$ is then
$$ \mathbb P(P=p) = { {n \choose p} \cdot !(n-p) \over n! } = {!(n-p) \over (n-p)! p! }.$$
When $n-p \gg 1$ we have ${!(n-p) \over (n-p)!} \simeq e^{-1}$, so  $\mathbb P(P=p) \simeq {1 \over e \cdot p!}$.
A: if a permutation $\pi\in S_n$ has exactly $k$ fixed points, you can consider it a permutation in $S_{n-k}$ with no fixed points (a derangement).    so you choose your fixed points ${n \choose k}$ and multiply by the number of derangements on $n-k$ elements, $(n-k)!\sum_{i=0}^{n-k}(-1)^i/i!$, then divide by $n!$ for the probability
$$
\frac{1}{k!}\sum_{i=0}^{n-k}\frac{(-1)^i}{i!}
$$
so for $n=3$ as you gave you get
$$
k=0:1/3, k=1: 1/2, k=2: 0, k=3: 1/6
$$
as desired (as a check i guess)
A: We will count the number of ways to have exactly $p$ objects in the correct places. Then one only needs to divide by $n!$ to find the probability.
Which $p$ objects are in the correct place? These can be chosen in $\binom{n}{p}$ ways. Now for every such choice, we must arrange the remaining $n-p$ objects so that none of them is in the correct place.
For any $k$, the number of arrangements of a set of $k$ numbers so that none of them is in the correct place is called the number of derangements of $k$.  The subject of derangements is extensively discussed at the preceding link.  One fairly common notation for the  number of derangements of an ordered set of cardinality $k$ is $!k$, though $D_k$, or $D(k)$, are also quite common.  
So the number of ways to do the arranging is
$$\binom{n}{p}(!(n-p)).$$
