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

Links

Table of n, a(n) for n=1..20.

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

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.

Cf. A131518, A131520.

Sequence in context: A004301 A223030 A292574 * A073848 A141382 A212426

Adjacent sequences: A354225 A354226 A354227 * A354229 A354230 A354231

Keyword

nonn

Author

Yasutoshi Kohmoto and Max Alekseyev, Jul 18 2022

Status

approved