A131518 -id:A131518 - cp's OEIS frontend

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

Yasutoshi Kohmoto, Aug 15 2007

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

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

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

Cf. A131518, A173740, A354228.

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

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

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

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

More terms from Max Alekseyev, Sep 29 2007

A131709 Number of partitions into "bus routes" of an n X 1 grid.

Original entry on oeis.org

1, 14, 104, 904, 8004, 71004, 630004, 5590004, 49600004, 440100004, 3905000004, 34649000004, 307440000004, 2727910000004, 24204700000004, 214767900000004, 1905632000000004, 16908641000000004, 150030090000000004, 1331214490000000004, 11811844000000000004, 104806295100000000004, 929944511000000000004, 8251382159000000000004, 73214376480000000000004, 649629943210000000000004

Offset: 0

Yasutoshi Kohmoto, Oct 03 2007, revised Nov 20 2007

If we make bus routes on a graph G, the routes should satisfy the following conditions.
1. One and only one route exists on all edges of G
2. Terminals of two different routes don't meet on the same point
This definition is equivalent to a "partition of graph G into undirected strokes". It is defined as follows.
Given an undirected graph G=(V,E), its partition into strokes is a collection of directed edge-disjoint paths (viewed as sets of directed edges) on V such that (i) union of any two paths is not a path; (ii)union of corresponding undirected paths is E.
So the case of undirected paths is the following.
Definition. Given an undirected graph G=(V,E), its partition into strokes is a collection of edge-disjoint paths (viewed as sets of edges) on V such that (i) union of any two paths is not a path; (ii) union of paths is E.
The first differences 90, 800, 7100, 63000, 559000,... are A177187 multiplied by powers of 10. - R. J. Mathar, Nov 02 2016

Colin Barker, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (11,-20,10).

Cf. A131518.

Vec(-(30*x^3-30*x^2+3*x+1)/((x-1)*(10*x^2-10*x+1)) + O(x^100)) \\ Colin Barker, Feb 11 2015

a(n) = Product_{v_i} m_i + Sum_{c_j} (se_j - 1)*(Product_{v_k E (G_n-c_j)} m_k - {number of partitions of (G_n-c_i) which has cycles}) where:
v_i E V_n, G_n={V_n,E_n}, "E" means element
m_i means number of matching of incident edges of v_i
c_j means cycles in G_n
se_j means number of start-end points in c_j
v_k E G_n and not(v_k E c_j)
m_k means number of matching of incident edges of v_k
If (G_n-c_j) is empty then Product_{v_k E (G_n-c_j)} m_k = 1.
For n>=3, a(n)=10*(a(n-1)-a(n-2))+4. - Max Alekseyev, Apr 25 2013
G.f.: -(30*x^3-30*x^2+3*x+1) / ((x-1)*(10*x^2-10*x+1)). - Colin Barker, Feb 11 2015

Terms a(4) onward from Max Alekseyev, Apr 25 2013

A354228 Number of partitions of the multigraph G_n (defined below) into "strokes".

Original entry on oeis.org

1, 6, 58, 578, 5766, 57810, 580310, 5829538, 58575686, 588641522, 5915670070, 59451845314, 597489270438, 6004768803090, 60348023150742, 606498938168290, 6095328830488582, 61258206225329970, 615646518692614390, 6187263150038580994

Offset: 1

Yasutoshi Kohmoto and Max Alekseyev, Jul 18 2022

nonn

Here G_n = {V_n, E_n}, V_n = {v_1, v_2, ..., v_n}, E_n = {e_1, e_2, ..., e_{n-1}, f_1, f_2, ..., f_{n-1}}. For all i, e_i = f_i = v_iv_{i+1} although e_i and f_i are considered distinct.

Given an undirected multigraph G = (V,E) with labeled edges, its partition into strokes is a collection of directed edge-disjoint paths (viewed as sets of directed edges) on V such that (i) union of any two paths is not a path; (ii) union of corresponding undirected paths is E.

Index entries for linear recurrences with constant coefficients, signature (13,-22,-88,112).

