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,1

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

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

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

Example

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

Mathematica

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

Prog

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

Crossrefs

Cf. A131518, A173740, A354228.

Sequence in context: A116658 A210065 A208850 * A086953 A101953 A084570

Adjacent sequences: A131517 A131518 A131519 * A131521 A131522 A131523

Keyword

nonn,easy

Author

Yasutoshi Kohmoto, Aug 15 2007

Extensions

More terms from Max Alekseyev, Sep 29 2007

Status

approved