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

%I #41 Jul 18 2022 20:42:12

%S 2,6,12,22,40,74,140,270,528,1042,2068,4118,8216,16410,32796,65566,

%T 131104,262178,524324,1048614,2097192,4194346,8388652,16777262,

%U 33554480,67108914,134217780,268435510,536870968,1073741882,2147483708

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

%C 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}

%C See the definition of "stroke" in A089243.

%C A partition of a graph G into strokes S_i must satisfy the following conditions, where H is a digraph on G:

%C - Union_{i} S_i = H,

%C - i != j => S_i and S_j do not have a common edge,

%C - i != j => S_i U S_j is not a directed path,

%C - For all i, S_i is a dipath.

%C 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

%H G. C. Greubel, <a href="/A131520/b131520.txt">Table of n, a(n) for n = 1..1000</a>

%H James East, Jitender Kumar, James D. Mitchell, and Wilf A. Wilson, <a href="https://arxiv.org/abs/1706.04967">Maximal subsemigroups of finite transformation and partition monoids</a>, arXiv:1706.04967 [math.GR], 2017. [_James Mitchell_ and _Wilf A. Wilson_, Jul 21 2017]

%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (4,-5,2).

%F a(n) = 2*(n-1) + 2^n = 2*A006127(n-1).

%F G.f.: 2*x*(1 - x - x^2)/((1-x)^2 * (1-2*x)). - _R. J. Mathar_, Nov 14 2007

%F a(n) = 4*a(n-1)-5*a(n-2)+2*a(n-3). - _Wesley Ivan Hurt_, May 20 2021

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

%t Table[2^n + 2*(n-1), {n, 30}] (* _G. C. Greubel_, Feb 13 2021 *)

%o (Sage) [2^n + 2*(n-1) for n in (1..30)] # _G. C. Greubel_, Feb 13 2021

%o (Magma) [2^n + 2*(n-1): n in [1..30]]; // _G. C. Greubel_, Feb 13 2021

%Y Cf. A131518, A173740, A354228.

%K nonn,easy

%O 1,1

%A _Yasutoshi Kohmoto_, Aug 15 2007

%E More terms from _Max Alekseyev_, Sep 29 2007