A286513 -id:A286513 - 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

A286514 Array read by antidiagonals: T(m,n) = number of dominating sets in the stacked prism graph C_m X P_n.

Original entry on oeis.org

1, 3, 3, 5, 11, 7, 9, 41, 51, 11, 17, 149, 383, 183, 21, 31, 547, 2865, 2629, 663, 39, 57, 2007, 21449, 38437, 18635, 2435, 71, 105, 7361, 160579, 561743, 531669, 133709, 8935, 131, 193, 27001, 1202181, 8207075, 15179657, 7455797, 956009, 32775, 241

Offset: 1

Andrew Howroyd, May 10 2017

			Table starts:
===========================================================
m\n|  1    2      3         4           5             6
---|-------------------------------------------------------
1  |  1    3      5         9          17            31 ...
2  |  3   11     41       149         547          2007 ...
3  |  7   51    383      2865       21449        160579 ...
4  | 11  183   2629     38437      561743       8207075 ...
5  | 21  663  18635    531669    15179657     433200191 ...
6  | 39 2435 133709   7455797   416118655   23213149395 ...
7  | 71 8935 956009 104209625 11369806353 1239821606103 ...
...

Stephan Mertens, Table of n, a(n) for n = 1..325 (first 91 terms from Andrew Howroyd)
Stephan Mertens, Domination Polynomials of the Grid, the Cylinder, the Torus, and the King Graph, arXiv:2408.08053 [math.CO], Aug 2024.
Eric Weisstein's World of Mathematics, Dominating Set
Eric Weisstein's World of Mathematics, Stacked Prism Graph
Wikipedia, Dominating set

Column 2 is A284702.
Row 3 is A285880.
Main diagonal is A286914.
Cf. A286513, A218354 (P_n X P_n).

A212270 Number of ways to place k non-attacking wazirs on an n x n cylindrical chessboard, summed over all k >= 0.

Original entry on oeis.org

2, 7, 43, 933, 36211, 3557711, 746156517, 363549830913, 394677987525997, 974602314570939359, 5418730454986467701985, 68176187476467835406646029, 1936241516342334422813929891295, 124281423643836238320564876791634465, 18018270577720149773239661332878801006033

Offset: 1

Vaclav Kotesovec, May 12 2012

Wazir is a leaper [0,1].

Vaclav Kotesovec, Table of n, a(n) for n = 1..32
V. Kotesovec, Non-attacking chess pieces, 6ed, 2013, p.414

Main diagonal of A286513.

Cf. A006506, A027683, A182407, A212269, A212271.

Limit n ->infinity (a(n))^(1/n^2) is the hard square entropy constant A085850.

A050400 Number of independent sets of vertices in P_3 X C_n (n > 2).

Original entry on oeis.org

5, 1, 17, 43, 181, 621, 2309, 8303, 30277, 109753, 398857, 1447931, 5258725, 19095285, 69344061, 251811903, 914429445, 3320635025, 12058502657, 43789003563, 159014593621, 577442573597, 2096914206261, 7614694850543, 27651860345029, 100414447219721, 364643142303353

Offset: 0

Stephen G Penrice, Dec 21 1999

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

Column 3 of A286513.

a:=[5,1,17,43,181];; for n in [6..30] do a[n]:=a[n-1]+8*a[n-2] +6*a[n-3] -a[n-4]-a[n-5]; od; a; # G. C. Greubel, Oct 30 2019

I:=[5,1,17,43,181]; [n le 5 select I[n] else Self(n-1) + 8*Self(n-2) + 6*Self(n-3) - Self(n-4) - Self(n-5): n in [1..30]]; // Vincenzo Librandi, May 11 2017

seq(coeff(series((5-4*x-24*x^2-12*x^3+x^4)/((1+x)*(1-2*x-6*x^2+x^4)), x, n+1), x, n), n = 0..30); # G. C. Greubel, Oct 30 2019

