Circular PermutationsDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/