Christmas combinatorics
21 Dec, 2022 at 10:49  Posted in Statistics & Econometrics  13 CommentsYours 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?
13 Comments
Sorry, the comment form is closed at this time.

Recent Posts
 Proud father (personal)
 Sadeness
 Assumption uncertainty
 On the benefits — and dangers — of reading
 Using counterfactuals in causal inference
 On the limited value of randomization
 On fighting inflation
 Greatest intro in pop history
 Physics envy — a sure way to make economics useless
 Alone together
 Does randomization control for ‘lack of balance’?
 Visdom
 On the method of ‘successive approximations’
 The insufficiency of validity
 Mainstream economics — a vending machine view
Comments Policy
I like comments. Follow netiquette. Comments — especially anonymous ones — with pseudo argumentations, abusive language or irrelevant links will not be posted. And please remember — being a fulltime professor leaves only limited time to respond to comments.
Recent Comments
Jan Milch on Proud father (personal) Wayne McMillan on Proud father (personal) Lars Syll on Does randomization control for… lesdomes on Using counterfactuals in causa… Lars Syll on Using counterfactuals in causa… Huw Williams on Physics envy — a sure wa… lesdomes on Using counterfactuals in causa… rsm on On fighting inflation Lars Syll on On fighting inflation Christian Mueller on On fighting inflation rsm on Physics envy — a sure wa… Jan Milch on Visdom Sander Greenland (@L… on Does randomization control for… skippy on The insufficiency of vali… Kingsley Lewis on On the method of ‘succes… Reading List
Blogroll
Categories
 Economics (3,664)
 Education & School (261)
 Politics & Society (1,084)
 Statistics & Econometrics (870)
 Theory of Science & Methodology (481)
 Varia (1,530)
Archives
 Mar 2023 (25)
 Feb 2023 (33)
 Jan 2023 (32)
 Dec 2022 (38)
 Nov 2022 (25)
 Oct 2022 (27)
 Sep 2022 (29)
 Aug 2022 (34)
 Jul 2022 (30)
 Jun 2022 (29)
 May 2022 (27)
 Apr 2022 (33)
 Mar 2022 (26)
 Feb 2022 (35)
 Jan 2022 (41)
 Dec 2021 (45)
 Nov 2021 (42)
 Oct 2021 (31)
 Sep 2021 (44)
 Aug 2021 (39)
 Jul 2021 (50)
 Jun 2021 (49)
 May 2021 (52)
 Apr 2021 (35)
 Mar 2021 (61)
 Feb 2021 (47)
 Jan 2021 (33)
 Dec 2020 (46)
 Nov 2020 (41)
 Oct 2020 (55)
 Sep 2020 (37)
 Aug 2020 (45)
 Jul 2020 (50)
 Jun 2020 (49)
 May 2020 (69)
 Apr 2020 (62)
 Mar 2020 (51)
 Feb 2020 (66)
 Jan 2020 (42)
 Dec 2019 (54)
 Nov 2019 (74)
 Oct 2019 (62)
 Sep 2019 (53)
 Aug 2019 (75)
 Jul 2019 (73)
 Jun 2019 (69)
 May 2019 (86)
 Apr 2019 (94)
 Mar 2019 (78)
 Feb 2019 (72)
 Jan 2019 (56)
 Dec 2018 (52)
 Nov 2018 (62)
 Oct 2018 (69)
 Sep 2018 (53)
 Aug 2018 (50)
 Jul 2018 (44)
 Jun 2018 (63)
 May 2018 (63)
 Apr 2018 (61)
 Mar 2018 (59)
 Feb 2018 (40)
 Jan 2018 (63)
 Dec 2017 (47)
 Nov 2017 (44)
 Oct 2017 (53)
 Sep 2017 (48)
 Aug 2017 (43)
 Jul 2017 (37)
 Jun 2017 (45)
 May 2017 (48)
 Apr 2017 (45)
 Mar 2017 (47)
 Feb 2017 (35)
 Jan 2017 (56)
 Dec 2016 (63)
 Nov 2016 (58)
 Oct 2016 (42)
 Sep 2016 (45)
 Aug 2016 (40)
 Jul 2016 (57)
 Jun 2016 (43)
 May 2016 (45)
 Apr 2016 (41)
 Mar 2016 (70)
 Feb 2016 (58)
 Jan 2016 (40)
 Dec 2015 (32)
 Nov 2015 (51)
 Oct 2015 (59)
 Sep 2015 (47)
 Aug 2015 (34)
 Jul 2015 (42)
 Jun 2015 (50)
 May 2015 (48)
 Apr 2015 (45)
 Mar 2015 (54)
 Feb 2015 (41)
 Jan 2015 (54)
 Dec 2014 (51)
 Nov 2014 (51)
 Oct 2014 (54)
 Sep 2014 (52)
 Aug 2014 (69)
 Jul 2014 (72)
 Jun 2014 (48)
 May 2014 (47)
 Apr 2014 (38)
 Mar 2014 (51)
 Feb 2014 (54)
 Jan 2014 (50)
 Dec 2013 (67)
 Nov 2013 (60)
 Oct 2013 (77)
 Sep 2013 (74)
 Aug 2013 (45)
 Jul 2013 (54)
 Jun 2013 (39)
 May 2013 (43)
 Apr 2013 (48)
 Mar 2013 (58)
 Feb 2013 (41)
 Jan 2013 (47)
 Dec 2012 (66)
 Nov 2012 (62)
 Oct 2012 (71)
 Sep 2012 (76)
 Aug 2012 (38)
 Jul 2012 (76)
 Jun 2012 (114)
 May 2012 (64)
 Apr 2012 (49)
 Mar 2012 (42)
 Feb 2012 (35)
 Jan 2012 (45)
 Dec 2011 (39)
 Nov 2011 (68)
 Oct 2011 (61)
 Sep 2011 (63)
 Aug 2011 (53)
 Jul 2011 (21)
 Jun 2011 (30)
 May 2011 (47)
 Apr 2011 (45)
 Mar 2011 (19)
Blog at WordPress.com.
Entries and Comments feeds.
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/diningpuzzle/ with my own response, which differs considerably from yours, Lars.
Comments welcome here or there.
Happy New Year
Comment by Dave Marsay— 26 Dec, 2022 #
Am I interpreting your point correctly: The solution of 72 requires the chairs to be equivalent?
If so, I agree. Nonequivalent chairs require the use of permutations with formulation depending on how many of the chairs are distinguishable.
Please reply if I am missing your point.
Comment by piedmonthudson— 27 Dec, 2022 #
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.
Comment by Dave Marsay— 27 Dec, 2022 #
@ Prof. Syll
Please explain why P(2 must be seated together) = (51)!2!
@ Dave Marsay
Your link gives your solution as “6!5!2!=432”.
Your explanation seems to be erroneous because 6!5!2! = 480
Comment by Kingsley Lewis— 27 Dec, 2022 #
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.
Comment by Dave Marsay— 27 Dec, 2022 #
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
Comment by piedmonthudson— 24 Dec, 2022 #
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
Comment by piedmonthudson— 24 Dec, 2022 #
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! – (51)!2! = 120 – 48 = 72.
Merry Christmas 🙂
Comment by Lars Syll— 24 Dec, 2022 #
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:
1A, 2C
1A, 2D
1A, 2E
…
1F, 2B
1F, 2C
1F, 2D
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.
Comment by Kingsley Lewis— 24 Dec, 2022 #
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 dividebysix 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?
Comment by rsm— 24 Dec, 2022 #
First fix the positions of A and B, the nonspeaking colleagues. If the positions around the table are arbitrarily labeled 1,2,…,5, there are only 2 possible nonadjacent 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!/(nr)! = 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.
Comment by piedmonthudson— 24 Dec, 2022 #
Forgot my name (signature)
– – John Lounsbury
Comment by piedmonthudson— 24 Dec, 2022 #
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
Comment by rsm— 23 Dec, 2022 #