Previously A131519 was thought to be this sequence.

Cf. A131518, A131520.

CoefficientList[Series[x (1-2x)^2(1-3x-14x^2)/(1-13x+22x^2+88x^3-112x^4),{x,0,20}],x] (* or *) LinearRecurrence[{13,-22,-88,112},{0,1,6,58,578,5766},30] (* Harvey P. Dale, Oct 31 2024 *)

For n >= 6, a(n) = 13*a(n-1) - 22*a(n-2) - 88*a(n-3) + 112*a(n-4).

O.g.f.: x * (1-2*x)^2 * (1 - 3*x - 14*x^2) / (1 - 13*x + 22*x^2 + 88*x^3 - 112*x^4).

A089243 Number of partitions into strokes of the star graph with n edges on the plane, up to rotations and reflections around the center node.

Original entry on oeis.org

1, 2, 3, 4, 9, 22, 61, 200, 689, 3054, 12110, 61132, 274264, 1515134, 7498195, 44301928, 238206692, 1490114770, 8605537805, 56612534420, 348083793872, 2396294898646, 15577794980189, 111781094032984, 763986810923430, 5695585712379834

Offset: 0

Yasutoshi Kohmoto

A "stroke" is defined as follows. If the following conditions are satisfied then the partition to directed paths on a directed graph is called "a partition to strokes on a directed graph", and all directed paths in the partition are called "strokes". C.1. Two different directed paths in a partition do not have the same edges. C.2. A union of two different paths in a partition does not become a directed path. In other words, a "stroke" is a locally maximal path on a directed graph.
This sequence has its origin in the strokes made when writing Japanese Kanji.
The value a(1) is ambiguous as it depends on the definition of the star graph with n = 1 edge. If one of the edge endpoints is labeled as the star center, then we have the current value a(1) = 2. However, if the center is not distinguished, then a(1) would be 1. - Max Alekseyev, May 04 2023

			For n = 3, call the center node "0" and the terminal nodes "1", "2", "3".
Four partitions exist as follows:
  {1->0->2, 0->3}
  {1->0->2, 3->0}
  {1->0, 2->0, 3->0}
  {0->1, 0->2, 0->3}.
So a(3) = 4.

Christian Sievers, Table of n, a(n) for n = 0..728

Cf. A131518, A131520, A354228, A131709, A357857, A357895.

p(n,t,o)=o*sum(k=0,(n-1)/2,n!/(k!*(n-2*k)!)*t^k)+if(n%2==0, n!/(n/2)!*t^(n/2));
a(n)=if(n==0,1,(sumdiv(n,d,eulerphi(n/d)*p(d,n/d,2)) + if(n%2,2*n*p((n-1)/2,2,1),n/2*p(n/2,2,2)+n*p(n/2-1,2,2)+n*p(n/2-1,2,1)))/(2*n)) \\ Christian Sievers, May 14 2023

Edited, terms a(0)-a(1) and a(6) corrected, a(7)-a(13) added by Max Alekseyev, Oct 20 2022

More terms from Christian Sievers, May 14 2023

A357895 Number of partitions of the complete graph on n vertices into strokes.

Original entry on oeis.org

1, 2, 12, 472, 104800

Offset: 1

Yasutoshi Kohmoto and Max Alekseyev, Oct 18 2022

Partition of graph G=(V,E) into strokes is a collection of directed edge-disjoint trails (viewed as sets of directed edges, cf. A357857) in G such that (i) no two trails can be concatenated into a single one; (ii) the corresponding undirected edges form a partition of E.

Cf. A089243, A131518, A131520, A354228, A131709, A357857.

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

Sage

Formula

Extensions

A131709 Number of partitions into "bus routes" of an n X 1 grid.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

Extensions

A354228 Number of partitions of the multigraph G_n (defined below) into "strokes".

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A089243 Number of partitions into strokes of the star graph with n edges on the plane, up to rotations and reflections around the center node.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Extensions

A357895 Number of partitions of the complete graph on n vertices into strokes.

Views

Author

Keywords

Comments

Crossrefs