A289254 a(n) = 4^n - 3*n - 1.

0, 9, 54, 243, 1008, 4077, 16362, 65511, 262116, 1048545, 4194270, 16777179, 67108824, 268435413, 1073741778, 4294967247, 17179869132, 68719476681, 274877906886, 1099511627715, 4398046511040, 17592186044349, 70368744177594, 281474976710583, 1125899906842548

Offset: 1

Author

Eric W. Weisstein, Jun 29 2017

Keywords

• nonn
• easy

Comments

Number of connected dominating sets in the n-cocktail party graph.

Links

• Colin Barker, Table of n, a(n) for n = 1..1000
• Eric Weisstein's World of Mathematics, Cocktail Party Graph
• Eric Weisstein's World of Mathematics, Connected Dominating Set
• Index entries for linear recurrences with constant coefficients, signature (6,-9,4).

Crossrefs

Column 1 of A174266.

Programs

Magma

[4^n -(3*n+1): n in [1..30]]; // G. C. Greubel, Mar 26 2022

Mathematica

Table[4^n - 3 n - 1, {n, 20}]
LinearRecurrence[{6, -9, 4}, {0, 9, 54}, 20]
CoefficientList[Series[-((9 x)/((-1 + x)^2 (-1 + 4 x))), {x, 0, 20}], x]

PARI

concat(0, Vec(9*x^2 / ((1 - x)^2*(1 - 4*x)) + O(x^30))) \\ Colin Barker, Jun 30 2017

Sage

[4^n -(3*n+1) for n in (1..30)] # G. C. Greubel, Mar 26 2022

Formula

a(n) = 4^n - 3*n - 1.

a(n) = 6*a(n-1) - 9*a(n-2) + 4*a(n-2).

G.f.: 9*x^2/((1-x)^2*(1-4*x)).

E.g.f.: exp(4*x) - (1+3*x)*exp(x). - G. C. Greubel, Mar 26 2022