Circular Permutations

Date: 08/07/2005 at 17:50:54
From: Ted
Subject: Combinations

With four card players at a table, how many different seating
arrangements exist from a sequential point of view?  It looks like six 
different seatings are possible: 1234, 1342, 1432, 1243, 1324, and 
1423.  This is a Liverpool Rummy game where the person before you is 
often significant. We just want a way to mix up the seating in a 
logical manner.

By some definitions this is a combination question and would be 4C4,
but that doesn't work out since that answer is one.  It looks like it
is (n-1)!, but I can't find the solution in your work.

Date: 08/08/2005 at 23:14:02
From: Doctor Wilko
Subject: Re: Combinations

Hi Ted,

Thanks for writing to Dr. Math!

This situation would be called a "circular permutation" and the 
formula is indeed (n-1)!  Since _order_ is important, it is a 
permutation, and there are six permutations (arrangements) of four
people at a circular table.

Does this help?  Please write back if you have further questions.

- Doctor Wilko, The Math Forum
  http://mathforum.org/dr.math/ 

Date: 08/13/2005 at 09:33:28
From: Ted
Subject: Combinations

That clears a lot up with the name circular permutaion and confirms
what I thought on the solution.  Thanks.  The next step would be to
select those combinations where the pairs don't sit next to each
other.  In the four case of 1234, it would only be 1432.  Is there a
calculation for that?

Ted

Date: 08/14/2005 at 13:18:13
From: Doctor Wilko
Subject: Re: Combinations

Hi again Ted,

Let's develop the rationale behind these formulas a little more, using 
3 distinct people (we'll use 3 to keep the numbers small).

If you have 3 distinct people and you want to arrange them on a 
straight bench, then you can seat any of the three people in the first 
seat, any of the remaining two in the second seat, and finally the 
last person in the last seat.  This gives

  3! (3 factorial) = 3 * 2 * 1 = 

  6 different ways to arrange 3 distinct people on a bench.

The six arrangements would look like:

  123
  132
  213
  231
  312
  321

In general, you can arrange n distinct people on a bench in n! ways. 


Now, say you want to arrange those same three people around a circular 
table.  Because it's difficult for me to draw circles, imagine the
following arrangements of individuals sitting around a circular table
with the first spot being the "head spot" (or 12:00 on a clock if you
were looking down on the table) and the other two individuals going 
clockwise around the table.

  123 <-- 1st arrangement
  132 <-- 2nd arrangement
  213 <-- 2nd arrangement rotated clockwise one turn
  231 <-- 1st arrangement rotated clockwise two turns
  312 <-- 1st arrangement rotated clockwise one turn
  321 <-- 2nd arrangement rotated clockwise two turns

As you can see from above there are really only two distinct 
circular permutations of three people around a circle table.  

The rest of the arrangements are just _rotations_ of the two 
distinct arrangements (cyclic permutations).

So in this case you take the 3! ways to arrange the people around a 
circular table and divide by 3, which is the number of rotations of 
each distinct permutation,

  (3! / 3) = (3 * 2 * 1) / 3 = 2 * 1 = 2! = 

  2 different ways to arrange 3 distinct people at a circular table.

The two distinct arrangements would be:

  123
  132

In general, you can arrange n distinct people around a circular 
table in [n!/n] or (n-1)! ways.


Now we're leading up to your question.  

We've arranged 3 people on a straight bench (there are 3! ways), and 
3 people around a circular table (2! ways).  But what if we don't 
want any person to have the same two neighbors around a circular 
table? 

If we look at our two arrangements of three people around a circular 
table, we see that the second arrangement is the equivalent 
counterclockwise arrangement of the first arrangement.

  123 (clockwise arrangement)
  132 (same order, just counterclockwise)

Another way to look at it is in the first arrangement person 2 has 3 
on his left and 1 on his right, and on the second arrangement person 
2 has 3 on his right and 1 on his left.  In both arrangements, person 
2 is still between 1 and 3 even though the order is different.  So 
these two arrangements can't fulfill our requirement that NO person 
has the same two neighbors.

In the case of three people, there is only ONE distinct arrangement 
around a table where no person has the same two neighbors, namely

  123

You may have to draw a picture to see this, but it turns out for any 
circular permutations of distinct objects, there is a clockwise and 
counterclockwise direction of each arrangement.  Because of this, we 
have to divide the answer we get by arranging n people around a 
circular table by 2.

In general, you can arrange n distinct people around a circular 
table, where no person has the same two neighbors, in [(n-1)! / 2] 
ways.

So for your problem you were arranging 4 people around a circular 
table and found that there are 3! or 6 ways to do this:

  1234 (1st arrangement)
  1243 (2nd arrangement)
  1324 (3rd arrangement)
  1342 (counterclockwise equivalent of 2nd arrangement)
  1423 (counterclockwise equivalent of 3rd arrangement)
  1432 (counterclockwise equivalent of 1st arrangement)

If you want to set up card games with four people and change the order 
each time you meet so that each game a person will not have the same 
two neighbors, then there are (3!/2) or 3 ways to do this,

  1234 (1st time you meet, play like this)
  1243 (2nd time you meet, play like this)
  1324 (3rd time you meet, play like this)

Then keep cycling back through these three arrangements if you want to 
keep the four people from not having the same two neighbors each time 
you meet.


Note that these problems do grow complicated very quickly.  There are 
problems where there are restrictions on how people can sit (husbands 
and wives together, males and females alternating seats, etc…).  Also 
these problems can be difficult if all the items are NOT distinct 
(e.g., different ways to arrange 6 red, 5 blue, and 3 yellow beads on 
a necklace).  Even listing the combinations can become more cumbersome 
when you start getting into five or six people sitting around a table.  
So, while your problem was much more manageable (because you have only 
four distinct people), these kinds of problems can become very 
complicated very fast.


Does this help?  Please write back if you have further questions.

- Doctor Wilko, The Math Forum
  http://mathforum.org/dr.math/