A347553 Number of minimum dominating sets in the n-cycle complement graph.

1, 4, 5, 9, 14, 20, 27, 35, 44, 54, 65, 77, 90, 104, 119, 135, 152, 170, 189, 209, 230, 252, 275, 299, 324, 350, 377, 405, 434, 464, 495, 527, 560, 594, 629, 665, 702, 740, 779, 819, 860, 902, 945, 989, 1034, 1080, 1127, 1175, 1224, 1274, 1325, 1377, 1430

Offset: 3

Author

Eric W. Weisstein, Sep 06 2021

Keywords

• nonn
• easy

Links

• John Konvalina, On the number of combinations without unit separation, Journal of Combinatorial Theory, Series A 31.2 (1981): 101-107. See Table II, row k=2.
• Eric Weisstein's World of Mathematics, Cycle Complement Graph
• Eric Weisstein's World of Mathematics, Minimum Dominating Set
• Index entries for linear recurrences with constant coefficients, signature (3,-3,1).

Crossrefs

Essentially the same as A000096.

Programs

Mathematica

Join[{1, 4}, Table[n(n-3)/2, {n, 5, 20}]]
CoefficientList[Series[x^3(-1 - x + 4 x^2 - 5 x^3 + 2 x^4)/(-1 + x)^3, {x, 0, 20}], x]

Formula

a(n) = n*(n - 3)/2 for n > 4.

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

From Stefano Spezia, Sep 08 2021: (Start)

E.g.f.: x*(12 + 6*exp(x)*(x - 2) + 6*x + 2*x^2 + x^3)/12.

a(n) = 3*a(n-1) - 3*a(n-3) + a(n-3) for n > 4. (End)