login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A131520 Number of partitions of the graph G_n (defined below) into "strokes". 8
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 (list; graph; refs; listen; history; text; internal format)
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
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]
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
Sequence in context: A116658 A210065 A208850 * A086953 A101953 A084570
KEYWORD
nonn,easy
AUTHOR
Yasutoshi Kohmoto, Aug 15 2007
EXTENSIONS
More terms from Max Alekseyev, Sep 29 2007
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 09:04 EDT 2024. Contains 371240 sequences. (Running on oeis4.)