A347633 Number of minimum dominating sets in the path graph P_n.

1, 2, 1, 4, 3, 1, 8, 4, 1, 13, 5, 1, 19, 6, 1, 26, 7, 1, 34, 8, 1, 43, 9, 1, 53, 10, 1, 64, 11, 1, 76, 12, 1, 89, 13, 1, 103, 14, 1, 118, 15, 1, 134, 16, 1, 151, 17, 1, 169, 18, 1, 188, 19, 1, 208, 20, 1, 229, 21, 1, 251, 22, 1, 274, 23, 1, 298, 24, 1, 323

Offset: 1

Author

Eric W. Weisstein, Sep 09 2021

Keywords

• nonn

Links

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

Crossrefs

Row 1 of A350815 and A350820.

Cf. A347538, A347558, A350816.

Programs

Mathematica

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

PARI

a(n)={if(n%3==0, 1, if(n%3==1, (n^2+13*n+4)/18,  (n+4)/3))} \\ Andrew Howroyd, Jan 18 2022

Formula

a(n) = 1 for n = 0 (mod 3)

(n^2+13*n+4)/18 for n = 1 (mod 3)

(n+4)/3 for n = 2 (mod 3).

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

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