A302653 Number of minimum total dominating sets in the n-cycle graph.

1, 1, 3, 4, 5, 9, 7, 4, 9, 25, 11, 4, 13, 49, 15, 4, 17, 81, 19, 4, 21, 121, 23, 4, 25, 169, 27, 4, 29, 225, 31, 4, 33, 289, 35, 4, 37, 361, 39, 4, 41, 441, 43, 4, 45, 529, 47, 4, 49, 625, 51, 4, 53, 729, 55, 4, 57, 841, 59, 4, 61, 961, 63, 4, 65, 1089, 67, 4, 69, 1225, 71, 4

Offset: 1

Author

Eric W. Weisstein, Apr 11 2018

Keywords

• nonn
• easy

Comments

Extended to a(1)-a(2) using the formula/recurrence.

Links

• Colin Barker, Table of n, a(n) for n = 1..1000
• Eric Weisstein's World of Mathematics, Cycle Graph.
• Eric Weisstein's World of Mathematics, Minimum Total Dominating Set.
• Index entries for linear recurrences with constant coefficients, signature (0,0,0,3,0,0,0,-3,0,0,0,1).

Programs

Mathematica

Table[((-1)^n (n - 4)^2 + (n + 4)^2 - 2 (n - 4) (n + 4) cos(n Pi/2))/16, {n, 80}]
Table[Piecewise[{{n, Mod[n, 2] == 1}, {4, Mod[n, 4] == 0}, {(n/2)^2, Mod[n, 4] == 2}}], {n, 80}]
LinearRecurrence[{0, 0, 0, 3, 0, 0, 0, -3, 0, 0, 0, 1}, {1, 1, 3, 4, 5, 9, 7, 4, 9, 25, 11, 4}, 80]

PARI

Vec(x*(1 + x + 3*x^2 + 4*x^3 + 2*x^4 + 6*x^5 - 2*x^6 - 8*x^7 - 3*x^8 + x^9 - x^10 + 4*x^11) / ((1 - x)^3*(1 + x)^3*(1 + x^2)^3) + O(x^70)) \\ Colin Barker, Dec 25 2019

Formula

a(n) = n for odd n.

a(n) = 4 for n mod 4 = 0.

a(n) = (n/2)^2 for n mod 4 = 2.

a(n) = ((-1)^n*(n - 4)^2 + (n + 4)^2 - 2*(n - 4)*(n + 4)*cos(n*Pi/2))/16.

a(n) = 3*a(n-4) - 3*a(n-8) + a(n-12).

G.f.: x*(1 + x + 3*x^2 + 4*x^3 + 2*x^4 + 6*x^5 - 2*x^6 - 8*x^7 - 3*x^8 + x^9 - x^10 + 4*x^11) / ((1 - x)^3*(1 + x)^3*(1 + x^2)^3). - Colin Barker, Dec 25 2019