A287431 Number of connected dominating sets in the n-gear graph.

7, 21, 45, 129, 373, 1177, 3741, 12065, 38949, 125993, 407597, 1318961, 4268085, 13811769, 44695613, 144638017, 468058181, 1514668105, 4901568589, 15861809233, 51329892437, 166107021401, 537533612125, 1739495309409, 5629125066853, 18216231370857, 58948963008621

Offset

1,1

Links

Colin Barker, Table of n, a(n) for n = 1..1000

Eric Weisstein's World of Mathematics, Connected Dominating Set

Eric Weisstein's World of Mathematics, Gear Graph

Index entries for linear recurrences with constant coefficients, signature (4,-1,-6,4).

Formula

From Colin Barker, May 25 2017: (Start)

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

a(n) = 1 + 4*n + (1-sqrt(5))^n + (1+sqrt(5))^n.

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

Mathematica

LinearRecurrence[{4, -1, -6, 4}, {7, 21, 45, 129}, 20]
Table[2^n LucasL[n] + 4 n + 1, {n, 20}]

Prog

(PARI) Vec(x*(7 - 7*x - 32*x^2 + 12*x^3) / ((1 - x)^2*(1 - 2*x - 4*x^2)) + O(x^30)) \\ Colin Barker, May 25 2017

Crossrefs

Sequence in context: A256051 A299254 A146411 * A127736 A212677 A146802

Adjacent sequences: A287428 A287429 A287430 * A287432 A287433 A287434

Keyword

nonn,easy

Author

Eric W. Weisstein, May 25 2017

Status

approved