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

Author

Yasutoshi Kohmoto, Aug 15 2007

Keywords

• nonn
• easy

Comments

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

Examples

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

Links

• 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).

Crossrefs

Cf. A131518, A173740, A354228.

Programs

Magma

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

Mathematica

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

Sage

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

Formula

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

Extensions

More terms from Max Alekseyev, Sep 29 2007