Question

In: Statistics and Probability

1. n people, all wearing different colored hats, throw their hats into a circle. Right after,...

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.

Expert Solution

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ⁿ

orchestra answered 2 years ago

At a party n men take off their hats. After mixing up the hats, each man...

At a party n men take off their hats. After mixing up the hats, each man randomly picks one. We say a match occurs if a man picks his own has. what is the probability of no matches?

people wearing prism goggles, which shift the visual world left or right by small, quickly adapt...

people wearing prism goggles, which shift the visual world left or right by small, quickly adapt to the distortion. suppose you were wearing goggles that completely reversed everything along the left-right dimension, as if you were viewing the world in a mirror, with objects to your right appearing to be on your left, and objects appearing to be on your left appearing to be on your right. would you be able to adapt to this sort of distortion? explain your...

Use the SEVEN Thinking Hats to explore all the possible aspects of choosing the right future...

Use the SEVEN Thinking Hats to explore all the possible aspects of choosing the right future spouse. Towards the end use the Blue Hat to summarize, conclude and design 7-10 strategies that help you to make a sound decision.

Use the blue Hats to explore all the possible aspects of choosing the right future spouse....

Use the blue Hats to explore all the possible aspects of choosing the right future spouse. Towards the end use the Blue Hat to summarize, conclude and design 7-10 strategies that help you to make a sound decision.

Answer ALL of the questions below! Circle the right expression in the parentheses. Q1. Import tariff...

Answer ALL of the questions below! Circle the right expression in the parentheses. Q1. Import tariff (a. raises, b. lowers, c, keeps constant) the domestic price and (a. always, b. sometimes, c. never) (a. raises, b lowers) the world price. 2. (Multiple choices.) A tariff in a large country tends to benefit (a. domestic producers/ b. foreign producers/ c. domestic consumers/ d. foreign consumers/ e. domestic government revenue) and hurt (a. domestic producers/ b. foreign producers/ c. domestic consumers/ d....

Suppose that the birthdays of different people in a group of n people are independent, each...

Suppose that the birthdays of different people in a group of n people are independent, each equally likely to be on the 365 possible days. (Pretend there's no such thing as a leap day.) What's the smallest n so that it's more likely than not that someone among the n people has the same birthday as you? (You're not part of this group.)

PROBLEM 6. Suppose that the birthdays of different people in a group of n people are...

PROBLEM 6. Suppose that the birthdays of different people in a group of n people are independent, each equally likely to be on the 365 possible days. (Pretend there's no such thing as a leap day.)What's the smallest n so that it's more likely than not that someone among the n people has the same birthday as you? (You're not part of this group.)

Research the hexagonal numbers whose explicit formula is given by Hn=n(2n-1) Use colored chips or colored...

Research the hexagonal numbers whose explicit formula is given by Hn=n(2n-1) Use colored chips or colored tiles to visually prove the following for .(n=5) [a] The nth hexagonal number is equal to the nth square number plus twice the (n-1) ^th triangular number. Also provide an algebraic proof of this theorem for full credit . [b] The nth hexagonal number is equal to the (2n-1)^th triangular number. Also provide an algebraic proof of this theorem for full credit. please use...

We have n people and K floors: what is the chance that 1)all people get off...

We have n people and K floors: what is the chance that 1)all people get off in the smae floor? 2)at least one in evey floor?3)P( floor 3 is empty)?4)p(2 people get out in the first floor and 3 people or mpre get off in the second floor)

10 people are sitting in a circle. How many different ways can they be seated relative...

10 people are sitting in a circle. How many different ways can they be seated relative to each other if Steve and Alice must be seated directly across from each other? Do I need to apply the circular permutation formula of (n-1)!, and do I need to multiply the end result by 2 to account for the fact that they could be in different positions kinda like standing beside each other where one is on the left but could also...