A387596 Number of maximum matchings in the n-Cameron graph.

7, 20, 53, 147, 401, 1105, 3034, 8349, 22957, 63155, 173711, 477852, 1314449, 3615799, 9946297, 27360297, 75262642, 207032537, 569505065, 1566594819, 4309389479, 11854270468, 32608731853, 89700113451, 246747109345, 678752052689, 1867111432010, 5136050915445

Offset

1,1

Links

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

Eric Weisstein's World of Mathematics, Cameron Graph.

Eric Weisstein's World of Mathematics, Maximum Independent Vertex Set.

Index entries for linear recurrences with constant coefficients, signature (3,1,-5,1).

Formula

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

G.f.: (x*(-7+x+14*x^2-3*x^3))/(-1+3*x+x^2-5*x^3+x^4).

Mathematica

Table[RootSum[-1 + 5 # - #^2 - 3 #^3 + #^4 &, 74 #^n - 262 #^(n + 1) + 122 #^(n + 2) + 149 #^(n + 3) &]/1327, {n, 20}]
LinearRecurrence[{3, 1, -5, 1}, {7, 20, 53, 147}, 20]
CoefficientList[Series[(-7 + x + 14 x^2 - 3 x^3)/(-1 + 3 x + x^2 - 5 x^3 + x^4), {x, 0, 20}], x]

Crossrefs

Sequence in context: A320681 A048755 A055267 * A218843 A219422 A209546

Adjacent sequences: A387593 A387594 A387595 * A387597 A387598 A387599

Keyword

nonn,easy

Author

Eric W. Weisstein, Sep 02 2025

Status

approved