A350816 Number of minimum dominating sets in the 2 X n king graph.

2, 4, 2, 16, 12, 4, 64, 32, 8, 208, 80, 16, 608, 192, 32, 1664, 448, 64, 4352, 1024, 128, 11008, 2304, 256, 27136, 5120, 512, 65536, 11264, 1024, 155648, 24576, 2048, 364544, 53248, 4096, 843776, 114688, 8192, 1933312, 245760, 16384, 4390912, 524288, 32768

Offset: 1

Author

Andrew Howroyd, Jan 17 2022

Keywords

• nonn
• easy

Links

• Andrew Howroyd, Table of n, a(n) for n = 1..1000
• Eric Weisstein's World of Mathematics, King Graph
• Eric Weisstein's World of Mathematics, Minimum Dominating Set
• Index entries for linear recurrences with constant coefficients, signature (0,0,6,0,0,-12,0,0,8).

Crossrefs

Row 2 of A350815.

Cf. A000079, A001787, A076616, A347558, A347633.

Programs

PARI

Vec(2*(1 - x)*(1 + 3*x + 4*x^2 + 6*x^3 - 4*x^5 - 8*x^6 - 4*x^7)/(1 - 2*x^3)^3 + O(x^45))

PARI

a(n) = {my(t=n\3); 2^t*if(n%3==0, 1, if(n%3==1, t^2 + 5*t + 2, 2*t + 4))}

Formula

a(n) = 6*a(n-3) - 12*a(n-6) + 8*a(n-9) for n > 9.

G.f.: 2*x*(1 - x)*(1 + 3*x + 4*x^2 + 6*x^3 - 4*x^5 - 8*x^6 - 4*x^7)/(1 - 2*x^3)^3.

a(3*n) = 2^n; a(3*n+1) = (n^2 + 5*n + 2)*2^n; a(3*n+2) = (n + 2)*2^(n+1).

a(3*n) = A000079(n); a(3*n+1) = A076616(n+3); a(3*n+2) = A001787(n+2).