A302689 a(n) = 4 + 2^n - 4*n.

2, 0, 0, 4, 16, 44, 104, 228, 480, 988, 2008, 4052, 8144, 16332, 32712, 65476, 131008, 262076, 524216, 1048500, 2097072, 4194220, 8388520, 16777124, 33554336, 67108764, 134217624, 268435348, 536870800, 1073741708, 2147483528, 4294967172, 8589934464

Offset

1,1

Comments

a(n) is the number of connected dominating sets and total dominating sets in the n-path complement graph for n > 1.

Links

Table of n, a(n) for n=1..33.

Eric Weisstein's World of Mathematics, Connected Dominating Set

Eric Weisstein's World of Mathematics, Path Complement Graph

Eric Weisstein's World of Mathematics, Total Dominating Set

Index entries for linear recurrences with constant coefficients, signature (4,-5,2).

Formula

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

a(n) = 4*a(n-1) - 5*a(n-2) + 2*a(n-3).

a(n) = A258547(n-5) for n > 5 (conjectured).

a(n) = 4 * A000295(n) for n > 1. - Alois P. Heinz, Apr 12 2018

Mathematica

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

Prog

(PARI) a(n) = 4+2^n-4*n; \\ Altug Alkan, Apr 12 2018
(Magma) [4+2^n-4*n : n in [1..45]]; // Vincenzo Librandi, Apr 13 2018

Crossrefs

Cf. A258547.

Sequence in context: A048243 A159814 A169774 * A289088 A057611 A329959

Adjacent sequences: A302686 A302687 A302688 * A302690 A302691 A302692

Keyword

nonn,easy

Author

Eric W. Weisstein, Apr 11 2018

Status

approved