A347538 Number of minimum dominating sets in the cycle graph C_n.

3, 6, 5, 3, 14, 8, 3, 25, 11, 3, 39, 14, 3, 56, 17, 3, 76, 20, 3, 99, 23, 3, 125, 26, 3, 154, 29, 3, 186, 32, 3, 221, 35, 3, 259, 38, 3, 300, 41, 3, 344, 44, 3, 391, 47, 3, 441, 50, 3, 494, 53, 3, 550, 56, 3, 609, 59, 3, 671, 62, 3, 736, 65, 3, 804, 68, 3

Offset: 3

Author

Eric W. Weisstein, Sep 05 2021

Keywords

• nonn
• easy

Links

• Eric Weisstein's World of Mathematics, Cycle Graph
• Eric Weisstein's World of Mathematics, Minimum Dominating Set
• Index entries for linear recurrences with constant coefficients, signature (0, 0, 3, 0, 0, -3, 0, 0, 1).

Programs

Mathematica

Table[Piecewise[{{3, Mod[n, 3] == 0}, {n (n + 5)/6, Mod[n, 3] == 1}, {n, Mod[n, 3] == 2}}], {n, 3, 20}]
CoefficientList[Series[-(3 + 6 x + 5 x^2 - 6 x^3 - 4 x^4 - 7 x^5 + 3 x^6 + x^7 + 2 x^8)/((-1 + x)^3 (1 + x + x^2)^3), {x, 0, 20}], x]
LinearRecurrence[{0, 0, 3, 0, 0, -3, 0, 0, 1}, {3, 6, 5, 3, 14, 8, 3, 25, 11}, 20]

Formula

a(n) = 3 if n == 0 (mod 3),

n*(n+5)/6 if n == 1 (mod 3),

n if n == 2 (mod 3).

a(n) = 3*a(n-3) - 3*a(n-6) + a(n-9).

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