Discrete Math Secret Santa Problem This is a game in which e

Discrete Math Secret Santa Problem

This is a game in which every student in a class brings in a present (with no identifying name) and puts it in a large basket. Each present is then randomly assigned to a child in the class. In effect, then, everyone is giving a \"secret\" gift. From the teacher\'s standpoint, our \"random\" assignment has to exclude the possibility that a child\'s gift ends back up with that same chlid.

(a) So...suppose we\'re the teacher. We have 8 children in a classroom, and we want to assign each of them a \"Secret Santa\". Naturally, we don\'t want to assign any kid to be his or her own Santa. How many distinct legal arrangments are there?

(b) And now that you solved the problem for 8, write an expression that solves the problem for n in general. As n gets large, what is the probability that any Secret Santa arrangment will be a legal one?

Solution

Number of students =8,
So number of ways student 1 can get it is 7ways, student 2 in 6 ways , student 3 in 5 ways and so on.
So number of ways when student 1 gets the first gift is = 7x6x5x4x3x2x1 = 7!
But total 8 ways are there to start so 8x7!=8! ways.

Now to explain the above arrangement.
Number of ways student1 gets it is by 7 ways excluding his gift.
Now if he selects 2\'s gift then for 2 number of choices are 7 but if he doesnt chooses then it is 6.
Now for 2 if it selects 3\'s gift , 3 has 6 chocies and if it doesnt chooses then it has 5 choices.
And in the same ways for all others .
So Number of ways = (7x6x5x4x3x2x1)+(7x7x6x5x4x3x2x1) =(7!+7.7!)=7!(7+1)=7!x8=8! ways.

For n in general it will be n! ways.
number of ways it can be set is nxn!.
So Probablity that it is a Secret Santa arrangement is n!/(nxn!)=1/n.