|
| |
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
Edited, terms a(0)-a(1) and a(6) corrected, a(7)-a(13) added by Max Alekseyev, Oct 20 2022
|
|
|
STATUS
|
approved
|
| |
|
|
