A051927 Number of independent vertex sets in the n-prism graph Y_n = K_2 X C_n (n > 2).

3, 1, 7, 13, 35, 81, 199, 477, 1155, 2785, 6727, 16237, 39203, 94641, 228487, 551613, 1331715, 3215041, 7761799, 18738637, 45239075, 109216785, 263672647, 636562077, 1536796803, 3710155681, 8957108167, 21624372013, 52205852195

Offset

0,1

Comments

For n>1, a(n) is also the number of ways to place k non-attacking wazirs on a 2 X n horizontal cylinder, summed over all k>=0 (wazir is a leaper [0,1]). - Vaclav Kotesovec, May 08 2012

Also the number of vertex covers for Y_n. - Eric W. Weisstein, Jan 04 2014

Links

Vincenzo Librandi, Table of n, a(n) for n = 0..1000

Vaclav Kotesovec, Non-attacking chess pieces, 6ed, 2013, pp. 400-401.

Eric Weisstein's World of Mathematics, Independent Vertex Set

Eric Weisstein's World of Mathematics, Prism Graph

Eric Weisstein's World of Mathematics, Vertex Cover

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

Formula

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

G.f.: (3-2x-3x^2)/((1-2x-x^2)(1+x)). - Michael Somos, Apr 07 2003

Let A=[0, 1, 1;1, 1, 1;1, 1, 0] be the adjacency matrix of a triangle with a loop at a vertex. Then a(n)=trace(A^n). a(n)=(-1)^n+(1-sqrt(2))^n+(1+sqrt(2))^n. - Paul Barry, Jul 22 2004

a(n) = A002203(n) + (-1)^n. - Vladimir Reshetnikov, Sep 15 2016

a(n)+a(n+1) = 4*A000129(n+1). - R. J. Mathar, Feb 13 2020

E.g.f.: cosh(x) + 2*exp(x)*cosh(sqrt(2)*x) - sinh(x). - Stefano Spezia, Mar 31 2024

Maple

A051927 := x -> (1+sqrt(2))^x+(-1)^x+(1-sqrt(2))^x;
seq(simplify(A051927(i)), i=0..28); # Peter Luschny, Aug 13 2012

Mathematica

CoefficientList[Series[(3 - 2 x - 3 x^2) / ((1 - 2 x - x^2) (1 + x)), {x, 0, 40}], x] (* Vincenzo Librandi, May 04 2013 *)
Table[LucasL[n, 2] + (-1)^n, {n, 0, 20}] (* Vladimir Reshetnikov, Sep 15 2016 *)
LinearRecurrence[{1, 3, 1}, {1, 7, 13}, {0, 20}] (* Eric W. Weisstein, Sep 27 2017 *)

Prog

(PARI) a(n)=polcoeff((3-2*x-3*x^2)/(1-2*x-x^2)/(1+x)+x*O(x^n), n)
(Sage)
def A051927(x) : return (1+sqrt(2))^x+(-1)^x+(1-sqrt(2))^x
[A051927(i).round() for i in (0..28)] # Peter Luschny, Aug 13 2012
(Magma)  I:=[3, 1, 7]; [n le 3 select I[n] else Self(n-1) + 3*Self(n-2) + Self(n-3): n in [1..30]]; // Vincenzo Librandi, May 04 2013
(PARI) x='x+O('x^66); Vec( (3-2*x-3*x^2)/((1-2*x-x^2)*(1+x)) ) \\ Joerg Arndt, May 04 2013

Crossrefs

Column 2 of A286513 and row 2 of A287376.

Cf. A000129, A002203.

Sequence in context: A370381 A161380 A257852 * A322069 A194595 A219063

Adjacent sequences: A051924 A051925 A051926 * A051928 A051929 A051930

Keyword

easy,nonn

Author

Stephen G Penrice, Dec 19 1999

Status

approved