Criss-crossing an n-gon

Leroy Quet qq-quet at mindspring.com
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 
once.

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 
permutations:
[1,5,3,6,2,4]
[1,4,5,2,6,3]
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.)

6,8,10,24,70,..

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

Is this last sequence in the EIS?

What else can be said about this?

thanks,
Leroy Quet





More information about the SeqFan mailing list