A287063 Number of dominating sets in the n-crown graph (for n > 1).

3, 9, 39, 183, 833, 3629, 15291, 63051, 256605, 1036401, 4167815, 16720031, 66986169, 268173525, 1073185011, 4293787923, 17177379125, 68714234201, 274866897279, 1099488559527, 4397998277073, 17592085381629, 70368534463019, 281474540503643, 1125899000873613

Offset: 1

Author

Eric W. Weisstein, May 19 2017

Keywords

• nonn
• easy

Comments

The 1-crown graph is the 2-empty graph bar K_2 which has a single dominating set and so differs from a(1) = 3. - Eric W. Weisstein, Sep 04 2021

Links

• Colin Barker, Table of n, a(n) for n = 1..1000
• Eric Weisstein's World of Mathematics, Crown Graph
• Eric Weisstein's World of Mathematics, Dominating Set
• Index entries for linear recurrences with constant coefficients, signature (11,-47,101,-116,68,-16).

Programs

Mathematica

Table[4^n - 2^n (n + 2) + n^2 + n + 3, {n, 25}]
LinearRecurrence[{11, -47, 101, -116, 68, -16}, {3, 9, 39, 183, 833, 3629}, 25]

PARI

Vec( x*(3 - 24*x + 81*x^2 - 126*x^3 + 92*x^4 - 32*x^5) / ((1 - x)^3*(1 - 2*x)^2*(1 - 4*x)) + O(x^30)) \\ Colin Barker, May 19 2017

Formula

a(n) = 4^n - 2^n*(n + 2) + n^2 + n + 3.

From Colin Barker, May 19 2017: (Start)

G.f.: x*(3 - 24*x + 81*x^2 - 126*x^3 + 92*x^4 - 32*x^5) / ((1 - x)^3*(1 - 2*x)^2*(1 - 4*x)).

a(n) = 11*a(n-1) - 47*a(n-2) + 101*a(n-3) - 116*a(n-4) + 68*a(n-5) - 16*a(n-6) for n>6.

(End)