CoefficientList[Series[(5-4*x-24*x^2-12*x^3+x^4)/((1+x)*(1-2*x-6*x^2+ x^4)), {x, 0, 30}], x] (* Vincenzo Librandi, May 11 2017 *)

my(x='x+O('x^30)); Vec((5-4*x-24*x^2-12*x^3+x^4)/((1+x)*(1-2*x-6*x^2+x^4))) \\ G. C. Greubel, Oct 30 2019

def A077952_list(prec):
    P. = PowerSeriesRing(ZZ, prec)
    return P((5-4*x-24*x^2-12*x^3+x^4)/((1+x)*(1-2*x-6*x^2+x^4))).list()
A077952_list(30) # G. C. Greubel, Oct 30 2019

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

G.f.: (5-4*x-24*x^2-12*x^3+x^4)/((1+x)*(1-2*x-6*x^2+x^4)). - Maksym Voznyy (voznyy(AT)mail.ru), Aug 12 2009

More terms from Michael Lugo (mlugo(AT)thelabelguy.com), Dec 22 1999

A050401 Number of independent sets of nodes in P_4 X C_n (n > 2).

Original entry on oeis.org

8, 1, 41, 142, 933, 4741, 26660, 143697, 788453, 4293286, 23454801, 127953981, 698467368, 3811712633, 20803963753, 113540081302, 619672701957, 3381980484909, 18457878595412, 100737602247769, 549796303339413

Offset: 0

Stephen G Penrice, Dec 21 1999

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (1,20,27,-14,-25,4,5,-1).

Column 4 of A286513.

a:=[8,1,41,142,933,4741,26660,143697];; for n in [9..30] do a[n]:= a[n-1]+20*a[n-2]+27*a[n-3]-14*a[n-4]-25*a[n-5]+4*a[n-6]+5*a[n-7]-a[n-8]; od; a; # G. C. Greubel, Oct 30 2019

I:=[8,1,41,142,933,4741,26660,143697]; [n le 8 select I[n] else Self(n-1)+20*Self(n-2)+27*Self(n-3)-14*Self(n-4)- 25*Self(n-5)+4*Self(n-6)+5*Self(n-7)-Self(n-8): n in [1..30]]; // Vincenzo Librandi, May 11 2017

R:=PowerSeriesRing(Integers(), 30); Coefficients(R!( (8 -7*x -120*x^2 -135*x^3 +56*x^4 +75*x^5 -8*x^6 -5*x^7)/((1+x)*(1+2*x-x^2)*( 1-4*x-9*x^2+5*x^3+4*x^4-x^5)) )); // G. C. Greubel, Oct 30 2019

seq(coeff(series((8 -7*x -120*x^2 -135*x^3 +56*x^4 +75*x^5 -8*x^6 -5*x^7)/( (1+x)*(1+2*x-x^2)*(1-4*x-9*x^2+5*x^3+4*x^4-x^5)), x, n+1), x, n), n = 0 ..30); # G. C. Greubel, Oct 30 2019

CoefficientList[Series[(8-7*x-120*x^2-135*x^3+56*x^4+75*x^5-8*x^6-5*x^7) /( (1+x)*(1+2*x-x^2)*(1-4*x-9*x^2+5*x^3+4*x^4-x^5)), {x, 0, 50}], x] (* Vincenzo Librandi, May 11 2017 *)

my(x='x+O('x^30)); Vec((8 -7*x -120*x^2 -135*x^3 +56*x^4 +75*x^5 -8*x^6 -5*x^7)/((1+x)*(1+2*x-x^2)*(1-4*x-9*x^2+5*x^3+4*x^4-x^5))) \\ G. C. Greubel, Oct 30 2019

def A050401_list(prec):
    P. = PowerSeriesRing(ZZ, prec)
    return P((8 -7*x -120*x^2 -135*x^3 +56*x^4 +75*x^5 -8*x^6 -5*x^7)/((1+x)*(1+2*x-x^2)*(1-4*x-9*x^2+5*x^3+4*x^4-x^5))).list()
A050401_list(30) # G. C. Greubel, Oct 30 2019

a(n) = a(n-1) + 20*a(n-2) + 27*a(n-3) - 14*a(n-4) - 25*a(n-5) + 4*a(n-6) + 5*a(n-7) - a(n-8).

G.f.: (8 -7*x -120*x^2 -135*x^3 +56*x^4 +75*x^5 -8*x^6 -5*x^7)/((1+x)*(1+2*x-x^2)*(1-4*x-9*x^2+5*x^3+4*x^4-x^5)). - Colin Barker, Aug 31 2012

More terms from Michael Lugo (mlugo(AT)thelabelguy.com), Dec 22 1999

A051926 Number of independent sets of nodes in graph C_4 X P_n (n>2).

Original entry on oeis.org

1, 7, 35, 181, 933, 4811, 24807, 127913, 659561, 3400911, 17536203, 90422365, 466247117, 2404121747, 12396433487, 63920042065, 329592522065, 1699486218903, 8763103574515, 45185411569413, 232990675202677, 1201375684008283, 6194683683674679, 31941803427179001

Offset: 0

Stephen G Penrice, Dec 19 1999

Number of ways zero or more black and white stones can be placed on the points of a 2 X n grid such that no white stones are adjacent to any black stones. A078057 is a related case, where the grid is 1 X n. - Wayne VanWeerthuizen, May 04 2004

Vincenzo Librandi, 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.
Sela Fried and Toufik Mansour, Staircase graph words, arXiv:2312.08273 [math.CO], 2023.
Index entries for linear recurrences with constant coefficients, signature (5,1,-1).

Row 4 of A286513.

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

CoefficientList[Series[(1+2*x-x^2)/(1-5*x-x^2+x^3),{x,0,30}],x] (* Vincenzo Librandi, Apr 27 2012 *)
LinearRecurrence[{5,1,-1},{1,7,35},40] (* Harvey P. Dale, Apr 29 2019 *)

a(n) = 5*a(n-1)+a(n-2)-a(n-3) for n>2. - Wayne VanWeerthuizen, May 04 2004

G.f.: (1+2*x-x^2)/(1-5*x-x^2+x^3). - Colin Barker, Apr 18 2012

More terms from James Sellers, Dec 20 1999

A181961 Number of independent sets of nodes in graph C_6 x P_n (n>=0).

Original entry on oeis.org

1, 18, 199, 2309, 26660, 307983, 3557711, 41097664, 474748249, 5484153915, 63351353194, 731816432741, 8453730886601, 97655043951558, 1128082705387895, 13031283779122753, 150533605489179940, 1738920490541077131, 20087504465180492695, 232045017488460324836

Offset: 0

Cesar Bautista, Apr 04 2012

Cesar Bautista, Table of n, a(n) for n = 0..219
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 (12,-3,-25,-2,1).

Row 6 of A286513.

Vec((1+6*x-14*x^2+x^4)/(1-12*x+3*x^2+25*x^3+2*x^4-x^5)+O(x^99)) \\ Charles R Greathouse IV, Apr 04 2012

a(n) = 12*a(n-1)-3*a(n-2)-25*a(n-3)-2*a(n-4)+a(n-5) for n>=5, with a(0)=1, a(1)=18, a(2)=199, a(3)=2309, a(4)=26660.

G.f.: (1 + 6*x - 14*x^2 + x^4)/(1 - 12*x + 3*x^2 + 25*x^3 + 2*x^4 - x^5). - Charles R Greathouse IV, Apr 04 2012

A181989 Number of independent sets of nodes in graph C_5 x P_n (n >= 0).

Original entry on oeis.org

1, 11, 81, 621, 4741, 36211, 276561, 2112241, 16132281, 123210611, 941023441, 7187084861, 54891500621, 419234905211, 3201914754721, 24454686308481, 186773143027761, 1426483517982011, 10894795654704401, 83209214029813101, 635511992964231701, 4853735225243983011

