Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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)

share|improve this question

marked as duplicate by Mike Spivey, Asaf Karagila, Byron Schmuland, Alex Becker, David Mitra Jan 4 '12 at 21:49

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

    
Elvis, you answer is not correct, becouse you are considering not $P(P = p) $ but $P(P \ge p) $ –  Aslan986 Jan 4 '12 at 21:31
    
You should probably say you want permutations with exactly $p$ objects in correct position. –  Thomas Andrews Jan 4 '12 at 21:43
    
@Aslan986: perhaps you wanted that comment on Elvis's answer? The comment fields for the question itself and the individual answers are separate. –  Willie Wong Jan 5 '12 at 12:02

4 Answers 4

up vote 1 down vote accepted

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!}$.

share|improve this answer

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)

share|improve this answer

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)).$$

share|improve this answer

Let $!k$ be the number of arrangements of $k$ ordered elements such that none of them are in correct position. (These are so-called derangements.) Then your count is the number of ways of picking $p$ points out of $n$, placing the correct numbered element in those slots, times the number of derangements on the remaining $n-p$ points. So your probability is $\frac{{n\choose p}!(n-p)}{n!}$

There are a number of formulas for derangements at Wikipedia.

Using that $!k = \frac{k!}{e} + \delta_k$ where $|\delta_k|\leq \frac{1}{2}$, and expanding ${n\choose p}=\frac{n!}{p!(n-p)!}$, you get that the probability is:

$$\frac{1}{ep!}(1+\delta_{n-p}')$$

Where $\delta_{k}' = \frac{e\delta_k}{k!}$, and hence it tends to be very small when $k$ is large, so we get that, when $n$ is relatively bigger than $p$, the probability is close to $\frac{1}{ep!}$

share|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.