Results 1 to 7 of 7

Math Help - Arranging k out of n chairs in a circle

  1. #1
    Member
    Joined
    Nov 2010
    Posts
    95

    Arranging k out of n chairs in a circle

    What are the number of ways of arranging k out of n chairs in a circle such that no two of the k chairs are adjacent to each other?
    e.g If n=4 and k =2 then number of ways is 2 .
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Dec 2010
    Posts
    470
    For simplicity, say the k chairs are red, and all the other chairs are green. You want to count circular arrangements where no two red chairs are next to each other.

    You know that each red chair must have a green chair on its right. Treat these pairs of red and green chairs as one object (i.e. they move around together).

    So for n=4 k=2
    (r1 g1)(r2 g2)
    (r1 g2)(r2 g1)

    Or for n=5 k=2
    (r1 g1)(r2 g2)g3
    (r1 g1)g3(r2 g2)
    (r1 g2)(r2 g1)g3
    (r1 g2)g3(r2 g1)
    (r1 g3)g1(r2 g2)
    ...

    See how it works? Think in terms of red-green pairs of chairs.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Nov 2010
    Posts
    95
    thanks , so is there any formula for it?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,912
    Thanks
    1760
    Awards
    1
    I have been reluctant to join this discussion.
    The reason being that while I agree with snowtea’s assignment of ‘red’ chairs, why do we assume that the chairs are distinct?
    If the chairs are not distinct, then the basic formula is incorrect.
    Why do we assume the chairs are distinct apart from color?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member
    Joined
    Dec 2010
    Posts
    470
    Quote Originally Posted by Plato View Post
    I have been reluctant to join this discussion.
    The reason being that while I agree with snowtea’s assignment of ‘red’ chairs, why do we assume that the chairs are distinct?
    If the chairs are not distinct, then the basic formula is incorrect.
    Why do we assume the chairs are distinct apart from color?
    I just assumed they were distinct since the original post said:
    "e.g If n=4 and k =2 then number of ways is 2."

    But Plato makes a good point. Was this condition part of the original problem, or did you give the example?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Nov 2010
    Posts
    95
    Quote Originally Posted by snowtea View Post
    I just assumed they were distinct since the original post said:
    "e.g If n=4 and k =2 then number of ways is 2."

    But Plato makes a good point. Was this condition part of the original problem, or did you give the example?
    yes the chairs are distinct and yes this was part of the problem.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Senior Member
    Joined
    Dec 2010
    Posts
    470
    Quote Originally Posted by pranay View Post
    thanks , so is there any formula for it?
    Yes there is a formula. Why don't you try what was suggested: First pair up "red" and "green" chairs. Then permute (treating the pairs as one block).
    How many ways are there to do each step?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Chairs and Stools
    Posted in the Math Topics Forum
    Replies: 2
    Last Post: March 1st 2011, 11:16 PM
  2. Arranging numbers in a circle
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 13th 2009, 03:20 AM
  3. Re-arranging...
    Posted in the Algebra Forum
    Replies: 2
    Last Post: January 2nd 2009, 06:34 PM
  4. Re-arranging
    Posted in the Algebra Forum
    Replies: 2
    Last Post: June 14th 2008, 09:16 AM
  5. chairs
    Posted in the Advanced Statistics Forum
    Replies: 6
    Last Post: February 18th 2008, 02:14 PM

Search Tags


/mathhelpforum @mathhelpforum