A354228 -id:A354228 - cp's OEIS frontend

A131520 Number of partitions of the graph G_n (defined below) into "strokes".

2, 6, 12, 22, 40, 74, 140, 270, 528, 1042, 2068, 4118, 8216, 16410, 32796, 65566, 131104, 262178, 524324, 1048614, 2097192, 4194346, 8388652, 16777262, 33554480, 67108914, 134217780, 268435510, 536870968, 1073741882, 2147483708

Offset: 1

Yasutoshi Kohmoto, Aug 15 2007

G_n = {V_n, E_n}, V_n = {v_1, v_2, ..., v_n}, E_n = {v_1 v_2, v_2 v_3, ..., v_{n-1} v_n, v_n v_1}
See the definition of "stroke" in A089243.
A partition of a graph G into strokes S_i must satisfy the following conditions, where H is a digraph on G:
- Union_{i} S_i = H,
- i != j => S_i and S_j do not have a common edge,
- i != j => S_i U S_j is not a directed path,
- For all i, S_i is a dipath.
a(n) is also the number of maximal subsemigroups of the monoid of partial order preserving mappings on a set with n elements. - James Mitchell and Wilf A. Wilson, Jul 21 2017

			Figure for G_4: o-o-o-o-o Two vertices on both sides are the same.

G. C. Greubel, Table of n, a(n) for n = 1..1000
James East, Jitender Kumar, James D. Mitchell, and Wilf A. Wilson, Maximal subsemigroups of finite transformation and partition monoids, arXiv:1706.04967 [math.GR], 2017. [_James Mitchell_ and _Wilf A. Wilson_, Jul 21 2017]
Index entries for linear recurrences with constant coefficients, signature (4,-5,2).

Cf. A131518, A173740, A354228.

[2^n + 2*(n-1): n in [1..30]]; // G. C. Greubel, Feb 13 2021

Table[2^n + 2*(n-1), {n, 30}] (* G. C. Greubel, Feb 13 2021 *)

[2^n + 2*(n-1) for n in (1..30)] # G. C. Greubel, Feb 13 2021

a(n) = 2*(n-1) + 2^n = 2*A006127(n-1).
G.f.: 2*x*(1 - x - x^2)/((1-x)^2 * (1-2*x)). - R. J. Mathar, Nov 14 2007
a(n) = 4*a(n-1)-5*a(n-2)+2*a(n-3). - Wesley Ivan Hurt, May 20 2021

More terms from Max Alekseyev, Sep 29 2007

A131518 Number of partitions of the graph G_n (defined below) into "strokes".

Original entry on oeis.org

2, 6, 14, 122, 362, 5282, 20582, 397154, 2027090, 46177922, 303147902, 7699478162, 63517159994, 1745540360930, 17676592058582, 517137940132802, 6290714838241442, 194139271606482434, 2782486941099788270, 90105513853333901042, 1495993248737211995402, 50671468195931300884322

Offset: 1

Yasutoshi Kohmoto, Aug 15 2007, Oct 03 2007

nonn

Here G_n = {V_n, E_n}, V_n = {v_1, v_2}, E_n = {e_1, e_2, ..., e_n}; for all i, e_i = v_1v_2.

Given an undirected graph G=(V,E), its partition into strokes is a collection of directed edge-disjoint paths (viewed as sets of directed edges) on V such that (i) union of any two paths is not a path; (ii) union of corresponding undirected paths is E.

			G_2 : o=o, two edges exist between v_1 and v_2.

G. C. Greubel, Table of n, a(n) for n = 1..440
R. J. Mathar, Explanation of the Alekseyev formula

Cf. A131520, A354228.

f[n_, k_]:= If[EvenQ[n-k], Binomial[(n+k)/2, k], 0];
A088009[n_]:= n!*Sum[f[n-1, k-1]/k!, {k, 0, n}];
A131518[n_]:= If[EvenQ[n], 2*A088009[n] + n!*(n/2 +1), 2*A088009[n]];
Table[A131518[n], {n,1,30}] (* G. C. Greubel, Feb 14 2021 *)

