Question

1. n people, all wearing different colored hats, throw their hats into a circle. Right after, all start grabbing as many hats as they can without regards to anyone else. Some end up with multiple hats, and others end up hatless.

a) Compute the probability that each person who grabbed at least one hat manages to grab not only their own hat but also one or more hats that do not belong to him or her.

b) Make a separate counting argument for the numerator and the denominator of the probability expression. Express your answer in Stirling numbers of the second kind.

Answer 1

Since every person is grabbing as many hats as he can, each hat has n choices, as it can be grabbed by any one out of n persons.

Total number of such distributions = nⁿ.

This can be understood in a better way, assume there are only two persons A and B and their hats are a and b, then the possible distributions will be 2² = 4 as shown in the following table.

A	B
a	b
b	a
ab	-
-	ab

Let us calculate the number of ways that each person who grabbed at least one hat, manages to grab not only their own hat but also one or more hats that do not belong to him or her.

We know that distributing n distinguishable objects to k distinguishable boxes, when each box has at least one object is given by

N(n, k) = kⁿ - ^kC₁(k-1)ⁿ + ^kC₂(k-2)ⁿ - ... + ^kC_n(k-n)ⁿ

The above formula uses inclusion - exclusion formula.

and Stirling number of second kind S(n,k) counts number of ways of distributing n distinguishable objects to k indistinguishable boxes, when each box has at least one object

S(n,k) = [kⁿ - ^kC₁(k-1)ⁿ + ^kC₂(k-2)ⁿ - ... + ^kC_n(k-n)ⁿ]/k!

Thus we can use N(n, k)= S(n,k).n!

Suppose, out of n, 3 persons are getting at least one hat, then these 3 persons also must have their own hats along with at least one more hat. So first give them their 3 hats and the remaining n - 3 hats can be distributed among them so that each one gets at least one hat.
This can be done in (ⁿC₃)N(n-3, 3) ways = (ⁿC₃) S(n-3, 3)*3! ways.

This can be generalized for k persons are getting at least one hat along with their own hats, as
(ⁿC_k) S(n-k, k)*k!, where 2k is less than or equal to n

Numerator of the probability = (ⁿC₁) S(n-1, 1)*1! + (ⁿC₂) S(n-2, 2)*2! + (ⁿC₃) S(n-3, 3)*3! + ......(ⁿC_k) S(n-k, k)*k!, where 2k is less than or equal to n.

denominator of the probability expression = nⁿ