A287376 -id:A287376 - cp's OEIS frontend

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

Stephen G Penrice, Dec 19 1999

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

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

Column 2 of A286513 and row 2 of A287376.

Cf. A000129, A002203.

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

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

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

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

x='x+O('x^66); Vec( (3-2*x-3*x^2)/((1-2*x-x^2)*(1+x)) ) \\ Joerg Arndt, May 04 2013

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

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

A135597 Square array read by antidiagonals: row m (m >= 1) satisfies b(0) = b(1) = 1; b(n) = m*b(n-1) + b(n-2).

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 7, 5, 1, 1, 5, 13, 17, 8, 1, 1, 6, 21, 43, 41, 13, 1, 1, 7, 31, 89, 142, 99, 21, 1, 1, 8, 43, 161, 377, 469, 239, 34, 1, 1, 9, 57, 265, 836, 1597, 1549, 577, 55, 1, 1, 10, 73, 407, 1633, 4341, 6765, 5116, 1393, 89, 1, 1, 11, 91, 593, 2906

Offset: 1

N. J. A. Sloane, Mar 02 2008

For n > 1, the number of independent vertex sets in the graph K_m X P_{n-1}. For example, in K_3 X P_1 there are 4 independent vertex sets. - Andrew Howroyd, May 23 2017

			Array begins:
========================================================
m\n| 0 1 2  3   4    5     6      7       8        9
---|----------------------------------------------------
1  | 1 1 2  3   5    8    13     21      34       55 ...
2  | 1 1 3  7  17   41    99    239     577     1393 ...
3  | 1 1 4 13  43  142   469   1549    5116    16897 ...
4  | 1 1 5 21  89  377  1597   6765   28657   121393 ...
5  | 1 1 6 31 161  836  4341  22541  117046   607771 ...
6  | 1 1 7 43 265 1633 10063  62011  382129  2354785 ...
7  | 1 1 8 57 407 2906 20749 148149 1057792  7552693 ...
8  | 1 1 9 73 593 4817 39129 317849 2581921 20973217 ...
...

Andrew Howroyd, Table of n, a(n) for n = 1..1275

Cf. A121875, A000045, A287376.

Rows 2-11 are A001333, A003688, A015448, A015449, A015451, A015453-A015457.

A135597 := proc(m,c) coeftayl( (m*x-x-1)/(x^2+m*x-1),x=0,c) ; end: for d from 1 to 15 do for c from 0 to d-1 do printf("%d,",A135597(d-c,c)) ; od: od: # R. J. Mathar, Apr 21 2008

a[, 0] = a[, 1] = 1; a[m_, n_] := m*a[m, n-1] + a[m, n-2]; Table[a[m-n+1, n], {m, 0, 11}, {n, 0, m}] // Flatten (* Jean-François Alcover, Jan 20 2014 *)

O.g.f. row m: (mx-x-1)/(x^2+mx-1). - R. J. Mathar, Apr 21 2008

More terms from R. J. Mathar, Apr 21 2008

A051928 Number of independent sets of vertices in graph K_3 X C_n (n > 2).

Original entry on oeis.org

4, 1, 13, 34, 121, 391, 1300, 4285, 14161, 46762, 154453, 510115, 1684804, 5564521, 18378373, 60699634, 200477281, 662131471, 2186871700, 7222746565, 23855111401, 78788080762, 260219353693, 859446141835, 2838557779204, 9375119479441, 30963916217533

Offset: 0

Stephen G Penrice, Dec 19 1999

Colin Barker, Table of n, a(n) for n = 0..1000
C. Bautista-Ramos and C. Guillen-Galvan, Fibonacci numbers of generalized Zykov sums, J. Integer Seq., 15 (2012), Article 12.7.8.
Index entries for linear recurrences with constant coefficients, signature (2,4,1).

Row 3 of A287376.

LinearRecurrence[{2,4,1},{4,1,13},30] (* Harvey P. Dale, Nov 20 2021 *)

Vec((4-7*x-5*x^2)/((1+x)*(1-3*x-x^2)) + O(x^30)) \\ Colin Barker, May 11 2017

a(n) = 2*a(n-1) + 4*a(n-2) + a(n-3).
G.f.: (4-7*x-5*x^2)/((1+x)*(1-3*x-x^2)). - Colin Barker, May 22 2012
a(n) = 2*(-1)^n + ((3-sqrt(13))/2)^n + ((3+sqrt(13))/2)^n. - Colin Barker, May 11 2017
a(n) = A006497+2*(-1)^n. - R. J. Mathar, Oct 20 2017

A051929 Number of independent sets of vertices in graph K_4 X C_n (n > 2).

Original entry on oeis.org

5, 1, 21, 73, 325, 1361, 5781, 24473, 103685, 439201, 1860501, 7881193, 33385285, 141422321, 599074581, 2537720633, 10749957125, 45537549121, 192900153621, 817138163593, 3461452808005, 14662949395601, 62113250390421, 263115950957273, 1114577054219525

Offset: 0

Stephen G Penrice, Dec 19 1999

Colin Barker, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (3,5,1).

Row 4 of A287376.

Vec((5 - 14*x - 7*x^2) / ((1 + x)*(1 - 4*x - x^2)) + O(x^30)) \\ Colin Barker, May 11 2017

