A392336 Number of maximal matchings in the n-necklace graph.

3, 25, 111, 545, 2623, 12673, 61183, 295425, 1426431, 6887425, 33255423, 160571393, 775307263, 3743514625, 18075287551, 87275208705, 421401985023, 2034708774913, 9824443039743, 47436607258625, 229044201193471, 1105923233808385, 5339869740007423

Offset

1,1

Links

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

Eric Weisstein's World of Mathematics, Maximal Independent Edge Set.

Eric Weisstein's World of Mathematics, Necklace Graph.

Index entries for linear recurrences with constant coefficients, signature (3,8,4).

Formula

a(n) = (-1)^n+A170931(n).

a(n) = (-1)^n+2^n*A002203(n).

a(n) = 3*a(n-1)+8*a(n-2)+4*a(n-3).

G.f.: x*(-3-16*x-12*x^2)/(-1+3*x+8*x^2+4*x^3).

a(n) + a(n+1) = A108051(n+2), n>=1. - R. J. Mathar, Feb 27 2026

Mathematica

Table[(-1)^n + 2^n LucasL[n, 2], {n, 20}]
LinearRecurrence[{3, 8, 4}, {3, 25, 111}, 20]
CoefficientList[Series[(-3 - 16 x - 12 x^2)/(-1 + 3 x + 8 x^2 + 4 x^3), {x, 0, 20}], x]

Crossrefs

Sequence in context: A360788 A373682 A166899 * A201534 A059457 A165206

Adjacent sequences: A392333 A392334 A392335 * A392337 A392338 A392339

Keyword

nonn,easy

Author

Eric W. Weisstein, Feb 15 2026

Status

approved