A290938 Number of dominating sets in the n-gear graph.

5, 23, 83, 291, 1015, 3539, 12339, 43043, 150239, 524723, 1833771, 6412467, 22437095, 78553491, 275180323, 964534339, 3382685743, 11869824179, 41673547291, 146387820371, 514484547639, 1809077492883, 6364347723667, 22400458807139, 78878848178815, 277881197881011

Offset: 1

Author

Eric W. Weisstein, Aug 14 2017

Keywords

• nonn

Comments

Extended to a(1)-a(2) using the formula/recurrence.

Links

• James East, Jitender Kumar, James D.Mitchell, Wilf A. Wilson, Maximal subsemigroups of finite transformation and diagram monoids, Journal of Algebra (2018), 504, 176-216, arXiv:1706.04967 [math.GR], 2017-2018.
• Eric Weisstein's World of Mathematics, Dominating Set
• Eric Weisstein's World of Mathematics, Gear Graph
• Index entries for linear recurrences with constant coefficients, signature (7, -12, -2, 3, 3, 2).

Crossrefs

Cf. A290378 (minimal dominating sets).

Programs

Mathematica

Table[(1/2 (3 - Sqrt[17]))^n + (1/2 (3 + Sqrt[17]))^n - 1 + RootSum[-1 - # - 3 #^2 + #^3 &, #^n &], {n, 20}] // Expand
LinearRecurrence[{7, -12, -2, 3, 3, 2}, {5, 23, 83, 291, 1015, 3539}, 20]
CoefficientList[Series[(-5 + 12 x + 18 x^2 + 4 x^3 - 5 x^4 - 8 x^5)/(-1 + 7 x - 12 x^2 - 2 x^3 + 3 x^4 + 3 x^5 + 2 x^6), {x, 0, 20}], x]

Formula

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

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