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