## Christmas combinatorics

21 Dec, 2022 at 10:49 | Posted in Statistics & Econometrics | 13 Comments

Yours truly has invited five of his colleagues to share a Christmas lunch with him around the circular dinner table in his kitchen. Unfortunately, two of the colleagues are not on speaking terms with each other, so they cannot be seated together. In how many ways can we be seated around the table?

1. This seems to me a very good example, but not in the way intended.

I have copied it to my https://djmarsay.wordpress.com/notes/puzzles/dining-puzzle/ with my own response, which differs considerably from yours, Lars.

Happy New Year

• Am I interpreting your point correctly: The solution of 72 requires the chairs to be equivalent?
If so, I agree. Non-equivalent chairs require the use of permutations with formulation depending on how many of the chairs are distinguishable.

• There is a subtle point here. Lars’ formulation of the question seems to suggest that the problem has rotational symmetry, which is what he assumes in his answer. He would find strong support for his view.

But he makes reference to a kitchen. Maybe this has six doors and is rotationally symmetric, but I doubt it. So should I take Lars’ formulation at some sort of ‘face value’ or should I query it or take account of my own experience of kitchens?

This distinction often matters, and seems to me to matter a lot in economics.

• @ Prof. Syll
Please explain why P(2 must be seated together) = (5-1)!2!

@ Dave Marsay
Your explanation seems to be erroneous because 6!-5!2! = 480

• Thanks. I also note that I forgot to allow comments. This just goes to show something important about mathematicians, if not mathematics. So another unintended example of something important!

My excuses are:
1. I worked out the actual number my way and then tried to adapt Lars’ method, but got it wrong.
2. Allowing comments used to be the default.

2. The first solution posted neglected to include the host (me).
Corrected solution:
There are now 6 indistinguishable chairs. The possible seating arrangements now fall into 2 different symmetry classes:
1. Arrangements 1 and 3 plus 1 and 5 for incompatible colleagues A and B have the same symmetry.
2. Arrangement 1 and 4 for A and B has different symmetry.

For symmetry 1:
P(4,4) = 4! = 24
The two possible arrangements (A,B) and (B,A) for positions 1 and 3, as well as two more for 1 and 5, are all identical by symmetry. Thus the number of possible arrangements here is 24.

For symmetry 2:
P(4,4) = 24
Because of symmetry, again (A,B) seating is the same as (B,A) and the number of possible arrangements is 24.

Ergo, the total number of possible seating arrangements is 24 + 24 = 48.
– – John Lounsbury

• I see my error. I identified a symmetry that does not exist in Symmetry 1:
A w B x y z is not the same as B w A x y z.
However, the symmetry between arrangements 1 and 3 vs. 1 and 5 is valid.
Symmetry 2:
Correctly identified previously.
Ergo, the total number of seating arrangements = 24 + 24 + 24 = 72.
Simple (minded?) error – incorrect result.
– – John Lounsbury

3. The answer is 72 (as suggested by rsm). The easiest way to get at this answer is to think in terms of a complement, so that P(2 not seated together) = P(no restrictions) – P(2 must be seated together). This gives (remember it’s ‘circle permutations’) 5! – (5-1)!2! = 120 – 48 = 72.
Merry Christmas 🙂

4. Label the chairs A,B,C,D,E,F.
Label the 6 colleagues (inc. the host) as 1,2,3,4,5,6 where 1 and 2 can’t be seated together.
There are 18 possible seatings of colleagues 1 and 2:
1-A, 2-C
1-A, 2-D
1-A, 2-E

1-F, 2-B
1-F, 2-C
1-F, 2-D
For each of the above the other seats could be occupied by 4! = 24 permutations of colleagues 3,4,5,6.
So there are 18 x 24 = 432 possible seatings.
——
rsm’s answer is too low by a factor of 6.
Possibly this is because his program unwittingly assumes colleague 1 is always on seat A.

• Does the alternate method in my program produce Kingsley’s answer, for which I personally have sympathy, but did I read Lars’ mind to figure out he wanted the divide-by-six solution?
.
May I also note that ChatGPT reproduced both piedmonthudson’s and Kingsley’s answers, but I was unable to teach it the answer Lars wanted?

5. First fix the positions of A and B, the non-speaking colleagues. If the positions around the table are arbitrarily labeled 1,2,…,5, there are only 2 possible non-adjacent positions for A and B: 1 and 3 plus 1 and 4. Thus there are 3 permutations of seating positions for the other 3 colleagues. For each of the 2 possible A and B positions:
P(3,3) = n!/(n-r)! = 3!/0! = 6
Also, each of the 2 positions for A and B can be B and A.
This implies that the result for all possible seating arrangements = 4 x P(3,3).
However, if the chairs are all equivalent (indistinguishable), each of the 4 possible seating arrangements is the same by symmetry.
Ergo, the number of seating arrangements is 6.

• Forgot my name (signature)
– – John Lounsbury

6. Is it wrong to generate all permutations numerically then reject the ones where 1 and 2 are sitting next to each other, yielding 72?
.
http://subbot.org/misc/combs5.rb.txt

Sorry, the comment form is closed at this time.