[seqfan] Re: Partition into Stroke
Richard J. Mathar
mathar at mpia-hd.mpg.de
Tue Feb 1 20:53:21 CET 2022
Here is an attempt to interpret the strokes in A131518 by reverse-engineering the formulas:
A088009(n) is the number of ways of splitting the elements {1,2,...,n} into
lists, where each list has an odd number of elements. E.g. for n=4 the 25 sets of lists are
[1],[2],[3],[4]
[1],[2,3,4]
[1],[2,4,3]
[1],[3,2,4]
[1],[3,4,2]
[1],[4,2,3]
[1],[4,3,2]
[2],[1,3,4]
[2],[1,4,3]
[2],[3,1,4]
[2],[3,4,1]
[2],[4,1,3]
[2],[4,3,1]
....
In A131518 consider two vertices and n edges labeled 1,...,n. Then A088009(n) is the
number of ways of generating paths starting at v1 with the first walk and walking
along the edges in the first list of A088009 (first stroke), lifting the "pen"
and to start again a second walk at the "other" vertex according to the 2nd edge list etc.
Because A088009 considers only lists with odd numbers of elements, each walk
ends on the "other" vertex, so the request that no two consecutive walks
can be combined (united) to a single path is fulfilled [because the stroke
from the end of a previous walk to the next would be missing...].
The other A088009(n) is the same thing of starting a path at v2 with the
first edge list, basically inverting all edges (arcs) in the paths already generated.
So 2*A088009(n) makes sense. It's important to consider vertices
and edges labelled, and to consider all edges be switchable in direction
according to need.
For even n, there are again 2*A088009(n) sequences of walks, starting
each the walk in each list at either v1 or v2 as above.
In addition there are n!*(n/2+1) = A327882(n/2+1) more sequences of walks
which are (see Max's comment) admissable because we can start a walk
at v1 AND end it at v1 and a second walk at v2 AND end at v2. This construction
still means that the union of the two paths is not another path, because
a step from v1 to v2 would be missing to unite them.
Then the n! is the number of ways of sorting the n edges, and the factor
of n/2+1 is the number of ways of cutting this list of n edges into two
pieces/walks (of even length), starting the first sublist at v1 and
the second sublist at v2. In detail: the edge list e1,e2,e3... ,en
can be split after e2, after e4, after e6 etc in n/2-1 ways, not be cut at
all (single path) in one way and started at v1, and not be cut
at all (single path) in one way and started at v2.
More information about the SeqFan
mailing list