A290700 Number of minimal edge covers in the n-prism graph.

1, 5, 25, 49, 141, 389, 1009, 2761, 7441, 19925, 53769, 144721, 389325, 1048325, 2821665, 7594761, 20444065, 55029413, 148124153, 398713969, 1073231821, 2888859781, 7776063377, 20931130057, 56341150641, 151655712629, 408217654249, 1098815597201

Offset: 1

Author

Eric W. Weisstein, Aug 09 2017

Keywords

• nonn

Comments

The n-prism graph is well defined for n >= 3. Sequence extended to n = 1 using recurrence. - Andrew Howroyd, Aug 10 2017

Links

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

Crossrefs

Cf. A123304.

Programs

Mathematica

Table[2 Cos[n Pi/2] + RootSum[-1 + # + #^2 + #^3 &, #^n &] -
  RootSum[1 - 2 #^2 - 2 #^3 + #^4 &, -2 #^(n + 2) - 2 #^(n + 3) + #^(n + 4) &], {n, 20}]
LinearRecurrence[{1, 2, 6, 2, 2, -2, -2, -1, 1}, {1, 5, 25, 49, 141, 389, 1009, 2761, 7441}, 20]
CoefficientList[Series[-( (1 + 4 x + 18 x^2 + 8 x^3 + 10 x^4 - 12 x^5 - 14 x^6 - 8 x^7 + 9 x^8)/((1 + x^2) (-1 - x - x^2 + x^3) (1 - 2 x - 2 x^2 + x^4))), {x, 0, 20}], x]

PARI

Vec((1 + 4*x + 18*x^2 + 8*x^3 + 10*x^4 - 12*x^5 - 14*x^6 - 8*x^7 + 9*x^8)/((1 - 2*x - 2*x^2 + x^4)*(1 + x + x^2 - x^3)*(1 + x^2))+O(x^30)) \\ Andrew Howroyd, Aug 10 2017

Formula

From Andrew Howroyd, Aug 10 2017: (Start)

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

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

(End)

Extensions

a(1)-a(2) and terms a(9) and beyond from Andrew Howroyd, Aug 10 2017