|
|
A303054
|
|
Number of minimum total dominating sets in the n-ladder graph.
|
|
3
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
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
|
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
|
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|