## Probability problem

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 S5. 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 S5, σ, cycle types, fixed points, how it comes up with (5!)/4 and (5!)/(2^3)?

 PhysOrg.com science news on PhysOrg.com >> 'Whodunnit' of Irish potato famine solved>> The mammoth's lament: Study shows how cosmic impact sparked devastating climate change>> Curiosity Mars rover drills second rock target

Blog Entries: 27
Recognitions:
Gold Member
Homework Help
hi superconduct!
 Quote by superconduct … what are those S5, σ, 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)

 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?

Blog Entries: 27
Recognitions:
Gold Member
Homework Help

## Probability problem

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

 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?

Blog Entries: 27
Recognitions:
Gold Member
Homework Help
hi superconduct!
 Quote by 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 l1, … lm is n!/l1 … lm

to prove this, make m columns, of widths l1, … lm

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 li has the same cycle li 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?