Permutation and combination problem

[manisha1980]

Hi,

I'm having trouble understanding a question, which looks deceptively simple. May be it is. I would like to know how any of you would tackle the following problem?

There are N men wearing identical hats in a room. They all take off their hats and place it in the center of the room and then each one of them picks up a hat. What's the probability none of them will end up with the hat he was initially wearing?

Thank you in advance,
Manisha

 

[honestrosewater]

I think the best way to solve any such problem is to figure out, in this order, the experiment, the sample space, and the event that you want to find the probability of.

The set of men = {1, 2, 3, ... n}. The set of hats = {1, 2, 3, ... n}. You could also index the sets if you prefer, e.g the set of men = {m₁, m₂, ..., m_n}. This numbering represents the fact that Man 1 was initially wearing Hat 1, Man n was initially wearing Hat n.

The experiment: Man 1 chooses a hat and doesn't replace it. Man 2 chooses a hat and doesn't replace it...
So you will end up with pairs (m, h) of one man to one hat. The key here is to let the men choose in the order in which they are labelled; Man 1 chooses first, Man 2 chooses second, etc. This way, you only need to consider the order in which the hats are chosen. The order in which that hats are chosen tells you which man is paired with which hat. For example, if there are 3 hats, one possible outcome of choosing hats is (2, 1, 3). This means the pairing of men to hats is {(1, 2), (2, 1), (3, 3)}. Here, one man (Man 3) has chosen the hat he was initially wearing. Make sense? Can you figure out the sample space?

 

[BicycleTree]

Let me know when you get the answer to this one. It's stumping me too. I have no idea unless you're supposed to use a recursion relation to solve it.

 

[TenaliRaman]

The problem is very simple however it is tricky in the sense, you need to setup your mathematical model correctly to find the answer.

Let E_i be the event that the i'th man gets his own hat.
So,
P(E_i)=1/n
P(E_i intersection E_j) = (1/n)(1/n-1) ... (i =/= j)
P(E_i intersection E_j intersection E_k) = (1/n)(1/n-1)(1/n-2) ... (i =/= j =/= k)
and so on

According to our question given here, we are looking for,
P(E_1* intersection E_2* intersection E_3* ... intersection E_N*)
(where E_i* denotes complement of E_i)
= 1 - P(E_1 U E_2 U E_3 ... U E_N)
Apply the inclusion exclusion principle and do some good algebra and you will end up with,
P(E_1* intersection E_2* intersection E_3* ... intersection E_N*)
= $$\sum_{i=0}^{N} \frac{(-1)^i}{i!}$$

-- AI

 

[manisha1980]

Thanks TenaliRaman,

Your answer's making sense to me... I guess Calculus1967 is making the same mistake I was making earlier, where I was just considering the case where every single man ended up with a different hat, disregarding the fact that my answer included cases where some not all of the men could have picked up their own hats.

Manisha

 

[BicycleTree]

Aha, Tenali. I need to find some exercises on this "principle of inclusion and exclusion" you're talking about.

I found a recursive way to calculate it, also. Let f(x) count the number of ways to arrange x hats among x people with no matches. First consider all cases total, then subtract from these all those where 1 hat matches, then subtract all those where 2 hats match, and so on. If 1 hat matches out of x then the other hats can be arranged without matching in f(x - 1) ways, and there are C(x, 1) = x ways to select the 1 hat to match. If 2 hats match out of x then the other hats can be arranged without matching in f(x - 2) ways, and there are C(x, 2) ways to select 2 hats to match. This goes on until you have x hats that match out of x, and you can arrange the "other" hats in f(0) = 1 ways and have C(x, x) = 1 way of picking the x hats. So the formula (with E for summation over) is:
f(0) = 1
f(x) = x! - E(i = 1 to x)(f(x - i)*C(x, i)) , when x > 1

Checking the first few terms, this gives 1, 0, 1, 2, 9 as desired, albeit with excessive calculation.

 

[TenaliRaman]

That recursion formula seems rather difficult to solve, for one that sigma cannot be easily eliminated(if it can be eliminated at all). Hmm, anyone with any luck to solving it?

-- AI

 

[honestrosewater]

Can you not extend P(A U B) to more than two non-mutually exclusive events?

 

[BicycleTree]

Ah, that should be f(x) = x! - E(i = 1 to x)(f(x - i)*C(x, i)) , when x > 0. I had it originally with x > 1 because I also supplied f(1) = 0.

 

[TenaliRaman]

Can you not extend P(A U B) to more than two non-mutually exclusive events?

Ofcourse you can extend, that's what i have used in my proof

-- AI

 

[honestrosewater]

Ofcourse you can extend, that's what i have used in my proof

-- AI

Oh, I can't see how you got there. What is the formula for three events? The best I can come up with follows, but I don't know how to simplify it or if it's correct ("~" is complement):
P(A) + P(B) + P(C) - P(A n B n ~C) - P(A n C n ~B) - P(B n C n ~A) - P(A n B n C).

 

[TenaliRaman]

Your expression for three events is almost correct but that last term should have 2 as a factor.

However, you can use a more cogent expression for the union of three events.
P(A u B u C)
= P(A)+P(B)+P(C) - P(A n B) - P(B n C) - P(A n C) + P(A n B n C)

I call this expression cogent, because it has a very intuitive reasoning.
Consider this diagram,
http://regentsprep.org/Regents/math/venn/VennDiagramlabeled.gif
(Sorry i am too lazy to draw one myself )

Now,
P(A u B u C) must contain P(A)+P(B)+P(C)
But we have counted P(A n B), P(B n C), P(A n C) twice while adding up P(A)+P(B)+P(C). Hence we remove each of them once from the addition.
Now, in P(A)+P(B)+P(C) we counted P(A n B n C) thrice but when removed P(A n B), P(B n C), P(A n C) once each, which means we haven't accounted for P(A n B n C) so far, hence we add P(A n B n C) which gives rise to the final expression.

The general expression for n events is,
$$P(E_1 + E_2 + ... + E_n) = <br /> \sum_{i=1}^{n}P(E_i)<br /> - \sum\sum_{\frac{i,j=1}{i<j}}^{n}P(E_i E_j)<br /> + \sum\sum\sum_{\frac{i,j,k=1}{i<j<k}}^{n}P(E_i E_j E_k)<br /> ...<br /> + (-1)^{n-1} P(E_1 E_2 E_3 ... E_n)$$

You can try proving it using induction.

-- AI

 

[honestrosewater]

Thanks, a diagram and tallies made it crystal clear; I'll remember to use them in the future! I just started with probability. I can't read that equation, but I'll look it up and give the proof a go tomorrow. Thanks again.

 

[LittleWolf]

If you are still interested in eliminating the summation, round (n!/e) to the nearest integer for n>0.

 

[TenaliRaman]

If you are still interested in eliminating the summation, round (n!/e) to the nearest integer for n>0.

I believe you are talking about Bicycle Tree's recursion formula, in which case i wonder how you got it. Ofcourse your formula is correct as long as the value of x in Bicycle Tree's recursion is large enough. (It stems directly from the fact that the summand i gave is a partial sum of 1/e)

-- AI