# Thread: Arranging k out of n chairs in a circle

1. ## 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 .

2. 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.

3. thanks , so is there any formula for it?

4. 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?

5. Originally Posted by Plato
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?

6. Originally Posted by snowtea
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.

7. Originally Posted by pranay
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?