A question from my WeChat problem solvers group asking about enumeration of the non-self-crossing paths that start from a fixed point and visit all vertices exactly once in a regular octagon. The result has a surprising connection to OEIS A059204.

Brute force

Given two pairs of disjoint diagonals, check if they have internal cross:
In[]:=
nGon=8;
In[]:=
crossQ[s1_List,s2_List]:=Xor[​​Mod[(s2[[1]]-s1[[1]]),nGon]<Mod[(s1[[2]]-s1[[1]]),nGon],​​Mod[(s2[[2]]-s1[[1]]),nGon]<Mod[(s1[[2]]-s1[[1]]),nGon]​​]
The idea is rather simple: in the following diagram, if we travel from 2 to 7 clockwise, we meet the node 1 and not 3. Thus the diagonal 1-2 and 2-7 intersects. Similarly, if we travel from 2 to 7 clockwise, we see neither 4 or 6 in this interval. Therefore the diagonal 2-7 does not intersect with the diagonal 4-6 inside the polygon. What function gives True if the two inputs are True and False? Clearly, Xor is the right candidate.
Out[]=
The function extends the one above to check if there exists are pair of disjoint paths intersects each other internally:
crossPathQ[pth_List]:=Module[{crossq=False,diag,i,j},​​diag=Partition[pth,2,1];​​i=1;​​While[!crossq&&i<Length[diag]-1,​​j=i+2;While[!crossq&&j<=Length[diag],​​crossq=crossQ[diag[[i]],diag[[j]]];j++];i++];crossq]
Test the function on the two selected cases:
In[]:=
{Graph[Rule@@@Partition[#,2,1],​​VertexCoordinates->vc,VertexLabels->"Name"]&[{0,7,2,1,3,4,6,5}],​​Graph[Rule@@@Partition[#,2,1],​​VertexCoordinates->vc,VertexLabels->"Name"]&[{0,1,7,6,2,5,4,3}]}//Row
Out[]=
Indeed the first one has a internal intersection and the second is free of self-crossing:
In[]:=
{crossPathQ[{0,7,2,1,3,4,6,5}],crossPathQ[{0,1,7,6,2,5,4,3}]}
Out[]=
{True,False}
Let’s label the vertices of the regular octagon from 0 to 7 and fix the starting point of our Hamiltonian path at 0. Enumerate all paths:
In[]:=
Once[LaunchKernels[]];
allPath=Prepend[#,0]&/@Permutations[Range[nGon-1]];
The number of path with at least one crossing point:
In[]:=
res=ParallelCases[allPath,_?(crossPathQ[#]&)];
In[]:=
Length[res]
Out[]=
4976
Then the number of non-self-crossing paths is:
In[]:=
nonCross=Complement[allPath,res];
In[]:=
Length[nonCross]
Out[]=
64
Visualize all such paths:
In[]:=
circleLayout[n_]:=Table[{Cos[2π/n(i-1)],Sin[2π/n(i-1)]},{i,n}];​​vc=Thread[Range[0,nGon-1]->circleLayout[nGon]];
In[]:=
Partition[Graph[Rule@@@Partition[#,2,1],​​VertexCoordinates->vc,​​VertexLabels->Placed[Automatic,Center],​​VertexSize->0.35,EdgeStyle->Thickness[0.012],​​VertexLabelStyle->Directive[StandardRed,Bold,15]]&/@nonCross,8​​]//Grid[#,Dividers->All]&
Out[]=

The underlying pattern

If you change the value of the variable
nGon
in the part above, you will find two things:
◼
  • the number of non-self-crossing path is always
    k
    2
    where
    k
    is
    nGon-2
    .
    • ◼
  • the number of paths that crosses itself at least once is
    (k+1)!-
    k
    2
    where
    k
    is
    nGon-2
    . This is OEIS A059204.
    • In[]:=
    ResourceFunction["OEISSequenceData"]["A059204"]
    Out[]=
    {0,0,0,2,16,104,688,4976,40192,362624,3628288,39915776,478999552,6227016704,87178283008,1307674351616,20922789855232,355687428030464,6402373705596928,121645100408569856,2432902008176115712,51090942171708391424,1124000727777605582848}
    I stared at the 64-path diagram above for a while then I realize the hidden information for the sequence of right choice to avoid crossing. Lets work out the code below step by step to explain my observation. First, create a “Deque” data structure to store the initial conditions:
    In[]:=
    hs2=CreateDataStructure["Deque",Range[nGon-1]];
    This DS comes with built-in method to reduce the size of our code greatly. Notice that the first point of our path is zero. Once it is chosen, the only options we have for next point is either 1 or 7. Otherwise, say we choose 2, then we must have the internal intersection of the diagonal 1-X with 0-2 where X is any number but {0,2} or X itself. Assume we choose 0 ->1. Then the next neighbouring elements of 1 are 2 and 7. Again, if we choose 7, then the next neighboring elements for 7 are 2 and 6. If you write down the numbers in a list, you will find every time we discard one number in list and we are facing that either we should choose the head of the list or the tail. This fits exactly deque’s two-end “pop” function:
    In[]:=
    Clear[buildTree]
    In[]:=
    buildTree[ds:DataStructure["Deque",_]]/;(ds["Length"]==1):={Tree[ds["PopFront"],None]}
    In[]:=
    buildTree[ds:DataStructure["Deque",_]]/;(ds["Length"]>1):=With[{ds1=ds["Copy"],ds2=ds["Copy"]},​​{Tree[ds1["PopFront"],buildTree[ds1]],Tree[ds2["PopBack"],buildTree[ds2]]}​​]
    Then all paths fit all paths perfectly into a complete binary tree structure, illustrating the decision-making process at each step. Each node represents a choice between the head or tail of the deque, corresponding to the next point on the path. As we traverse the tree from the root to the leaves, we visualize all possible sequences of choices that result in non-self-crossing paths:
    In[]:=
    myTree=Tree[0,buildTree[hs2],AspectRatio->1/3,TreeElementLabelStyle->All->12]
    Out[]=
    The frequency of all leaves also obeys binomial distribution:
    If you are familiar with Pascal triangle, the second column is the seventh row in the triangular array:

    Bijection between Graph and Tree

    Because we have successfully represent all paths above in a binary tree, conversely, we should be able to encode the path with binary code. Indeed this is rather straightforward:
    Use the function below to translate a given binary code back to the path on our tree:
    Highlight a node if we have its binary code:

    Summary

    CITE THIS NOTEBOOK

    Hamiltonian-type paths without crossings in regular polygons​
    by Shenghui Yang​
    Wolfram Community, STAFF PICKS, September 7, 2025
    ​https://community.wolfram.com/groups/-/m/t/3542213