Criss-crossing an n-gon

Leroy Quet qq-quet at
Wed Sep 8 19:41:28 CEST 2004

Start with a convex n-gon.

We can express a permutation of {1,2,3,...n} by drawing a path (of 
connected line-segments) which visits every vertex of the n-gon exactly 

Now, how many permutation-paths of {1,2,3,...,n} are there where, AS the 
path is being drawn (before any future segments are drawn), each m_th 
line-segment (connecting 2 vertexes) crosses exactly floor((m-1)/2) 
earlier-drawn segments?

We have 2 situations here:
1) there are n segments, and the last segment connects back to the 
starting vertex.
2) there are (n-1) segments, and the first and last vertexes are not 
connected by a segment.

For example, unless I erred, for n = 6 and situation (2) we have the 
and there rotations/reflections for a total of 24 such permutations.

Unless I erred (which is likely), the sequence of numbers of such 
permutations begins:
(Offset is 3. For (n-1) segments.)


Not distinguishing between different rotations/reflections, we have the 
(Again, first term is a(3).)

Is this last sequence in the EIS?

What else can be said about this?

Leroy Quet

More information about the SeqFan mailing list