# Self-intersecting polygonal chains in a hexagon [closed]

This is continuation of this Q&A. Given a regular hexagon with center at point O: Question: How many self-intersecting polygonal chains are there that connect 7 points?

The self-intersecting polygonal chain passes through each point once and chains should be non-isomorphic.

• What is a reason of down-vote?
– Nick
Dec 2, 2020 at 10:24
• It does not feel much like a puzzle to me, as it mostly seems like boring case-work (especially if we have to subtract the non-intersecting ones), without much clever insight needed. Dec 2, 2020 at 10:36
• Then again, maybe I'm biased because of this question about paths in a 3x3 square which was similar and involved way too many cases to be fun to answer. Dec 2, 2020 at 11:23
• @JaapScherphuis subtracting the non-intersecting is easy. There's only 6 of them. It's removing the ones that cross over the midpoint without stopping that's the annoying part. Dec 2, 2020 at 18:58

Edit: this answer is not correct. It solves for undirected cycles (and I believe does so correctly) but the number for chains is different. I will not be solving for chains. Answer left in place in case it is somehow useful for future attempts.

This is pretty basic math, if a bit convoluted. There are 6 non-intersecting polygonal chains that cover all 7 points (depending on which direction you point the slice). Anything else would intersect.

Further, the chords that cross the center are non-legal, as they'd cause the center point to be touched more than once.

The total number of polygonal chains if you ignore those limitations? Simply 6!/2. You start at A. You have 6 options of where to go. After that 5, after that 4, and so on. Then you cut the result in half to acknowledge that it's not a directed graph.

The number of graphs where a line cross over the midpoint is equivalent to the number where B and E is one point, plus where C and F are one point, plus where A and D are one point, less the number where more than one of those is true. In this case, that means 3x5!/2 - x. Th x is the cases where two of those are true (subtract once, because it counts once rather than twice), less the case where all three are true (which shows up 3 times in the minuend, but three times also in the subtrahend, so we need to add it back in because it's supposed to show up once).

So, the total number of cases where it crosses the midpoint at least once without stopping is (3x5! - 3x4! + 3!)/2. The non-intersecting is, as mentioned, 6.

The final result is (6! - 3x5! + 3x4! - 3!)/2 - 6, which (I believe) comes to 207

• There are more than 6 non-intersecting ones, for example abcdefo, bacdefo, abcdeof, bacdeof, abcdoef, bacdoef, abcdofe, bacdofe, abcodef, abcofed, abcofde, abcodfe, bacodfe, bacofde, and possibly more that I missed. "You start at A" - What about starting at O (and then A)? Dec 2, 2020 at 20:09
• @JaapScherphuis Ah! You're right. I was looking at cycles, rather than chains. Ugh. You're also right that the answer for chains is a lot uglier. Dec 3, 2020 at 14:22