A291773 Domination number of the n-Apollonian network.
1, 1, 3, 4, 7, 16, 43, 124, 367, 1096, 3283, 9844, 29527, 88576, 265723, 797164, 2391487, 7174456, 21523363, 64570084, 193710247, 581130736, 1743392203, 5230176604, 15690529807, 47071589416, 141214768243, 423644304724, 1270932914167, 3812798742496
Offset: 1
Links
- Colin Barker, Table of n, a(n) for n = 1..1000
- Eric Weisstein's World of Mathematics, Apollonian Network
- Eric Weisstein's World of Mathematics, Connected Domination Number
- Eric Weisstein's World of Mathematics, Domination Number
- Index entries for linear recurrences with constant coefficients, signature (4,-3).
Crossrefs
Cf. A298105.
Programs
-
Mathematica
(* Start from Eric W. Weisstein, Jan 17 2018 *) Join[{1, 1}, Table[(3^(n - 3) + 5)/2, {n, 3, 20}]] Join[{1, 1}, Table[(3^n + 135)/54, {n, 3, 20}]] Join[{1, 1}, (3^Range[3, 20] + 135)/54] Join[{1, 1}, LinearRecurrence[{4, -3}, {3, 4}, 20]] CoefficientList[Series[(1 - 3 x + 2 x^2 - 5 x^3)/(1 - 4 x + 3 x^2), {x, 0, 20}], x] (* End *)
-
PARI
\\ here d0..d3 are for 0..3 outside vertices included in dominating set. D(d0,d1,d2,d3) = {[min(3*d0,1+3*d1), min(d0+2*d1,1+d1+2*d2), min(2*d1+d2,1+2*d2+d3), min(3*d2,1+3*d3)]} a(n)={my(v=[1,0,0,0]); for(i=2,n,v=D(v[1],v[2],v[3],v[4])); min(min(v[1],1+v[2]),min(2+v[3],3+v[4]))} \\ Andrew Howroyd, Sep 01 2017 -
PARI
Vec(x*(1 - 3*x + 2*x^2 - 5*x^3) / ((1 - x)*(1 - 3*x)) + O(x^40)) \\ Colin Barker, Oct 03 2017
Formula
a(n) = (3^(n-3) + 5) / 2 for n > 2. - Andrew Howroyd, Sep 01 2017
From Colin Barker, Oct 03 2017: (Start)
G.f.: x*(1 - 3*x + 2*x^2 - 5*x^3) / ((1 - x)*(1 - 3*x)).
a(n) = 4*a(n-1) - 3*a(n-2) for n>4.
(End)
a(n) = A289521(n-3) for n > 3. - Andrew Howroyd, Jan 16 2018
Extensions
a(7)-a(30) from Andrew Howroyd, Sep 01 2017
Comments