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
KEYWORD
nonn,easy
AUTHOR
Yasutoshi Kohmoto, Aug 15 2007
EXTENSIONS
More terms from Max Alekseyev, Sep 29 2007
STATUS
approved