def f(n, k): return binomial((n+k)/2, k) if (n-k)%2==0 else 0
def A088009(n): return factorial(n)*sum(f(n-1, k-1)/factorial(k) for k in (0..n))
def A131518(n): return 2*A088009(n) + (n/2 +1)*factorial(n) if (n%2==0) else 2*A088009(n)
[A131518(n) for n in (1..30)] # G. C. Greubel, Feb 14 2021

For odd n, a(n)=2*A088009(n); for even n, a(n)=2*A088009(n)+n!*(n/2+1). The first term stands for partitions with paths starting and ending in different vertices. The second term (that exists only for even n) stands for partitions with paths starting and ending at the same vertex (there are at most 2 such paths starting and ending in v_1 and v_2 respectively, each path consists of even number of edges). - Max Alekseyev, Sep 29 2007

More terms from Max Alekseyev, Sep 29 2007

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.

Original entry on oeis.org

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

Yasutoshi Kohmoto

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

			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.

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

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

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

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

A131519 a(1) = 1, a(2) = 6, a(3) = 66, a(4) = 714, and a(n) = 11a(n-1) - 24a(n-3) for n >= 5.

Original entry on oeis.org

1, 6, 66, 714, 7710, 83226, 898350, 9696810, 104667486, 1129781946, 12194877966, 131631637962, 1420833250878, 15336488688474, 165542216262126, 1786864380862314, 19287432460962078, 208188743880291834, 2247191437542514638, 24256207433904571146, 261821751919823278590

Offset: 1

Yasutoshi Kohmoto, Aug 15 2007, Oct 03 2007

nonn

G. C. Greubel, Table of n, a(n) for n = 1..950
Index entries for linear recurrences with constant coefficients, signature (11, 0, -24).

Previously this sequence was thought to represent what now is A354228.

I:=[6, 66, 714]; [1] cat [n le 3 select I[n] else 11*Self(n-1) -24*Self(n-3): n in [1..30]]; // G. C. Greubel, Feb 14 2021

LinearRecurrence[{11, 0, -24}, {1, 6, 66, 714}, 30] (* G. C. Greubel, Feb 14 2021 *)

def A131519_list(prec):
    P. = PowerSeriesRing(ZZ, prec)
    return P( x*(1-2*x)*(1-3*x-6*x^2)/(1-11*x+24*x^3) ).list()
a=A131519_list(31); a[1:] # G. C. Greubel, Feb 14 2021

For n>4, a(n) = 11*a(n-1) - 24*a(n-3). - Max Alekseyev, Sep 29 2007

G.f.: x*(1-2*x)*(1-3*x-6*x^2)/(1-11*x+24*x^3). - R. J. Mathar, Nov 14 2007

More terms from Max Alekseyev, Sep 29 2007

Edited by Max Alekseyev, Jul 18 2022

A357895 Number of partitions of the complete graph on n vertices into strokes.

Original entry on oeis.org

1, 2, 12, 472, 104800

Offset: 1

Yasutoshi Kohmoto and Max Alekseyev, Oct 18 2022

Partition of graph G=(V,E) into strokes is a collection of directed edge-disjoint trails (viewed as sets of directed edges, cf. A357857) in G such that (i) no two trails can be concatenated into a single one; (ii) the corresponding undirected edges form a partition of E.

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

cp's OEIS Frontend

A131520 Number of partitions of the graph G_n (defined below) into "strokes".

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

Sage

Formula

Extensions

A131518 Number of partitions of the graph G_n (defined below) into "strokes".

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Sage

Formula

Extensions

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Extensions

A131519 a(1) = 1, a(2) = 6, a(3) = 66, a(4) = 714, and a(n) = 11*a(n-1) - 24*a(n-3) for n >= 5.

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Mathematica

Sage

Formula

Extensions

A357895 Number of partitions of the complete graph on n vertices into strokes.

Views

Author

Keywords

Comments

Crossrefs

A131519 a(1) = 1, a(2) = 6, a(3) = 66, a(4) = 714, and a(n) = 11a(n-1) - 24a(n-3) for n >= 5.