A300738 Number of minimal total dominating sets in the n-cycle graph.

0, 0, 3, 4, 5, 9, 7, 4, 12, 25, 22, 25, 39, 49, 68, 100, 119, 144, 209, 289, 367, 484, 644, 841, 1130, 1521, 1983, 2601, 3480, 4624, 6107, 8100, 10717, 14161, 18807, 24964, 33004, 43681, 57918, 76729, 101639, 134689, 178364, 236196, 313007, 414736, 549289

Offset: 1

Author

Andrew Howroyd, Apr 15 2018

Keywords

• nonn
• easy

Links

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

Crossrefs

Cf. A001608, A001638 (total dominating sets), A253413, A302653, A302655, A302918.

Programs

Mathematica

Table[RootSum[-1 - # + #^3 &, #^n &] + (1 + (-1)^n) RootSum[-1 + #^2 + #^3 &, #^(n/2) &], {n, 20}]
Perrin[n_] := RootSum[-1 - # + #^3 &, #^n &]; Table[With[{b = Mod[n, 2, 1]}, Perrin[n/b]^b], {n, 20}]
LinearRecurrence[{0, 0, 1, 1, 1, 1, 0, -1, -1}, {0, 0, 3, 4, 5, 9, 7, 4, 12}, 20]
CoefficientList[Series[x^2 (3 + 4 x + 5 x^2 + 6 x^3 - 8 x^5 - 9 x^6)/(1 - x^3 - x^4 - x^5 - x^6 + x^8 + x^9), {x, 0, 20}], x]

PARI

concat([0,0], Vec((3 + 4*x + 5*x^2 + 6*x^3 - 8*x^5 - 9*x^6)/((1 - x^2 - x^3)*(1 + x^2 - x^6)) + O(x^50)))

Formula

a(n) = a(n-3) + a(n-4) + a(n-5) + a(n-6) - a(n-8) - a(n-9) for n > 9.

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

a(2*n) = A001608(n)^2.

a(2*n-1) = A001608(2*n-1), where A001608 are the Perrin numbers.