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.

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

Author

Yasutoshi Kohmoto

Keywords

• nonn
• walk

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

Examples

			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.
		

Links

• Christian Sievers, Table of n, a(n) for n = 0..728

Crossrefs

Cf. A131518, A131520, A354228, A131709, A357857, A357895.

Programs

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

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