login
A354228
Number of partitions of the multigraph G_n (defined below) into "strokes".
5
1, 6, 58, 578, 5766, 57810, 580310, 5829538, 58575686, 588641522, 5915670070, 59451845314, 597489270438, 6004768803090, 60348023150742, 606498938168290, 6095328830488582, 61258206225329970, 615646518692614390, 6187263150038580994
OFFSET
1,2
COMMENTS
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.
FORMULA
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).
MATHEMATICA
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 *)
CROSSREFS
Previously A131519 was thought to be this sequence.
Sequence in context: A004301 A223030 A292574 * A073848 A141382 A212426
KEYWORD
nonn,changed
AUTHOR
STATUS
approved