A303054 Number of minimum total dominating sets in the n-ladder graph.

1, 4, 1, 16, 9, 1, 64, 16, 1, 169, 25, 1, 361, 36, 1, 676, 49, 1, 1156, 64, 1, 1849, 81, 1, 2809, 100, 1, 4096, 121, 1, 5776, 144, 1, 7921, 169, 1, 10609, 196, 1, 13924, 225, 1, 17956, 256, 1, 22801, 289, 1, 28561, 324, 1, 35344, 361, 1, 43264, 400, 1, 52441

Offset

1,2

Comments

Each vertex can dominate up to three others. A ladder with a length that is an exact multiple of three can be dominated in only one way with 2n/3 vertices. - Andrew Howroyd, Apr 21 2018

Links

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

Eric Weisstein's World of Mathematics, Ladder Graph

Eric Weisstein's World of Mathematics, Total Dominating Set

Index entries for linear recurrences with constant coefficients, signature (0,0,5,0,0,-10,0,0,10,0,0,-5,0,0,1).

Formula

a(n) = 1 for n mod 3 = 0

= ((n^2 + 13*n + 4)/18)^2 for n mod 3 = 1

= ((n + 4)/3)^2 for n mod 3 = 2.

G.f.: x*(-1 - 4*x - x^2 - 11*x^3 + 11*x^4 + 4*x^5 + 6*x^6 - 11*x^7 - 6*x^8 + x^9 + 5*x^10 + 4*x^11 - x^12 - x^13 - x^14)/(-1 + x^3)^5.

a(n) = 5*a(n-3) - 10*a(n-6) + 10*a(n-9) - 5*a(n-12) + a(n-15) for n>15. - Colin Barker, Apr 23 2018

Example

From Andrew Howroyd, Apr 21 2018: (Start)
a(9) = 1 because there is only one arrangement of 6 vertices that is totally dominating and no set with fewer vertices can be totally dominating:
  .__o__.__.__o__.__.__o__.
     |        |        |
  .__o__.__.__o__.__.__o__.
(End)

Mathematica

Table[Piecewise[{{1, Mod[n, 3] == 0}, {((n^2 + 13 n + 4)/18)^2, Mod[n, 3] == 1}, {((n + 4)/3)^2, Mod[n, 3] == 2}}], {n, 58}] (* Eric W. Weisstein, Apr 23 2018 and Michael De Vlieger, Apr 21 2018 *)
Table[(916 + 392 n + 213 n^2 + 26 n^3 + n^4 - (-56 + 392 n + 213 n^2 + 26 n^3 + n^4) Cos[2 n Pi/3] + Sqrt[3] (-20 + 7 n + n^2) (28 + 19 n + n^2) Sin[2 n Pi/3])/972, {n, 20}] (* Eric W. Weisstein, Apr 23 2018 *)
LinearRecurrence[{0, 0, 5, 0, 0, -10, 0, 0, 10, 0, 0, -5, 0, 0, 1}, {1, 4, 1, 16, 9, 1, 64, 16, 1, 169, 25, 1, 361, 36, 1}, 20] (* Eric W. Weisstein, Apr 23 2018 *)
CoefficientList[Series[(-1 - 4 x - x^2 - 11 x^3 + 11 x^4 + 4 x^5 + 6 x^6 - 11 x^7 - 6 x^8 + x^9 + 5 x^10 + 4 x^11 - x^12 - x^13 - x^14)/(-1 + x^3)^5, {x, 0, 20}], x] (* Eric W. Weisstein, Apr 23 2018 *)

Prog

(PARI) a(n)={if(n%3==0, 1, if(n%3==1, (n^2 + 13*n + 4)/18, (n + 4)/3))^2} \\ Andrew Howroyd, Apr 21 2018
(PARI) Vec(x*(1 + 4*x + x^2 + 11*x^3 - 11*x^4 - 4*x^5 - 6*x^6 + 11*x^7 + 6*x^8 - x^9 - 5*x^10 - 4*x^11 + x^12 + x^13 + x^14) / ((1 - x)^5*(1 + x + x^2)^5) + O(x^60)) \\ Colin Barker, Apr 23 2018

Crossrefs

Row 2 of A303293.

Sequence in context: A038231 A104855 A351419 * A143496 A143697 A272088

Adjacent sequences: A303051 A303052 A303053 * A303055 A303056 A303057

Keyword

nonn,easy

Author

Eric W. Weisstein, Apr 17 2018

Extensions

Terms a(14) and beyond from Andrew Howroyd, Apr 21 2018

Status

approved