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

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

Offset: 1

Author

Yasutoshi Kohmoto and Max Alekseyev, Jul 18 2022

Keywords

• nonn

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.

Links

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

Crossrefs

Previously A131519 was thought to be this sequence.

Cf. A131518, A131520.

Programs

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

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