A397750 Number of minimum independent dominating sets in the n-path graph.

1, 1, 2, 1, 3, 3, 1, 6, 4, 1, 10, 5, 1, 15, 6, 1, 21, 7, 1, 28, 8, 1, 36, 9, 1, 45, 10, 1, 55, 11, 1, 66, 12, 1, 78, 13, 1, 91, 14, 1, 105, 15, 1, 120, 16, 1, 136, 17, 1, 153, 18, 1, 171, 19, 1, 190, 20, 1, 210, 21, 1, 231, 22, 1, 253, 23, 1, 276, 24, 1, 300, 25, 1, 325, 26, 1

Offset

0,3

Links

Andrew Howroyd, Table of n, a(n) for n = 0..10000

Eric Weisstein's World of Mathematics, Path Graph.

Eric Weisstein's World of Mathematics, Independent Dominating Set.

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

Formula

a(3*n) = 1; a(3*n + 1) = binomial(n + 2, 2); a(3*n + 2) = n + 2.

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

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

Example

a(4) = 3 corresponding to the following independent dominating sets:
    x . . x      x . x .     . x . x

Prog

(PARI) Vec((1 + x + 2*x^2 - 2*x^3 - 3*x^5 + x^6 + x^8)/((1 - x)*(1 + x + x^2))^3 + O(x^80))

Crossrefs

Row 1 of A397748.

Cf. A397751 (cycle graph).

Sequence in context: A153341 A127119 A322265 * A066704 A262917 A165007

Adjacent sequences: A397747 A397748 A397749 * A397751 A397752 A397753

Keyword

nonn,easy,new

Author

Andrew Howroyd, Jul 13 2026

Status

approved