Online Course Discussion Forum

MC II-B Combinatorics Self-paced

 
 
Picture of Jeremy Zhao
MC II-B Combinatorics Self-paced
by Jeremy Zhao - Tuesday, 21 July 2020, 8:57 AM
 

Hi, I had a question about the Lecture 7 Quick Response Questions #10 (Question 7.20).

Suppose n friends go to a party. They each wear a coat. However, as they are leaving, they each randomly grab a coat. Let an= the number of ways the friends can leave so that \emph{none} of them have their own coat. In class we gave a recursive formula for an.

Calculate a4

and verify the calculation by listing out all of the outcomes. Let the people 1,2,3,4 have hats A,B,C,D. Thus, one example is DCBA (person one getting coat D, person two had C, etc.). (Input the value of a4 as your answer.)


Question #1: Where do I find the given recursive formula in the class?

Question #2: Regarding the math problem itself, can we solve it using PIE(Principle Inclusion Exclusion)? Where Set A=ways person 1 has his own coat, Set B=ways person 2 has own coat, etc. and then subtracting the union of the sets AUBUCUD from the total. I tried using this method, but I got the wrong answer.

 
Picture of Dr. Kevin Wang
Re: MC II-B Combinatorics Self-paced
by Dr. Kevin Wang - Thursday, 23 July 2020, 11:02 PM
 

The recursive formula is in Problem 7.9(b).  You can watch the video lecture for that problem, or check the solution at the end of the book.

The PIE method does work.  If you calculate the union correctly, you should get the right answer.  If you show the details of your work, the teachers or other students may help out.