Solving Probability Problem: Find P(Exactly 1 Person Gets Own Name Tag)

[superconduct]

Problem : Five students at a meeting remove their name tags and put them in a hat; the five students then each randomly choose one of the name tags from the bag. What is the probability that exactly one person gets their own name tag?

Attempt: I assumed the first person gets his/her own nametag and let other people be B,C,D and E. The number of arrangements of the persons that none of them gets his/her own nametag =9 : CBED, CDEB, CEBD, DBEC, DEBC, DECB, EBCD, EDBC, EDCB. And I get the answer 9/(4!) = 3/8

Then I found a solution of it : The selection of random nametags amounts to a selection of a random permutation of the five students from the symmetric group S₅. The condition will be met if and only if the selected permutation σ has exactly one cycle of length one (i.e. exactly one fixed point). The only distinct cycle types with exactly one fixed point are (1,4) and (1,2,2). There are (5!)/4=30 permutations of the first type and (5!)/(2^3)=15 permutations of the second. Thus, the desired probability is (30+15)/(5!) = 3/8

I don't understand the solution of it and I want to know about it. Can someone please explain the solution to me? Like what are those S₅, σ, cycle types, fixed points, how it comes up with (5!)/4 and (5!)/(2^3)?

 

[tiny-tim]

hi superconduct!

… what are those S₅, σ, cycle types, fixed points, how it comes up with (5!)/4 and (5!)/(2^3)?

it's just jargon!

it means that if you daisy-chain the people with each other's name-tags, then each daisy-chain is called a cycle, and the only way you can split 4 people into daisy-chains (without any "solo" chain) is {4} and {2,2}

(and "σ" is a symbol for a permutation (more usually, "π", i think), which means any re-ordering)

 

[superconduct]

Thank you for answering tim.
However I still don't understand the reason to daisy-chain it, and I am not sure if I get your {4}, {2,2} correctly...May I have some more explanation?

 

[tiny-tim]

yes … if everyone links an arm with the person whose name-tag he's wearing, then sooner or later there'll be a circle

everybody will be in exactly one circle

so the whole crowd is divided into circles, which in maths are called cycles (and i called daisy-chains)

the question stipulates that the 4 people have no cycles with only one person in

so that means there's either a cycle of all 4, or 2 cycles of 2

 

[superconduct]

but how come (5!)/4 and (5!)/(2^3) give the permutations with exactly 1 person chosen the correct tag? Why interpreting it as cycles will be able to do this convenient calculation?

 

[tiny-tim]

hi superconduct!

but how come (5!)/4 and (5!)/(2^3) give the permutations with exactly 1 person chosen the correct tag? Why interpreting it as cycles will be able to do this convenient calculation?

the number of ways of splitting n objects into cycles of lengths l₁, … l_m is n!/l₁ … l_m

to prove this, make m columns, of widths l₁, … l_m

in each row, write a different permutation of n objects (or numbers) … clearly, that's n! rows

now we have double-counting because eg if the width of a column is 4, then the order abcd is the same cycle as bcda, cdab, and dabc …

generally, any column of width l_i has the same cycle l_i times,

and so the total number of cycles is the total number of permutations divided by the products of the lengths of the cycles

hmm … that's a bit messy … can anyone provide a simpler proof? ​