Probability question of CLRS

Question

In a restaurant each of $n$ customer gives a hat to the hat check person. The hat check person gives the hat back to the customer in a random order. What is expected number of customer who get back their own hat?

Comments

Its silly to ask but is it n/2  ?

---

how??

---

is it correct or not ?

---

no, ans 1

---

You can find it here: 

Although i did not understand it. 

https://ita.skanev.com/05/02/04.html

---

Please check if this method is correct or not.

$n$ customers

suppose n=1

Then the hat check person gives the hat back to the customer i.e probability of getting the correct hat back is 1.

suppose n=2

if the hat check person gives the correct hat back to the 1st customer then there is only 1 hat left so the other customer will also get back his hat.

If customer 1 gets wrong hat then customer 2 will also get the wrong hat.

So here 2 cases are possible and out of this we need to have first case so probability = $\frac{1}{2}$

suppose n=3

Then out of 3! cases there is only 1 correct way of giving the hat back to the customers so probability = $\frac{1}{6}$

suppose n=4

Then out of 4! cases there is only 1 correct way of giving the hat back to the customers so probability = $\frac{1}{24}$

......

suppose n=n

Then out of n! cases there is only 1 correct way of giving the hat back to the customers so probability = $\frac{1}{n!}$

n	1	2	3	4	5	...	n
P(giving hats correctly)	1	1/2	1/6	1/24	1/120	...	1/n!

E(giving hats correctly) = $1*1 + 2* \frac{1}{2} + 3 * \frac{1}{3!} + 4* \frac{1}{4!} + 5* \frac{1}{5!} +....n* \frac{1}{n!}$

= $1 + 1 + \frac{1}{1*2}+\frac{1}{1*2*3}+\frac{1}{1*2*3*4}+....+\frac{1}{1*2*3....*(n-1)}$

=$1 + \frac{1}{1!} + \frac{1}{2!}+\frac{1}{3!}+\frac{1}{4!}+....+\frac{1}{(n-1)!}$

=$1 + 1+0.5 + 0.16 +0.041+0.0083+0.0013+......$

=$1+1.71$

=$2.71$

= $3$

---

ans 1. not 3

---

What is wrong in my method ?

---

@Satbir , 

Then out of n! cases there is only 1 correct way of giving the hat back to the customers so probability = 1/n!

What is it that you're calculating? Is it the probability to give everyone their correct hat?

---

Yes.

---

i thought you are just considering only that case where a single customer among various customers should get  their hat back.

Answer 1

X :  1       1        1         1           1        .......... 1  (Till n terms)

fx : 1/n   1/n     1/n      1/n        1/n                1/n       (probability that he gets the correct hat back out of n hats)

Now, expectation (or in other words mean)= x * $f_x$

= n* (1/n)

= 1.