login
A089243
Number of partitions into strokes of the star graph with n edges on the plane, up to rotations and reflections around the center node.
4
1, 2, 3, 4, 9, 22, 61, 200, 689, 3054, 12110, 61132, 274264, 1515134, 7498195, 44301928, 238206692, 1490114770, 8605537805, 56612534420, 348083793872, 2396294898646, 15577794980189, 111781094032984, 763986810923430, 5695585712379834
OFFSET
0,2
COMMENTS
A "stroke" is defined as follows. If the following conditions are satisfied then the partition to directed paths on a directed graph is called "a partition to strokes on a directed graph", and all directed paths in the partition are called "strokes". C.1. Two different directed paths in a partition do not have the same edges. C.2. A union of two different paths in a partition does not become a directed path. In other words, a "stroke" is a locally maximal path on a directed graph.
This sequence has its origin in the strokes made when writing Japanese Kanji.
The value a(1) is ambiguous as it depends on the definition of the star graph with n = 1 edge. If one of the edge endpoints is labeled as the star center, then we have the current value a(1) = 2. However, if the center is not distinguished, then a(1) would be 1. - Max Alekseyev, May 04 2023
LINKS
EXAMPLE
For n = 3, call the center node "0" and the terminal nodes "1", "2", "3".
Four partitions exist as follows:
{1->0->2, 0->3}
{1->0->2, 3->0}
{1->0, 2->0, 3->0}
{0->1, 0->2, 0->3}.
So a(3) = 4.
PROG
(PARI) p(n, t, o)=o*sum(k=0, (n-1)/2, n!/(k!*(n-2*k)!)*t^k)+if(n%2==0, n!/(n/2)!*t^(n/2));
a(n)=if(n==0, 1, (sumdiv(n, d, eulerphi(n/d)*p(d, n/d, 2)) + if(n%2, 2*n*p((n-1)/2, 2, 1), n/2*p(n/2, 2, 2)+n*p(n/2-1, 2, 2)+n*p(n/2-1, 2, 1)))/(2*n)) \\ Christian Sievers, May 14 2023
CROSSREFS
KEYWORD
nonn,walk
EXTENSIONS
Edited, terms a(0)-a(1) and a(6) corrected, a(7)-a(13) added by Max Alekseyev, Oct 20 2022
More terms from Christian Sievers, May 14 2023
STATUS
approved