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

%I #58 Apr 01 2024 09:13:20

%S 3,1,7,13,35,81,199,477,1155,2785,6727,16237,39203,94641,228487,

%T 551613,1331715,3215041,7761799,18738637,45239075,109216785,263672647,

%U 636562077,1536796803,3710155681,8957108167,21624372013,52205852195

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

%C 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

%C Also the number of vertex covers for Y_n. - _Eric W. Weisstein_, Jan 04 2014

%H Vincenzo Librandi, <a href="/A051927/b051927.txt">Table of n, a(n) for n = 0..1000</a>

%H Vaclav Kotesovec, <a href="https://oeis.org/wiki/User:Vaclav_Kotesovec">Non-attacking chess pieces</a>, 6ed, 2013, pp. 400-401.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/IndependentVertexSet.html">Independent Vertex Set</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/PrismGraph.html">Prism Graph</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/VertexCover.html">Vertex Cover</a>

%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (1,3,1).

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

%F G.f.: (3-2x-3x^2)/((1-2x-x^2)(1+x)). - _Michael Somos_, Apr 07 2003

%F 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

%F a(n) = A002203(n) + (-1)^n. - _Vladimir Reshetnikov_, Sep 15 2016

%F a(n)+a(n+1) = 4*A000129(n+1). - _R. J. Mathar_, Feb 13 2020

%F E.g.f.: cosh(x) + 2*exp(x)*cosh(sqrt(2)*x) - sinh(x). - _Stefano Spezia_, Mar 31 2024

%p A051927 := x -> (1+sqrt(2))^x+(-1)^x+(1-sqrt(2))^x;

%p seq(simplify(A051927(i)),i=0..28); # _Peter Luschny_, Aug 13 2012

%t CoefficientList[Series[(3 - 2 x - 3 x^2) / ((1 - 2 x - x^2) (1 + x)), {x, 0, 40}], x] (* _Vincenzo Librandi_, May 04 2013 *)

%t Table[LucasL[n, 2] + (-1)^n, {n, 0, 20}] (* _Vladimir Reshetnikov_, Sep 15 2016 *)

%t LinearRecurrence[{1, 3, 1}, {1, 7, 13}, {0, 20}] (* _Eric W. Weisstein_, Sep 27 2017 *)

%o (PARI) a(n)=polcoeff((3-2*x-3*x^2)/(1-2*x-x^2)/(1+x)+x*O(x^n),n)

%o (Sage)

%o def A051927(x) : return (1+sqrt(2))^x+(-1)^x+(1-sqrt(2))^x

%o [A051927(i).round() for i in (0..28)] # _Peter Luschny_, Aug 13 2012

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

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

%Y Column 2 of A286513 and row 2 of A287376.

%Y Cf. A000129, A002203.

%K easy,nonn

%O 0,1

%A _Stephen G Penrice_, Dec 19 1999