# Probability and permutations

I performed an experiment in which an individual had to order 5 items (i.e. his "response" was something like $(3,2,1,4,5)$ or some other permutation). The correct ordering was $(1,2,3,4,5)$ and I want to know the probability of getting 1, 2, 3 or 5 of the numbers right by chance alone.

I know that the probability of getting all right by chance alone is $1/5!$, and I think that probability of getting 3 right is:

$$\frac{5 \choose 2}{5!}$$

Because if you get 3 right you are just "swapping" two items from $(1,2,3,4,5)$. I am having difficulty to deduce the rest of the probabilities. I have written an R code that simulates the process, so I have an approximate answer. I just wanted to know how to do it by hand.

Thank you in advance!

-
I'm sorry, I don't follow. I don't think it would be correct to "generalize" in that way. The probability of getting 2 or 3 right would be the same because ${5 \choose 2} = {5 \choose 3}$, and I think that is not correct. –  Jay D. May 10 '12 at 15:02

You calculated the probability of getting exactly $3$ right correctly, and of course the probability of getting all $5$ right. The probability of getting exactly $4$ right is clearly $0$. So we need only deal with the probabilities of $2$ right, $1$ right, and $0$ right.

A small comment about the number of permutations that have exactly $3$ right. Your analysis was good. I would, however, prefer to count as follows. There are $\binom{5}{3}$ ways to pick which three will be right. For each of these ways, we need to swap the other two, so the number is $\binom{5}{3}$. You chose instead the two items that would be swapped. Same count.

For exactly $2$ right, let us count the permutations that have exactly $2$ right. Which $2$ are right can be chosen is $\binom{5}{2}$ ways. For any such choice, that leaves three entries, say $a$, $b$, and $c$, that should be all wrong. Thus $a$ should be in one of positions $b$ or $c$. If $a$ is in position $b$, then $b$ must be in position $c$ (it cannot be in position $a$, for then $c$ would be forced into position $c$, which would make more than $2$ right). It follows that there are $\binom{5}{2}(2)$ permutations in which exactly $2$ are right.

For exactly $1$ right, the one that is right can be chosen in $\binom{5}{1}$ ways. That leaves $4$ items, which should all be in the wrong position. Where does $a$ go? There are $3$ possibilities, $b$, $c$, and $d$. The situation is symmetrical in $b$, $c$, and $d$, so we count the permutations that take $a$ to $b$, and multiply the result by $3$.

So suppose $a$ goes to position $b$. Maybe $b$ goes to $a$, in which case $c$ and $d$ must also get interchanged. This gives $1$ permutation. Or maybe $b$ goes to $c$ or $d$. We count the permutations that take $b$ to $c$, and multiply by $2$. So $a$ goes to $b$, and $b$ goes to $c$. Then $c$ must go to $d$, and $d$ must go to $a$. We conclude that there are $1+2$ allowed permutations such that $a$ goes to $b$. The total is therefore $\binom{5}{1}(3)(3)$.

For exactly $0$ right, we can use the same idea. However, it is easier to subtract the sum of the answers for $5$, $4$, $3$, $2$, and $1$ from $5!$.

Remark: We did crude counting, with essentially no theory. For numbers bigger than $5$, this could become very difficult. There is general theory that gives an answer. For details, look for example at the discussion of derangements in Wikipedia.

For any $m$, let $D_m$ be the number of derangements of a set $S_m$ of $m$ elements, that is, permutations of $S_m$ that leave no element fixed. (Wikipedia uses the notation $!m$ for $D_m$.) There are explicit expressions, and also nice recurrences, for $D_m$. The number of permutations of a set of $n$ elements that leave exactly $k$ elements fixed is then $\binom{n}{k}D_{n-k}$.

-
Great answer! Thank you so much :) And thank you for the link! –  Jay D. May 10 '12 at 15:04
@JayD.: Another thing to do for a great answer is to vote it up. Not that Andre will mind, but I just wanted to point it out, because you're new here. –  Tara B May 10 '12 at 15:12
I don't have enough reputation :-( –  Jay D. May 10 '12 at 15:18
@JayD.: I gave a "raw" analysis of the case $n=5$. But now that you have done some experimental work, and understand the ideas that went into the count, it is time to look into derangements (reference given at the end of the answer). A huge range of combinatorial ideas has been brought to bear on this classical problem. –  André Nicolas May 10 '12 at 15:30
@JayD.: Oh, I forgot that reputation is required for upvoting! You'll probably have enough before long, anyway. –  Tara B May 10 '12 at 15:44