A089243 -id:A089243 - 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

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.

A135443 Number of maximal directed trails in the labeled n-ladder graph P_2 X P_n.

Original entry on oeis.org

2, 8, 12, 40, 84, 144, 220, 312, 420, 544, 684, 840, 1012, 1200, 1404, 1624, 1860, 2112, 2380, 2664, 2964, 3280, 3612, 3960, 4324, 4704, 5100, 5512, 5940, 6384, 6844, 7320, 7812, 8320, 8844, 9384, 9940, 10512, 11100, 11704, 12324, 12960, 13612, 14280

Offset: 1

Yasutoshi Kohmoto, Feb 18 2008

			For n = 4 the graph is
  .__.__.__.
  |__|__|__|
Names of nodes:
  1 2 3 4
  a b c d
Maximal directed paths which start from node 3:
  34dcba123c
  34dc32ba12
  34dc321ab2
  34dc321abc
  3cd432ba12
  3cd4321ab2
  3cd4321abc
  3cba1234dc
  321abc34dc
  321abcd43c
There are also paths from nodes c,b,2. So a(4) = 4*10 = 40.

Apart from initial terms sequence is the same as A033586.

Cf. A003682, A089243.

For n > 2, a(n) = 4 * (n-2) * (2*n - 3) = A033586(n-2). - Max Alekseyev, May 04 2023

Edited and extended by Max Alekseyev, May 04 2023

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

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

Views

Author

Keywords

Comments

Crossrefs

A135443 Number of maximal directed trails in the labeled n-ladder graph P_2 X P_n.

Views

Author

Keywords

Examples

Crossrefs

Formula

Extensions