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