Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Probability problem

  1. May 14, 2012 #1
    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)?
  2. jcsd
  3. May 14, 2012 #2


    User Avatar
    Science Advisor
    Homework Helper

    hi superconduct! :smile:
    it's just jargon! :rolleyes:

    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} :wink:

    (and "σ" is a symbol for a permutation (more usually, "π", i think), which means any re-ordering)
  4. May 14, 2012 #3
    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?
  5. May 14, 2012 #4


    User Avatar
    Science Advisor
    Homework Helper

    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 :smile:
  6. May 15, 2012 #5
    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?
  7. May 15, 2012 #6


    User Avatar
    Science Advisor
    Homework Helper

    hi superconduct! :smile:
    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 :wink:

    hmm … that's a bit messy … can anyone provide a simpler proof? :smile:
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook