A284702 -id:A284702 - cp's OEIS frontend

A284663 Number of dominating sets in the Moebius ladder M_n.

3, 15, 51, 179, 663, 2439, 8935, 32771, 120219, 440975, 1617531, 5933267, 21763823, 79831879, 292831311, 1074134531, 3940032883, 14452434639, 53012975555, 194456895859, 713287340551, 2616409296967, 9597250953527, 35203676264195, 129130605057163

Offset: 1

Eric W. Weisstein, Mar 31 2017

nonn

Sequence extrapolated to n=1 using recurrence. - Andrew Howroyd, May 10 2017

Andrew Howroyd, Table of n, a(n) for n = 1..200
Eric Weisstein's World of Mathematics, Dominating Set
Eric Weisstein's World of Mathematics, Moebius Ladder
Index entries for linear recurrences with constant coefficients, signature (3,1,5,1,1,-1,-1).

Cf. A182143, A284702, A218348 (ladder).

LinearRecurrence[{3, 1, 5, 1, 1, -1, -1}, {3, 15, 51, 179, 663, 2439,
  8935}, 20] (* Eric W. Weisstein, May 17 2017 *)
Rest[CoefficientList[Series[x*(1 - x)*(1 + x)*(3*x^4 + 2*x^3 + 6*x^2 + 6*x + 3)/((x^2 + 1)*(x^5 + x^4 - 2*x^3 - 2*x^2 - 3*x + 1)), {x,0,50}], x]] (* G. C. Greubel, May 17 2017 *)
Table[RootSum[1 + # - 2 #^2 - 2 #^3 - 3 #^4 + #^5 &, #^n &] - 2 Cos[n Pi/2], {n, 20}] (* Eric W. Weisstein, Jun 14 2017 *)

Vec((1-x)*(1+x)*(3*x^4+2*x^3+6*x^2+6*x+3)/((x^2+1)*(x^5+x^4-2*x^3-2*x^2-3*x+1))+O(x^50)) \\ Andrew Howroyd, May 10 2017

From Andrew Howroyd, May 10 2017 (Start)
a(n) = 3*a(n-1)+a(n-2)+5*a(n-3)+a(n-4)+a(n-5)-a(n-6)-a(n-7) for n>7.
G.f.: x*(1-x)*(1+x)*(3*x^4+2*x^3+6*x^2+6*x+3)/((x^2+1)*(x^5+x^4-2*x^3 -2*x^2-3*x+1)). (End)

a(1)-(2) and a(16)-a(25) from Andrew Howroyd, May 10 2017

A290336 Number of minimal dominating sets in the n-prism graph.

Original entry on oeis.org

11, 12, 37, 55, 149, 316, 596, 1219, 2444, 4971, 10103, 20465, 41746, 84924, 172501, 350668, 712597, 1448447, 2943959, 5983344, 12162310, 24720787, 50246512, 102129655, 207584129, 421928981, 857596064, 1743117100, 3543000201, 7201373724, 14637255611

Offset: 3

Eric W. Weisstein, Jul 27 2017

nonn

The prism graphs are defined for n>=3. If the sequence is extended to n=1 using P_n X P_2 then a(1)=2 and a(2)=6 (as A290379). The empirical recurrence is the same as that for the Moebius ladder graph (see A290337). - Andrew Howroyd, Aug 01 2017

Andrew Howroyd, Table of n, a(n) for n = 3..200
Eric Weisstein's World of Mathematics, Minimal Dominating Set
Eric Weisstein's World of Mathematics, Prism Graph

Cf. A284702, A290337, A290379.

Empirical: a(n) = a(n-1)+a(n-2)+2*a(n-3) -a(n-4)+2*a(n-5)-2*a(n-6) +6*a(n-7)+4*a(n-8)+4*a(n-9) -6*a(n-10)-3*a(n-12) +5*a(n-13)-a(n-14)-2*a(n-15) -5*a(n-16)-2*a(n-17)-2*a(n-18) for n > 20. - Andrew Howroyd, Aug 01 2017

Empirical g.f.: x^3*(11 + x + 14*x^2 - 16*x^3 + 44*x^4 + 28*x^5 + 56*x^6 - 52*x^7 - 6*x^8 - 70*x^9 + 52*x^10 - 28*x^11 - 23*x^12 - 97*x^13 - 56*x^14 - 62*x^15 - 12*x^16 - 8*x^17) / ((1 - x)*(1 + 2*x^4 + x^6)*(1 - x^2 - 3*x^3 - 4*x^4 - 4*x^5 - x^6 - 2*x^7 - 3*x^8 - 5*x^9 - 4*x^10 - 2*x^11)). - Colin Barker, Aug 02 2017

Terms a(9) and beyond from Andrew Howroyd, Aug 01 2017

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

A218348 Hilltop maps: number of n X 2 binary arrays indicating the locations of corresponding elements not exceeded by any horizontal or vertical neighbor in a random 0..1 nX2 array.

Original entry on oeis.org

3, 11, 41, 149, 547, 2007, 7361, 27001, 99043, 363299, 1332617, 4888173, 17930307, 65770159, 241251521, 884934705, 3246028995, 11906758971, 43675182633, 160204937605, 587647732323, 2155550649479, 7906775346689, 29002842683433

Offset: 1

R. H. Hardin, Oct 26 2012

Number of dominating sets in the ladder graph P_2 X P_n. - Andrew Howroyd, May 10 2017

			Some solutions for n=3
..1..0....1..1....0..1....1..0....1..1....1..1....0..1....0..0....1..0....0..1
..1..0....0..0....1..1....1..0....0..1....1..1....0..1....1..1....0..0....0..0
..0..1....1..1....0..1....1..0....1..0....1..0....1..0....0..0....0..1....1..0

R. H. Hardin, Table of n, a(n) for n = 1..210
Eric Weisstein's World of Mathematics, Dominating Set
Eric Weisstein's World of Mathematics, Ladder Graph
Index entries for linear recurrences with constant coefficients, signature (3,2,2,-1,-1).

Column 2 of A218354.

Cf. A284663, A284702.

LinearRecurrence[{3, 2, 2, -1, -1}, {3, 11, 41, 149, 547}, 20]  (* Eric W. Weisstein, Jun 14 2017 *)
CoefficientList[Series[(x (3 + 2 x + 2 x^2 - 2 x^3 - x^4))/(1 - 3 x - 2 x^2 - 2 x^3 + x^4 + x^5), {x, 0, 20}], x] (* Eric W. Weisstein, Jun 14 2017 *)
Table[RootSum[1 + # - 2 #^2 - 2 #^3 - 3 #^4 + #^5 &, (-167 + 525 # - 73 #^2 + 819 #^3 - 218 #^4) #^n &]/2102, {n, 20}] (* Eric W. Weisstein, Jul 13 2017 *)

Vec((3+2*x+2*x^2-2*x^3-x^4)/(1-3*x-2*x^2-2*x^3+x^4+x^5)+O(x^50)) \\ Andrew Howroyd, May 10 2017

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

G.f.: x*(3 + 2*x + 2*x^2 - 2*x^3 - x^4)/(1 - 3*x - 2*x^2 - 2*x^3 + x^4 + x^5). - Andrew Howroyd, May 10 2017

A286914 Number of dominating sets in the stacked prism graph C_n X P_n.

Original entry on oeis.org

1, 11, 383, 38437, 15179657, 23213149395, 135207176568283, 3008600384479080345, 255856229024918222966821, 83138455533359719800266401039, 103225590675437292878209927396154515, 489730115155632619934278544711183719808829

Offset: 1

Andrew Howroyd, May 15 2017

nonn

Stephan Mertens, Table of n, a(n) for n = 1..26
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
Wikipedia, Dominating set

Main diagonal of A286514.

Cf. A284702, A285880.

A296102 Number of total dominating sets in the n-prism graph.

Original entry on oeis.org

3, 9, 39, 121, 443, 1521, 5071, 17161, 58035, 196249, 664183, 2247001, 7601259, 25715041, 86992799, 294294025, 995591267, 3368061225, 11394069191, 38545861561, 130399710235, 441139057489, 1492362749807, 5048627017225, 17079382868243, 57779138385081, 195465425009943

Offset: 1

Eric W. Weisstein, Apr 16 2018

Sequence extrapolated to n=1 using recurrence. - Andrew Howroyd, Apr 16 2018

Andrew Howroyd, Table of n, a(n) for n = 1..200
Eric Weisstein's World of Mathematics, Prism Graph
Eric Weisstein's World of Mathematics, Total Dominating Set
Index entries for linear recurrences with constant coefficients, signature (3, 0, 4, -2, 10, 4, 0, -1, -1).

Cf. A284702, A290336, A295420.

Table[RootSum[-1 - # - 3 #^2 + #^3 &, #^n &] + RootSum[1 + # - #^2 + #^3 &, #^n &] + RootSum[-1 + # + #^2 + #^3 &, #^n &], {n, 20}]
LinearRecurrence[{3, 0, 4, -2, 10, 4, 0, -1, -1}, {3, 9, 39, 121, 443,
   1521, 5071, 17161, 58035}, 20]
CoefficientList[Series[(3 + 12 x^2 - 8 x^3 + 50 x^4 + 24 x^5 - 8 x^7 - 9 x^8)/(1 - 3 x - 4 x^3 + 2 x^4 - 10 x^5 - 4 x^6 + x^8 + x^9), {x, 0, 20}], x]

Vec((3 + 12*x^2 - 8*x^3 + 50*x^4 + 24*x^5 - 8*x^7 - 9*x^8)/((1 - x + x^2 + x^3)*(1 + x + x^2 - x^3)*(1 - 3*x - x^2 - x^3)) + O(x^30)) \\ Andrew Howroyd, Apr 16 2018

From Andrew Howroyd, Apr 16 2018: (Start)
G.f.: x*(3 + 12*x^2 - 8*x^3 + 50*x^4 + 24*x^5 - 8*x^7 - 9*x^8)/((1 - x + x^2 + x^3)*(1 + x + x^2 - x^3)*(1 - 3*x - x^2 - x^3)).
a(n) = 3*a(n-1) + 4*a(n-3) - 2*a(n-4) + 10*a(n-5) + 4*a(n-6) - a(n-8) - a(n-9) for n > 9. (End)

a(1)-a(2) and terms a(10) and beyond from Andrew Howroyd, Apr 16 2018

A338153 a(n) is the number of acyclic orientations of the edges of the n-prism.

Original entry on oeis.org

204, 1862, 14700, 109334, 790524, 5633222, 39828300, 280376054, 1968934044, 13807724582, 96754776300, 677686169174, 4745413960764, 33224340503942, 232596153986700, 1628276158432694, 11398345428510684, 79790067272259302, 558537067986067500, 3909785864202510614

Offset: 3

Peter Kagey, Oct 13 2020

nonn

Conjectured linear recurrence and g.f. confirmed by Kagey's formula. - Ray Chandler, Mar 10 2024

			For n = 4, the 4-prism is the 3-dimensional cube, so a(4) = A334247(3) = 1862.

Peter Kagey, Table of n, a(n) for n = 3..1000
Eric Weisstein's World of Mathematics, Prism Graph
Wikipedia, Acyclic orientation
Index entries for linear recurrences with constant coefficients, signature (14, -63, 106, -56).

Cf. A102080, A124349, A284702.

Cf. A033815 (cross-polytope), A058809 (wheel), A334247 (cube), A338152 (n-demihypercube), A338154 (n-antiprism).

A338153[n_] := 5 + 7^n - 2^(n + 1) - 2*4^n (* Peter Kagey, Nov 15 2020 *)

Conjectures from Colin Barker, Oct 13 2020: (Start)
G.f.: 2*x^3*(102 - 497*x + 742*x^2 - 392*x^3) / ((1 - x)*(1 - 2*x)*(1 - 4*x)*(1 - 7*x)).
a(n) = 14*a(n-1) - 63*a(n-2) + 106*a(n-3) - 56*a(n-4) for n>6.
(End)
a(n) = 5 + 7^n - 2^(n+1) - 2*4^n. - Peter Kagey, Nov 15 2020

A285880 Number of dominating sets in the stacked prism graph C_3 X P_n.

Original entry on oeis.org

7, 51, 383, 2865, 21449, 160579, 1202181, 9000177, 67380199, 504444655, 3776545835, 28273267057, 211668986689, 1584668649559, 11863687582089, 88817989227329, 664939560807015, 4978097605819019, 37268734233506311, 279013924866426465

Offset: 1

Andrew Howroyd, May 15 2017

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..200
Eric Weisstein's World of Mathematics, Dominating Set
Wikipedia, Dominating set

Row 3 of A286514.

Cf. A284702, A286914.

Empirical: a(n) = 7*a(n-1)+3*a(n-2)+5*a(n-3)-a(n-4)-3*a(n-5)-a(n-6)-a(n-7) for n>7.

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

A286985 Number of connected dominating sets in the n-prism graph.

Original entry on oeis.org

7, 7, 39, 115, 343, 967, 2663, 7203, 19239, 50887, 133543, 348179, 902775, 2329607, 5986535, 15327555, 39115847, 99532423, 252601127, 639548595, 1615746455, 4073951559, 10253517671, 25763632995, 64635943783, 161928486727, 405134009511, 1012371656275

Offset: 1

Eric W. Weisstein, May 17 2017

nonn

Sequence extrapolated to a(1) and a(2) using recurrence. - Andrew Howroyd, Sep 04 2017

Andrew Howroyd, Table of n, a(n) for n = 1..200
Eric Weisstein's World of Mathematics, Connected Dominating Set
Eric Weisstein's World of Mathematics, Prism Graph
Index entries for linear recurrences with constant coefficients, signature (6, -11, 4, 5, -2, -1).

Cf. A284702, A286182.

Rest @ CoefficientList[Series[x (7 - 35 x + 74 x^2 - 70 x^3 + 19 x^4 - 3 x^5)/((1 - x)^2*(1 - 2 x - x^2)^2), {x, 0, 28}], x] (* Michael De Vlieger, Sep 04 2017 *)
Table[LucasL[n, 2] + 2 n (3 Fibonacci[n - 2, 2] + Fibonacci[n - 1, 2] - 1) + 1, {n, 20}] (* Eric W. Weisstein, Sep 08 2017 *)
LinearRecurrence[{6, -11, 4, 5, -2, -1}, {7, 7, 39, 115, 343, 967}, 20] (* Eric W. Weisstein, Sep 08 2017 *)

Vec((7 - 35*x + 74*x^2 - 70*x^3 + 19*x^4 - 3*x^5)/((1 - x)^2*(1 - 2*x - x^2)^2) + O(x^30))

From Andrew Howroyd, Sep 04 2017: (Start)
a(n) = 6*a(n-1) - 11*a(n-2) + 4*a(n-3) + 5*a(n-4) - 2*a(n-5) - a(n-6) for n > 6.
G.f.: x*(7 - 35*x + 74*x^2 - 70*x^3 + 19*x^4 - 3*x^5)/((1 - x)^2*(1 - 2*x - x^2)^2).
(End)

a(1)-a(2) and terms a(14) and beyond from Andrew Howroyd, Sep 04 2017

A290511 Number of irredundant sets in the n-prism graph.

Original entry on oeis.org

3, 9, 24, 77, 198, 522, 1550, 4477, 12732, 36214, 103579, 296294, 846303, 2417368, 6907329, 19737901, 56396602, 161138214, 460420182, 1315565162, 3758963099, 10740463083, 30688703123, 87686813998, 250547405698, 715888629491, 2045507376543, 5844625043236

Offset: 1

Eric W. Weisstein, Aug 04 2017

nonn

The n-prism graph is well defined for n >= 3. Sequence extended to n=1 via the number of period n periodic solutions on a larger graph. - Andrew Howroyd, Aug 07 2017

Andrew Howroyd, Table of n, a(n) for n = 1..200
Eric Weisstein's World of Mathematics, Irredundant Set
Eric Weisstein's World of Mathematics, Prism Graph

Cf. A284702, A290336, A290493.

Empirical: a(n) = 3*a(n-1) - a(n-3) + 2*a(n-4) - 6*a(n-5) - 8*a(n-6) + 13*a(n-7) + 6*a(n-8) - 6*a(n-9) - 2*a(n-10) - 5*a(n-11) - 4*a(n-12) + 2*a(n-13) + 2*a(n-14) - a(n-15) + a(n-16) + 3*a(n-17) + 2*a(n-19) for n > 19. - Andrew Howroyd, Aug 07 2017

a(1)-a(2) and terms a(10) and beyond from Andrew Howroyd, Aug 07 2017

cp's OEIS Frontend

A284663 Number of dominating sets in the Moebius ladder M_n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A290336 Number of minimal dominating sets in the n-prism graph.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

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

A218348 Hilltop maps: number of n X 2 binary arrays indicating the locations of corresponding elements not exceeded by any horizontal or vertical neighbor in a random 0..1 nX2 array.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A286914 Number of dominating sets in the stacked prism graph C_n X P_n.

Views

Author

Keywords

Links

Crossrefs

A296102 Number of total dominating sets in the n-prism graph.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A338153 a(n) is the number of acyclic orientations of the edges of the n-prism.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A285880 Number of dominating sets in the stacked prism graph C_3 X P_n.

Views

Author

Keywords

Links

Crossrefs

Formula

A286985 Number of connected dominating sets in the n-prism graph.

Views

Author