login
Number of dominating sets in the n-gear graph.
2

%I #13 May 16 2018 20:01:20

%S 5,23,83,291,1015,3539,12339,43043,150239,524723,1833771,6412467,

%T 22437095,78553491,275180323,964534339,3382685743,11869824179,

%U 41673547291,146387820371,514484547639,1809077492883,6364347723667,22400458807139,78878848178815,277881197881011

%N Number of dominating sets in the n-gear graph.

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

%H James East, Jitender Kumar, James D.Mitchell, Wilf A. Wilson, <a href="https://arxiv.org/abs/1706.04967">Maximal subsemigroups of finite transformation and diagram monoids</a>, Journal of Algebra (2018), 504, 176-216, arXiv:1706.04967 [math.GR], 2017-2018.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/DominatingSet.html">Dominating Set</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/GearGraph.html">Gear Graph</a>

%H <a href="/index/Rec#order_06">Index entries for linear recurrences with constant coefficients</a>, signature (7, -12, -2, 3, 3, 2).

%F 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).

%F 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).

%t Table[(1/2 (3 - Sqrt[17]))^n + (1/2 (3 + Sqrt[17]))^n - 1 + RootSum[-1 - # - 3 #^2 + #^3 &, #^n &], {n, 20}] // Expand

%t LinearRecurrence[{7, -12, -2, 3, 3, 2}, {5, 23, 83, 291, 1015, 3539}, 20]

%t 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]

%Y Cf. A290378 (minimal dominating sets).

%K nonn

%O 1,1

%A _Eric W. Weisstein_, Aug 14 2017