1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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...]
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Combinatorics and not getting your hat
  1. Derivative of r^hat (Replies: 4)

  2. Combinatorics Question (Replies: 4)

  3. Combinatorics question (Replies: 2)

Loading...