login
Number of connected dominating sets in the complete tripartite graph K_{n,n,n}.
2

%I #28 Dec 25 2021 09:03:56

%S 7,54,490,4050,32674,261954,2096770,16776450,134216194,1073738754,

%T 8589928450,68719464450,549755789314,4398046461954,35184371990530,

%U 281474976514050,2251799813292034,18014398508695554,144115188074283010,1152921504603701250

%N Number of connected dominating sets in the complete tripartite graph K_{n,n,n}.

%C For n > 1, the only dominating sets that are not connected are the 3 sets consisting of all vertices from a single partition. For n > 1, the only connected sets that are not dominating are the 3n sets consisting of a single vertex. - _Andrew Howroyd_, Aug 30 2017

%H Colin Barker, <a href="/A291703/b291703.txt">Table of n, a(n) for n = 1..1000</a>

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

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

%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (11,-26,16).

%F a(n) = A291537(n) - 3 = A290756(n) - 3*n for n > 1. - _Andrew Howroyd_, Aug 30 2017

%F From _Colin Barker_, Sep 01 2017: (Start)

%F G.f.: x*(7 - 23*x + 78*x^2 - 48*x^3) / ((1 - x)*(1 - 2*x)*(1 - 8*x)).

%F a(n) = 2 - 3*2^n + 8^n for n > 1.

%F a(n) = 11*a(n-1) - 26*a(n-2) + 16*a(n-3) for n > 4.

%F (End)

%F a(n) = A302942(n) for n > 1. - _Eric W. Weisstein_, Apr 16 2018

%F E.g.f.: 3*x + exp(x)*(2 - 3*exp(x) + exp(7*x)). - _Stefano Spezia_, Dec 24 2021

%t a[1] = 7; a[n_] := 2 - 3*2^n + 8^n; Array[a, 20] (* _Jean-François Alcover_, Oct 08 2017 *)

%t (* Start from _Eric W. Weisstein_, Oct 12 2017 *)

%t Table[Piecewise[{{7, n == 1}}, 2 - 3 2^n + 8^n], {n, 20}]

%t Table[Piecewise[{{7, n == 1}}, 2 (2^(n - 1) + 1) (2^n - 1)^2], {n, 20}]

%t Join[{7}, LinearRecurrence[{11, -26, 16}, {54, 490, 4050}, 20]]

%t CoefficientList[Series[(-7 + 23 x - 78 x^2 + 48 x^3)/(-1 + 11 x - 26 x^2 + 16 x^3), {x, 0, 20}], x]

%t (* End *)

%o (PARI) a(n) = if(n < 2, [7][n], 8^n - 3*2^n + 2); \\ _Andrew Howroyd_, Aug 30 2017

%o (PARI) Vec(x*(7 - 23*x + 78*x^2 - 48*x^3) / ((1 - x)*(1 - 2*x)*(1 - 8*x)) + O(x^30)) \\ _Colin Barker_, Sep 01 2017

%Y Cf. A290756, A291537.

%Y Cf. A302942.

%K nonn,easy

%O 1,1

%A _Eric W. Weisstein_, Aug 30 2017

%E a(8)-a(20) from _Andrew Howroyd_, Aug 30 2017