Results 1 to 7 of 7

Math Help - Problem of hats

  1. #1
    Newbie
    Joined
    Dec 2010
    Posts
    7

    Problem of hats

    There are N people. All with their own, unique hat. Each throw his hat into a pile, and mix it. The number of ways for n < N to get their hats is ( N-n)!. Why?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Master Of Puppets
    pickslides's Avatar
    Joined
    Sep 2008
    From
    Melbourne
    Posts
    5,236
    Thanks
    28
    To understand these problems I take N to be a smallish number i.e. N=3, then find the number of arrangements for n=1,2.

    Then take N=4 and find the number of arrangements for n=1,2,3

    Finally take N=5 and find the number of arrangements for n=1,2,3,4 you'll start to see the pattern.

    ;D
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Flow Master
    mr fantastic's Avatar
    Joined
    Dec 2007
    From
    Zeitgeist
    Posts
    16,948
    Thanks
    5
    Quote Originally Posted by phillipshwong View Post
    There are N people. All with their own, unique hat. Each throw his hat into a pile, and mix it. The number of ways for n < N to get their hats is ( N-n)!. Why?
    Your formula is wrong.

    Partial Derangement -- from Wolfram MathWorld

    Rencontres numbers - Wikipedia, the free encyclopedia
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,749
    Thanks
    649
    Hello, phillipshwong!

    The problem is badly worded.
    Perhaps it was written by an amateur, a student . . .


    \text{There are }N\text{ people, each with a unique hat.}

    \text{The hats are mixed and returned to them at random.}

    \text{The number of ways for }n\text{ people to get their hats is }(N-n)!\;\text{ Why?}

    I think I understand their reasoning . . .


    \,n people get their hats back.

    The other N-n people may or may not get their hats back.

    . . And there are (N-n)! ways to return those hats.


    This is very sloppy work!



    If they meant exactly \,n get their hats,
    . . the problem is more complicated.

    \text{There are: }\:_NC_n \:=\:{N\choose n}\text{ ways to select the }n \text{ lucky people.}

    The original problem did not consider this.

    The other N-n people must not get their own hats.
    . . This is derangement of the N-n hats,
    . . which can be written: d(N-n).


    Example:
    . . 8 people, 8 hats.
    . . Find the number of ways that exactly 3 get their hats.

    There are: . _8C_3 \:=\:{8\choose3} \:=\:56 choices of the 3 people.

    The other 5 people must not get their own hats.
    . . There are: . d(5) \:=\:44 ways. .**

    Therefore, there are: . 56\cdot44 \:=\:2464 ways.


    **
    The Derangement Formula is a topic best left for a separate lesson.
    Or you can do a search for "derangement".

    Last edited by Soroban; December 20th 2010 at 09:18 AM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Dec 2010
    Posts
    7
    Quote Originally Posted by Soroban View Post
    Hello, phillipshwong!

    The problem is badly worded.
    Perhaps it was written by an amateur, a student . . .



    I think I understand their reasoning . . .


    \,n people get their hats back.

    The other N-n people may or may not get their hats back.

    . . And there are (N-n)! ways to return those hats.


    This is very sloppy work!



    If they meant exactly \,n get their hats,
    . . the problem is more complicated.

    \text{There are: }\:_NC_n \:=\:{N\choose n}\text{ ways to select the }n \text{ lucky people.}

    The original problem did not consider this.

    The other N-n people must not get their own hats.
    . . This is derangement of the N-n hats,
    . . which can be written: d(N-n).


    Example:
    . . 8 people, 8 hats.
    . . Find the number of ways that exactly 3 get their hats.

    There are: . _8C_3 \:=\:{8\choose3} \:=\:56 choices of the 3 people.

    The other 5 people must not get their own hats.
    . . There are: . d(5) \:=\:44 ways. .**

    Therefore, there are: . 56\cdot44 \:=\:2464 ways.


    **
    The Derangement Formula is a topic best left for a separate lesson.
    Or you can do a search for "derangement".

    I am waiting for that other lesson.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Flow Master
    mr fantastic's Avatar
    Joined
    Dec 2007
    From
    Zeitgeist
    Posts
    16,948
    Thanks
    5
    Quote Originally Posted by phillipshwong View Post
    I am waiting for that other lesson.
    You need to understand that what Soroban said was very probably a figure of speech and is code for "I don't have the time and MHF is not the place for teaching a course on combinatorics." I suggest you research these things yourself.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Dec 2010
    Posts
    7
    That is ok, since I don 't have time for a course, or that concern with d(i). I already figure out why it is ( N-n)!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Looking for Hats
    Posted in the Advanced Statistics Forum
    Replies: 7
    Last Post: March 17th 2010, 03:57 PM
  2. Prisoner' Hats
    Posted in the Math Puzzles Forum
    Replies: 2
    Last Post: November 24th 2009, 02:03 AM
  3. Variations on colours and hats
    Posted in the Math Challenge Problems Forum
    Replies: 12
    Last Post: July 8th 2009, 03:38 PM
  4. Hats off to helpful mathaticians
    Posted in the Statistics Forum
    Replies: 1
    Last Post: May 30th 2009, 08:41 PM

/mathhelpforum @mathhelpforum