A secretary needs to send n letters (to n people). She first prepares all the le

Question

A secretary needs to send n letters (to n people). She first prepares all the letters and all the envelopes. Then she gets drunk at lunch and comes back to the office. As a result, she stuffs the letters into the envelopes completely at random. Clearly, many of the letters will probably be put in the wrong envelopes. This problem deals with this question: for any integer k (0 is less than or equal to k is les than n), what is th eprobability that exactly k letters will be in their correct envelopes? So, for n letters and envelopes, we want to determine P(k matches).

A.) Derive a nice and simple expression for P(k matches) as a multiple of P(no matches....) Thus, the matching problem effectively reduces to finding P(no mathces).

B.) Derive a general formula for P(no matches) for n letters.
Hint: Use the Inclusion-Exclusion principle

C.) Based on the formula you derived in Part b, calculate P(no matches) for n = 1,2,3,...10 (present the results in the form of a table).

D.) Find the limit of P(no matches), as n goes to infinity.

Explanation / Answer

total number of envelopes: n number of ways to put the letters in: n! P(no matches)=(n-1)*(n-1)!/n! P(1 match)=n*(n-2)*(n-2)!/n! P(n-1 matches)=0 p(n matches)=1/n! A For k=/=n-1 or n, P(k matches)=(n-k)(n-k)!/n! B P(no matches)=(n-1)*(n-1)!/n!

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.