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

Homework Help: Combinatorics and not getting your hat

  1. Jan 11, 2006 #1

    Alkatran

    User Avatar
    Science Advisor
    Homework Helper

    We were given an extra credit problem in discrete structures 2 today. The problem is: n people go to a party and leave a hat. When they leave they take a random hat. What is the probability that no one ends up with the same hat?
    I can calculate the probability, but I was just wondering if I can simplify this any more. Here is my basic work (obviously a lot of reasoning is left out):

    2 people:
    [tex]2! - 2*1! + 1 = 1[/tex]

    3 people:
    [tex]3! - 3*2! + 3*1! - 1 = 2[/tex]

    generalized:
    [tex]
    \sum_{x=0}^n _n C_x (n - x)! (-1)^x
    [/tex]

    simplified:
    [tex]
    \sum_{x=0}^n \frac{n!}{x!}(-1)^x
    [/tex]
    I know that this needs to be divided by n! to get the probability.

    Is there any way to get rid of the summation or simplify in some other way?

    edit: just realized I could take the n! out. It's now obvious that the summation stays nicely between 1 and 0... still not sure where to simplify from there.
     
    Last edited: Jan 11, 2006
  2. jcsd
  3. Jan 11, 2006 #2

    benorin

    User Avatar
    Homework Helper

    This is a derangement problem and you got it: good job! The number of derangements of n objects, say hats, is variously denoted by [itex]D_n[/itex] or by [itex]!n[/itex] and is given by

    [tex]D_n=!n=\sum_{k=0}^n \frac{n!}{k!}(-1)^k[/tex]

    EDIT: I fixed the link (it goes to mathworld now).
     
    Last edited: Jan 11, 2006
  4. Jan 11, 2006 #3

    Alkatran

    User Avatar
    Science Advisor
    Homework Helper

    Excellent. So I suppose that means there isn't a non-summation (elementary?) formula for the summation of -1 to the x divided by x factorial from 0 to n?
     
  5. Jan 11, 2006 #4

    benorin

    User Avatar
    Homework Helper

    [tex]!n=\left[ \frac{n!}{e}\right][/tex] where [x] is the nearest integer function.
     
  6. Jan 11, 2006 #5

    Alkatran

    User Avatar
    Science Advisor
    Homework Helper

    I found that one on mathworld too, very nice. Small point though: It doesn't match when n = 0.

    I'm going to stick with the summation form: I can show the work to make it there. I have no idea how to reach round(n!/e).
     
  7. Jan 11, 2006 #6

    benorin

    User Avatar
    Homework Helper

    Hmm... I'll try.

    We know that [tex]!n=\sum_{k=0}^n \frac{n!}{k!}(-1)^k=n!\sum_{k=0}^n \frac{(-1)^k}{k!}[/tex] is, by your combinatorial arguement, an integer, furthermore we have

    [tex]\frac{n!}{e}=n!e^{-1}=n!\sum_{k=0}^{\infty} \frac{(-1)^k}{k!} = n!\sum_{k=0}^{n} \frac{(-1)^k}{k!} + n!\sum_{k=n+1}^{\infty} \frac{(-1)^k}{k!} = !n+n!\sum_{k=n+1}^{\infty} \frac{(-1)^k}{k!}[/tex]

    so we need to show that the second term in the last equality is less than unity, and we wish to know when it is greater than 0.5 [I think].

    Since it is an alternating series, we have an estimation theorem for that... notably, it is also the remainder for a Taylor series (times n!).
     
  8. Jan 11, 2006 #7

    benorin

    User Avatar
    Homework Helper

  9. Jan 11, 2006 #8

    benorin

    User Avatar
    Homework Helper

    so, picking up at the alternating series estimation, we know that the error in estimating [itex]\frac{n!}{e}[/itex] by stopping at the nth term is less than the absolute value of the next term in the series, hence

    [tex]\left| \frac{n!}{e} - !n\right| \leq \frac{n!}{(n+1)!} = \frac{1}{n+1}<1,[/tex]

    therefore round it! [but I am tired :zzz: , so have a go at it: I'm likely missing something...]
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook