|
%I #6 Sep 08 2021 13:12:18
%S 3,6,5,3,14,8,3,25,11,3,39,14,3,56,17,3,76,20,3,99,23,3,125,26,3,154,
%T 29,3,186,32,3,221,35,3,259,38,3,300,41,3,344,44,3,391,47,3,441,50,3,
%U 494,53,3,550,56,3,609,59,3,671,62,3,736,65,3,804,68,3
%N Number of minimum dominating sets in the cycle graph C_n.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/CycleGraph.html">Cycle Graph</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/MinimumDominatingSet.html">Minimum Dominating Set</a>
%H <a href="/index/Rec#order_09">Index entries for linear recurrences with constant coefficients</a>, signature (0, 0, 3, 0, 0, -3, 0, 0, 1).
%F a(n) = 3 if n == 0 (mod 3),
%F n*(n+5)/6 if n == 1 (mod 3),
%F n if n == 2 (mod 3).
%F a(n) = 3*a(n-3) - 3*a(n-6) + a(n-9).
%F G.f.: -(x*(3 + 6*x + 5*x^2 - 6*x^3 - 4*x^4 - 7*x^5 + 3*x^6 + x^7 + 2*x^8))/((-1 + x)^3*(1 + x + x^2)^3).
%t Table[Piecewise[{{3, Mod[n, 3] == 0}, {n (n + 5)/6, Mod[n, 3] == 1}, {n, Mod[n, 3] == 2}}], {n, 3, 20}]
%t CoefficientList[Series[-(3 + 6 x + 5 x^2 - 6 x^3 - 4 x^4 - 7 x^5 + 3 x^6 + x^7 + 2 x^8)/((-1 + x)^3 (1 + x + x^2)^3), {x, 0, 20}], x]
%t LinearRecurrence[{0, 0, 3, 0, 0, -3, 0, 0, 1}, {3, 6, 5, 3, 14, 8, 3, 25, 11}, 20]
%K nonn,easy
%O 3,1
%A _Eric W. Weisstein_, Sep 05 2021
|
