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

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

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)

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

Prog

(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
(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

Crossrefs

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

Sequence in context: A174062 A020642 A067253 * A048822 A227753 A313989

Adjacent sequences: A284700 A284701 A284702 * A284704 A284705 A284706

Keyword

nonn

Author

Eric W. Weisstein, Apr 01 2017

Extensions

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

Status

approved