# 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.

-
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

I just wanted to make the simple observation that since you are only looking at permuting a sequence of 5, the total number of permutations is 5!=120 which is small enough for complete enumeration. I am sure that most of you being mathematicians find doing this by brute force distasteful. But it does work as long as you systematically enumerate all 120. You can then inspect each one to see how many numbers are in their right place and then sum all cases with 1 and divide it by 120 to get the probability of one match. Do the same for 2,3 and 5. Aside from the obvious logic that if you match 4 the last one can only be in its right place you can also see this by noting that no case had exactly 4 matching their positions. I did not notice that this was mentioned in the answer above. I did the full enumeration and got 46/120 for 0 46/120 for 1 20/120 for 2 7/120 for 3 0/120 for 4 and 1/120 for 5.

-
Could someone explain the downvote on this answer? i am just wondering if you found an error in my calculations. – Michael Chernick May 10 '12 at 20:14
I downvoted for the phrase "I am sure that most of you being mathematicians find doing this by brute force distasteful." Surely this answer doesn't require such presumption. If it was simply a joke then I apologize for misunderstanding. – Antonio Vargas May 10 '12 at 22:08
Yes I was saying it tongue in cheek. I cinsider myself a statistician. i have a PhD is statistics but a bachelor's and masters in mathematics. So I think I can claim to be a mathematician as well and i knwo a lot of mathematicians and how they think. There is really elegance to mathematics and I do think that mathematicians look for the elegant solutions. So in a way I was half serious. I don't like doing things by brute force either (unless I can't think of a better way). I don't mind the downvote. I was just concerned that maybe I slipped up dong it the brute force way. – Michael Chernick May 10 '12 at 23:19
I've reversed the downvote. Cheers! – Antonio Vargas May 11 '12 at 0:36
Okay. It was not necessary but thanks. – Michael Chernick May 13 '12 at 15:31