a(n) = 3*a(n-1) + 5*a(n-2) + a(n-3).
From Colin Barker, May 22 2012: (Start)
a(n) = (3*(-1)^n+(2-sqrt(5))^n+(2+sqrt(5))^n).
G.f.: (5 - 14*x - 7*x^2) / ((1 + x)*(1 - 4*x - x^2)).
(End)

More terms from James Sellers, Dec 20 1999

A051930 Number of independent sets of vertices in graph K_5 X C_n (n > 2).

Original entry on oeis.org

6, 1, 31, 136, 731, 3771, 19606, 101781, 528531, 2744416, 14250631, 73997551, 384238406, 1995189561, 10360186231, 53796120696, 279340789731, 1450500069331, 7531841136406, 39109705751341, 203080369893131, 1054511555216976, 5475638145978031, 28432702285107111

Offset: 0

Stephen G Penrice, Dec 19 1999

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (4,6,1).

Row 5 of A287376.

I:=[6, 1, 31]; [n le 3 select I[n] else 4*Self(n-1)+6*Self(n-2)+Self(n-3): n in [1..30]]; // Vincenzo Librandi, Jun 17 2012

LinearRecurrence[{4,6,1},{6,1,31},30] (* Vincenzo Librandi, Jun 17 2012 *)

Vec((6 - 23*x - 9*x^2) / ((1 + x)*(1 - 5*x - x^2)) + O(x^40)) \\ Colin Barker, Nov 24 2017

a(n) = 4*a(n-1) + 6*a(n-2) + a(n-3).
G.f.: (6 - 23*x - 9*x^2) / ((1 + x)*(1 - 5*x - x^2)). - Colin Barker, May 22 2012
From Colin Barker, Nov 24 2017: (Start)
a(n) = ((5-sqrt(29))/2)^n + ((5+sqrt(29))/2)^n + 4 for n even.
a(n) = ((5-sqrt(29))/2)^n + ((5+sqrt(29))/2)^n - 4 for n odd.
(End)

More terms from James Sellers, Dec 20 1999

A051931 Number of independent sets of nodes in graph K_6 X C_n (n > 2).

Original entry on oeis.org

7, 1, 43, 229, 1447, 8881, 54763, 337429, 2079367, 12813601, 78961003, 486579589, 2998438567, 18477210961, 113861704363, 701647437109, 4323746327047, 26644125399361, 164188498723243, 1011775117738789, 6234839205156007, 38420810348674801, 236759701297204843

Offset: 0

Stephen G Penrice, Dec 19 1999

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (5,7,1).

Row 6 of A287376.

I:=[7, 1, 43]; [n le 3 select I[n] else 5*Self(n-1)+7*Self(n-2)+Self(n-3): n in [1..25]]; // Vincenzo Librandi, Apr 27 2012

CoefficientList[Series[(7-34*x-11*x^2)/((1+x)*(1-6*x-x^2)),{x,0,30}],x] (* Vincenzo Librandi, Apr 27 2012 *)

Vec((7 - 34*x - 11*x^2) / ((1 + x)*(1 - 6*x - x^2)) + O(x^40)) \\ Colin Barker, Nov 24 2017

a(n) = 5*a(n-1) + 7*a(n-2) + a(n-3).
G.f.: (7 - 34*x - 11*x^2) / ((1 + x)*(1 - 6*x - x^2)). - Colin Barker, Apr 18 2012
From Colin Barker, Nov 24 2017: (Start)
a(n) = (3 - sqrt(10))^n + (3 + sqrt(10))^n + 5 for n even.
a(n) = (3 - sqrt(10))^n + (3 + sqrt(10))^n - 5 for n odd.
(End)

More terms from James Sellers, Dec 20 1999

A051932 Number of independent sets of nodes in graph K_7 X C_n (n > 2).

Original entry on oeis.org

8, 1, 57, 358, 2605, 18551, 132504, 946037, 6754805, 48229630, 344362257, 2458765387, 17555720008, 125348805401, 894997357857, 6390330310358, 45627309530405, 325781497023151, 2326097788692504, 16608466017870637, 118585359913787005, 846705985414379630

Offset: 0

Stephen G Penrice, Dec 19 1999

Colin Barker, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (6,8,1).

Row 7 of A287376.

LinearRecurrence[{6,8,1},{8,1,57},20] (* Harvey P. Dale, Sep 11 2011 *)

Vec((8 - 47*x - 13*x^2) / ((1 + x)*(1 - 7*x - x^2)) + O(x^30)) \\ Colin Barker, May 11 2017

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

G.f.: (13*x^2+47*x-8)/(x^3+8*x^2+6*x-1). - Harvey P. Dale, Sep 11 2011

More terms from James Sellers, Dec 20 1999

Corrected by T. D. Noe, Nov 07 2006

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

PARI

Sage

Formula

A135597 Square array read by antidiagonals: row m (m >= 1) satisfies b(0) = b(1) = 1; b(n) = m*b(n-1) + b(n-2).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A051928 Number of independent sets of vertices in graph K_3 X C_n (n > 2).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A051929 Number of independent sets of vertices in graph K_4 X C_n (n > 2).

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

Extensions

A051930 Number of independent sets of vertices in graph K_5 X C_n (n > 2).

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

Extensions

A051931 Number of independent sets of nodes in graph K_6 X C_n (n > 2).

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

Extensions

A051932 Number of independent sets of nodes in graph K_7 X C_n (n > 2).

Views

Author

Keywords

Links

Crossrefs

Programs