A284703 Number of maximal matchings in the n-prism graph.

1, 5, 10, 17, 51, 98, 211, 457, 964, 2095, 4489, 9638, 20723, 44469, 95550, 205225, 440777, 946808, 2033571, 4367947, 9381928, 20151345, 43283195, 92967814, 199685501, 428904403, 921243124, 1978737477, 4250128177, 9128846128, 19607840133, 42115660425

Offset: 1

Author

Eric W. Weisstein, Apr 01 2017

Keywords

• nonn

Comments

Sequence extrapolated to n=1 using recurrence. - Andrew Howroyd, May 16 2017

Links

• Andrew Howroyd, Table of n, a(n) for n = 1..200
• Eric Weisstein's World of Mathematics, Matching
• Eric Weisstein's World of Mathematics, Maximal Independent Edge Set
• Eric Weisstein's World of Mathematics, Prism Graph
• Index entries for linear recurrences with constant coefficients, signature (1,2, 1,-1,2,1,-1,-1).

Crossrefs

Cf. A284701, A286945, A284710, A102080, A068397, A123304.

Programs

Magma

I:=[1,5,10,17,51,98,211,457]; [n le 8 select I[n] else Self(n-1)+2*Self(n-2)+Self(n-3)-Self(n-4)+2*Self(n-5)+Self(n-6)-Self(n-7)-Self(n-8): n in [1..40]]; // Vincenzo Librandi, May 17 2017

Mathematica

LinearRecurrence[{1, 2, 1, -1, 2, 1, -1, -1}, {1, 5, 10, 17, 51, 98, 211, 457}, 40] (* Vincenzo Librandi, May 17 2017 *)
CoefficientList[Series[(-8 x^7 - 7 x^6 + 6 x^5 + 10 x^4 - 4 x^3 + 3 x^2 + 4 x + 1) / ((x^2 - x + 1) (x^3 - x - 1) (x^3 + 2 x^2 + x - 1)), {x, 0, 33}], x] (* Vincenzo Librandi, May 17 2017 *)
Table[2 Cos[n Pi/3] + RootSum[-1 - 2 # - #^2 + #^3 &, #^n &] +
  RootSum[-1 + #^2 + #^3 &, #^n &], {n, 20}] (* Eric W. Weisstein, May 17 2017 *)

PARI

Vec((-8*x^7-7*x^6+6*x^5+10*x^4-4*x^3+3*x^2+4*x+1)/((x^2-x+1)*(x^3-x-1)*(x^3+2*x^2+x-1))+O(x^20)) \\ Andrew Howroyd, May 16 2017

Formula

From Andrew Howroyd, May 16 2017 (Start)

a(n) = a(n-1)+2*a(n-2)+a(n-3)-a(n-4)+2*a(n-5)+a(n-6)-a(n-7)-a(n-8) for n>8.

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

(End)

Extensions

a(1)-a(2) and a(20)-a(32) from Andrew Howroyd, May 16 2017