login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A051927 Number of independent vertex sets in the n-prism graph Y_n = K_2 X C_n (n > 2). 13
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 (list; graph; refs; listen; history; text; internal format)
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

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

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

Sequence in context: A113647 A161380 A257852 * A322069 A194595 A219063

Adjacent sequences:  A051924 A051925 A051926 * A051928 A051929 A051930

KEYWORD

easy,nonn

AUTHOR

Stephen G. Penrice (spenrice(AT)ets.org), Dec 19 1999

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 8 16:47 EST 2021. Contains 341953 sequences. (Running on oeis4.)