0,2

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

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

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.

(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

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

Sequence in context: A361326 A390850 A280016 * A122534 A101135 A280054

Adjacent sequences: A089240 A089241 A089242 * A089244 A089245 A089246

nonn,walk

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

approved