Offset: 0

Cesar Bautista, Apr 04 2012

Cesar Bautista, Table of n, a(n) for n = 0..299
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 (7,5,-1).

Row 5 of A286513.

a(n) = 7*a(n-1) + 5*a(n-2) - a(n-3) with a(0)=1, a(1)=11, a(2)=81.

G.f.: (1+4*x-x^2)/(x^3-5*x^2-7*x+1).

A182014 Number of independent sets of nodes in graph C_7 x P_n (n>=0).

Original entry on oeis.org

1, 29, 477, 8303, 143697, 2488431, 43089985, 746156517, 12920616493, 223736359029, 3874270087045, 67087749098875, 1161706844818941, 20116382073294655, 348339884131004417, 6031933298656980345, 104450339960964929961, 1808686034441106749965

Offset: 0

Cesar Bautista, Apr 06 2012

Cesar Bautista, Table of n, a(n) for n = 0..399
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 (17,8,-44,5,1).

Row 7 of A286513.

LinearRecurrence[{17,8,-44,5,1},{1,29,477,8303,143697},30] (* Harvey P. Dale, Aug 27 2012 *)

Vec((x^4+6*x^3-24*x^2+12*x+1)/(-x^5-5*x^4+44*x^3-8*x^2-17*x+1)+O(x^99)) \\ Charles R Greathouse IV, Apr 06 2012

a(n) = 17*a(n-1) + 8*a(n-2) - 44*a(n-3) + 5*a(n-4) + a(n-5) with a(0)=1, a(1)=29, a(2)=477, a(3)=8303, a(4)=143697.

G.f.: (x^4+6*x^3-24*x^2+12*x+1)/(-x^5-5*x^4+44*x^3-8*x^2-17*x+1).

A182019 Number of independent sets of nodes in graph C_8 x P_n (n>=0).

Original entry on oeis.org

1, 47, 1155, 30277, 788453, 20546803, 535404487, 13951571713, 363549830913, 9473376491295, 246857112567171, 6432599206076589, 167620580643483109, 4367854759124964451, 113817498564834289095, 2965854794621630365713, 77284202988962060229833

Offset: 0

Cesar Bautista, Apr 06 2012

Cesar Bautista, Table of n, a(n) for n = 0..499
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 (29,-65,-317,334,187,-109,5,1).

Row 8 of A286513.

a(n) = 29*a(n-1)-65*a(n-2)-317*a(n-3)+334*a(n-4)+187*a(n-5)-109*a(n-6)+5*a(n-7)+a(n-8) with a(0)=1, a(1)=47,a(2)=1155,a(3)=30277,a(4)=788453, a(5)=20546803, a(6)=535404487, a(7)=13951571713.

G.f.: -(x^7 +4*x^6 -79*x^5 +60*x^4 +154*x^3 -143*x^2 +18*x +1)/(x^8 +5*x^7 -109*x^6 +187*x^5 +334*x^4 -317*x^3 -65*x^2 +29*x -1). [Colin Barker, Aug 31 2012]

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

A286514 Array read by antidiagonals: T(m,n) = number of dominating sets in the stacked prism graph C_m X P_n.

Views

Author

Keywords

Examples

Links

Crossrefs

A212270 Number of ways to place k non-attacking wazirs on an n x n cylindrical chessboard, summed over all k >= 0.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A050400 Number of independent sets of vertices in P_3 X C_n (n > 2).

Views

Author

Keywords

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

Sage

Formula

Extensions

A050401 Number of independent sets of nodes in P_4 X C_n (n > 2).

Views

Author

Keywords

Links

Crossrefs

Programs

GAP

Magma

Magma

Maple

Mathematica

PARI

Sage

Formula

Extensions

A051926 Number of independent sets of nodes in graph C_4 X P_n (n>2).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

Formula

Extensions

A181961 Number of independent sets of nodes in graph C_6 x P_n (n>=0).

Views

Author

Keywords

Links

Crossrefs