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,3

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, Total Dominating Set

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

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.

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]

Prog

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

Crossrefs

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

Sequence in context: A122403 A349659 A302653 * A324506 A342772 A065336

Adjacent sequences: A300735 A300736 A300737 * A300739 A300740 A300741

Keyword

nonn,easy

Author

Andrew Howroyd, Apr 15 2018

Status

approved