Results 1 to 11 of 11

Math Help - Combinatorics Question

  1. #1
    Newbie
    Joined
    Nov 2013
    From
    United Kingdom
    Posts
    4

    Combinatorics Question

    6 people each own a desk each. The company owner wants to swap them round, so at most one of them stays where they were before. How many arrangements are possible?

    I've tried 264, which was the apparent sum of the arrangements where everybody changes position plus the arrangements with one in the same place.

    Can anyone help?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1573
    Awards
    1

    Re: Combinatorics Question

    Quote Originally Posted by Urbandude23 View Post
    6 people each own a desk each. The company owner wants to swap them round, so at most one of them stays where they were before. How many arrangements are possible?
    You need to know about derangements. Scroll down to the counting formula.
    Let D(n) be the number of derangements on n objects.

    The answer to your question is D(6)+\binom{6}{1}D(5).
    Last edited by Plato; November 15th 2013 at 03:13 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Nov 2013
    From
    United Kingdom
    Posts
    4

    Re: Combinatorics Question

    Does this factor in the part of the question that states there can still be one person in the same place as before?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1573
    Awards
    1

    Re: Combinatorics Question

    Quote Originally Posted by Urbandude23 View Post
    Does this factor in the part of the question that states there can still be one person in the same place as before?
    Please see my edit to that post. I miss-read it. I thought it said two people stayed put.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Nov 2013
    From
    United Kingdom
    Posts
    4

    Re: Combinatorics Question

    I get 283, is that correct?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1573
    Awards
    1

    Re: Combinatorics Question

    Quote Originally Posted by Urbandude23 View Post
    I get 283, is that correct?
    Did you take note of my edit?
    D(6)+\binom{6}{1}D(5).

    Look at this. Then at this

    Now apply the above formula.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Nov 2013
    From
    United Kingdom
    Posts
    4

    Re: Combinatorics Question

    So, it's 6*44+265!
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,765
    Thanks
    683

    Re: Combinatorics Question

    Quote Originally Posted by Urbandude23 View Post
    So, it's 6*44+265!
    I believe that overcounts. I think this gives the correct solution:

    Start with all permutations: 6!. Subtract from it the number of permutations where at least two people remain in their original positions: to count this, choose two people to remain in their original position, then permute the remaining four. However, this overcounts. If the permutation of the remaining four people fixes any other person, then I can I am counting that permutation an additional time. So, the correct number is \binom{6}{2}4!-k where k is the number of permutations that fixes at least three people. To count that, choose three people and permute the remaining three. Again, this overcounts by the number of permutations that fix at least four people. In other words, we need to apply inclusion/exclusion:

    6!-\binom{6}{2}4!+\binom{6}{3}3!-\binom{6}{4}2!+\binom{6}{5}1! = 720 - 360 + 60 - 30 + 6 =396
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1573
    Awards
    1

    Re: Combinatorics Question

    Quote Originally Posted by SlipEternal View Post
    I believe that overcounts.
    Not is does not over count.
    In the OP it wants at most one to stay put.

    D(6) counts the number of ways that none stay put.

    \binom{6}{1}D(5) counts number of the ways that exactly one stays put.

    Now I did not check the poster's calculations. But the idea is correct.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,765
    Thanks
    683

    Re: Combinatorics Question

    Quote Originally Posted by Plato View Post
    Not is does not over count.
    In the OP it wants at most one to stay put.

    D(6) counts the number of ways that none stay put.

    \binom{6}{1}D(5) counts number of the ways that exactly one stays put.

    Now I did not check the poster's calculations. But the idea is correct.
    My mistake. I haven't worked with derangements since I was an undergrad, and the inclusion/exclusion argument I set up was not quite right. You are correct. I was trying to give the idea of how to count it if they had not yet learned how to count derangements. But, that wikipedia entry gives a good explanation of how to arrive at the recursive formula.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1573
    Awards
    1

    Re: Combinatorics Question

    Quote Originally Posted by SlipEternal View Post
    I was trying to give the idea of how to count it if they had not yet learned how to count derangements. But, that wikipedia entry gives a good explanation of how to arrive at the recursive formula.
    The actual closed formula is interesting. Using inclusion/'exclusion:
    D(N) = \sum\limits_{k = 0}^N {{{\left( { - 1} \right)}^k}\binom{N}{k} \left( {N - k} \right)!}  = N!\sum\limits_{k = 0}^N {\frac{{{{( - 1)}^k}}}{{k!}}}  \approx \frac{{N!}}{e}
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Combinatorics question
    Posted in the Advanced Applied Math Forum
    Replies: 1
    Last Post: January 16th 2013, 06:26 PM
  2. Combinatorics QUESTION 1-3
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 20th 2012, 05:46 AM
  3. combinatorics question
    Posted in the Statistics Forum
    Replies: 4
    Last Post: May 10th 2012, 01:20 PM
  4. Combinatorics Question
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: September 28th 2009, 09:55 AM
  5. Combinatorics Question
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: September 27th 2009, 08:53 PM

Search Tags


/mathhelpforum @mathhelpforum