Results 1 to 5 of 5

Math Help - derangement problem

  1. #1
    Junior Member
    Joined
    Feb 2011
    Posts
    38

    derangement problem

    At a party, n people are seated in a room with n+1 chairs. They go to another room for supper; when they return and sit down again, it is found that no one occupies the same chair as before. Show that this can occur in precisely Dn + Dn+1 ways.

    When I tried to solve this, I got (n+1)*Dn + Dn+1 instead, and I'd like to know what I got wrong.

    Here's my strategy: add a new "invisible person" to the n people, and consider the seating for the n+1 people & n+1 chairs.

    Case 1) the invisible person sits in the same chair
    Then the remaining n seats should make a derangement, so there are Dn possibilities.

    Case 2) the invisible person also gets a new chair the second time
    All n+1 chairs should make up a derangement, so there are Dn+1 possibilities.

    But for Case 1, there are n+1 seats where the invisible person can occupy, so in total there are (n+1)*Dn + Dn+1 ways.


    Why is the (n+1) factor unnecessary?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,403
    Thanks
    1486
    Awards
    1

    Re: derangement problem

    Quote Originally Posted by Yuuki View Post
    At a party, n people are seated in a room with n+1 chairs. They go to another room for supper; when they return and sit down again, it is found that no one occupies the same chair as before. Show that this can occur in precisely Dn + Dn+1 ways.
    When I tried to solve this, I got (n+1)*Dn + Dn+1 instead, and I'd like to know what I got wrong.

    Here's my strategy: add a new "invisible person" to the n people, and consider the seating for the n+1 people & n+1 chairs.

    The \mathcal{D}_{n+1} is the number of ways for all, including your "invisible person", are not in the original seat.

    BUT, \mathcal{D}_{n} is the number of ways for everyone other than your "invisible person" is not in the original seat.

    There are just two cases: the original unoccupied seat is now occupied or it is not,
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Feb 2011
    Posts
    38

    Re: derangement problem

    Thank you for the reply.

    So for a given starting condition, there would be only be one Dn instead of n+1.

    For example, if I denote the people A, B, C, X (X being the invisible person), and assign chairs 1, 2, 3, 4 to them respectively,
    either 1) X sits in #4 the second time 2) X doesn't sit in #4 the second time, so in fact there are only Dn + Dn+1 possibilities, since the problem is only asking me to count the ways for one initial condition.

    If I took in account all the initial conditions, would there be n!(Dn + Dn+1) possibilities?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,403
    Thanks
    1486
    Awards
    1

    Re: derangement problem

    Quote Originally Posted by Yuuki View Post
    So for a given starting condition, there would be only be one Dn instead of n+1.
    For example, if I denote the people A, B, C, X (X being the invisible person), and assign chairs 1, 2, 3, 4 to them respectively,
    either 1) X sits in #4 the second time 2) X doesn't sit in #4 the second time, so in fact there are only Dn + Dn+1 possibilities, since the problem is only asking me to count the ways for one initial condition.
    If I took in account all the initial conditions, would there be n!(Dn + Dn+1) possibilities?
    As I said, this is binary. Two cases.
    The original unoccupied seat now occupied or not.
    Those are disjoint events, so their countings are additive.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Feb 2011
    Posts
    38

    Re: derangement problem

    I think I see.

    What you're saying is that there are Dn + Dn+1 ordered pairs (1234, x1x2x3x4),
    and there are only two situations: x4=4 or x4≠4, right?

    What I said about the n! is that there are n! possibilities for the first element of the ordered pair.
    I was considering situations such as (2314, x1x2x3x4).
    But the chairs are not actually labeled, so any starting position whether it be 1234, 2314, or 3421, are all identical.

    Hence, like you said there are only Dn + Dn+1 ways.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 5
    Last Post: January 13th 2013, 10:48 AM
  2. Combinatorial proof of derangement identity
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: July 29th 2010, 02:40 PM
  3. Derivation of Derangement formula
    Posted in the Advanced Statistics Forum
    Replies: 9
    Last Post: June 6th 2010, 01:42 PM
  4. derangement question
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: December 8th 2009, 02:18 PM
  5. Derangement Question
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: September 22nd 2009, 09:47 PM

Search Tags


/mathhelpforum @mathhelpforum