Hi Chew,

I'll have to go to the Introduce Yourself forum in a bit. But first, some math.

**Quick Answer**

Suppose there are n people with n different professions. If one makes a random matching of the list of people to list of professions, then the probability that one correctly matches exactly k professions is

(nCk) (!(n-k))

------------------

n!

**Some explanation**

This is actually a somewhat difficult problem, and I don't really know if there is a slicker way to do it. What that means is I'll have to introduce a concept that I think is a bit esoteric. (Actually, I just learned about the subfactorial trying to figure this problem out, and I'm a math grad student, so I've seen my fair share of such things.)

**First, the conceptual definitions:**

-- An integer n factorial (written n!) is the number of ways you can order n different objects. For example, 3! = 6 because, if you have three objects a,b and c, you can order them 6 ways: abc, acb, bac, bca, cab, and cba.

-- An integer n subfactorial (written !n) is the number of ways you order n different objects so that none of the objects are in the right place, i.e. the first object isn't in the first place, etc. For example, !3 = 2 because, of the 6 ways of ordering a, b and c above, only bca and cab don't have a in the first place, b in the second or c in the third.

-- An integer n choose k (written nCk) is the number of distinct subsets of size k you can make from n objects. (Order doesn't matter). For example, 3C2 = 3, because of {a,b,c}, you can make 3 subsets of size 2: {a,b}, {a,c} and {b,c}. (Order doesn't matter, so {a,b} is the same as {b,a}.)

**Second, the technical definitions:**

-- The factorial of n the product of the consecutive series of whole numbers from 1 to n. For example, "5!" is shorthand for "5*4*3*2*1" and "3!" is shorthand for "3*2*1". So 5!=120 and 3!=6. (0! = 1 = 1! by definition).

-- The subfactorial is defined as

!n = n! (1 - 1/1! + 1/2! - 1/3! + 1/4! - ... + 1/n!)

(Note that 1/3! should be read as 1/(3!) = 1/6, not (1/3)!. Also, the sign in front of 1/n! is + if n is even, - if n is odd.)

So, as an example:

!5 = 5*4*3*2*1 [1 - 1/1 + 1/(2*1) - 1/(3*2*1) + 1/(4*3*2*1) - 1/(5*4*3*2*1)]

!5 = 120 [1 - 1/1 + 1/2 - 1/6 + 1/24 - 1/120]

!5 = 44

If you look up subfactorial, you can find the definition written more clearly.

-- n choose k is defined as

nCk = n! / [k! * (n-k)!]

So, as an example:

3C2 = 3!/[2! * (3-2)!]

3C2 = 3!/[2! * 1!]

3C2 = 6/[2*1]

3C2 = 6/2 = 3

**Sketch of justification**

Consider the 5 women (woman A, B, C, D and E) and 5 professions proposed in the original problem and say we wanted to know the probability that a guess gets exactly 2 correct.

For illustration, let's say the guess ABCDE is completely correct. So an example in which we get exactly two correct is EBCAD.

First we need to figure out which 2 we get correct. There are 5C2=10 different ways we can get 2 correct, because essentially we're just choosing 2 of the women and assigning the correct professions. (This is where the nCk comes in to play.) In our example, we get the professions correct for woman B and C, but we could have gotten it correct for 9 others: {A,B}, {A,C}, {D, E}, etc.

Now focus on one possible correct pair, say {B,C}, so our list looks like *BC**. We need to fill in the other three women's professions and we need to get them wrong. Otherwise, we'd have more than two correct.

If you think about it for a second, you're just trying to list A, D and E is an order so that A is not first, D is not second and E is not third. But, by our conceptual definition of subfactorial, the number of ways you can do this is !3 = 2. (There is where the !(n-k) comes into play.)

So, for each correct pair we can choose, there are !3=!(5-2) ways we can order the remaining three professions so that they are incorrect. Thus there are

(5C2)*(!(5-2)) = 10*2 = 20

different ways we can guess the 5 professions and get exactly 2 correct.

Finally, to find the probability, we need to divide this by the total number of guesses we can make, which is 5!=120, because a guess is simply a specific ordering of the five letters. (See the conceptual definition of factorial.)

So the probability we get exactly 2 correct is

(5C2)*(!(5-2))

------------------- = 20/120 = 16.7%.

5!

I hope this explanation is clear enough for digestion. Let me know if you have any questions.