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