Christmas combinatorics

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

Combinatorics in .NET - Part I - Permutations, Combinations & Variations – try { } catch { } meYours 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

  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.

    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. Non-equivalent 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) = (5-1)!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 #

  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

    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 #

  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 🙂

    Comment by Lars Syll— 24 Dec, 2022 #

  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.

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

      Comment by rsm— 24 Dec, 2022 #

  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.

    Comment by piedmonthudson— 24 Dec, 2022 #

    • Forgot my name (signature)
      – – John Lounsbury

      Comment by piedmonthudson— 24 Dec, 2022 #

  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

    Comment by rsm— 23 Dec, 2022 #


Sorry, the comment form is closed at this time.

Blog at WordPress.com.
Entries and Comments feeds.