A321684 Independent domination number of the n X n grid graph.

0, 1, 2, 3, 4, 7, 10, 12, 16, 21, 24, 30, 35, 40, 47, 53, 60, 68, 76, 84, 92, 101, 111, 121, 131, 141, 152, 164, 176, 188, 200, 213, 227, 241, 255, 269, 284, 300, 316, 332, 348, 365, 383, 401, 419, 437, 456, 476, 496, 516, 536, 557, 579, 601, 623, 645, 668

Offset

0,3

Links

Colin Barker, Table of n, a(n) for n = 0..1000

Simon Crevals, Patric R. J. Östergård, Independent domination of grids, Discrete Math., 338 (2015), 1379-1384.

Index entries for linear recurrences with constant coefficients, signature (2,-1,0,0,1,-2,1).

Formula

For n >= 14, a(n) = floor((n+2)^2 / 5 - 4).

a(n) = A104519(n+2), the domination number of the n X n grid graph, for all n except for n = 9, 11.

From Colin Barker, Jan 14 2019: (Start)

G.f.: x*(1 + 2*x^4 - x^5 - x^6 + 2*x^7 + x^8 - 4*x^9 + 3*x^10 - 2*x^12 + x^13 + x^14 - 2*x^15 + 2*x^16 - 2*x^18 + x^19) / ((1 - x)^3*(1 + x + x^2 + x^3 + x^4)).

a(n) = 2*a(n-1) - a(n-2) + a(n-5) - 2*a(n-6) + a(n-7) for n > 20.

(End)

Maple

ogf := (-41*x^6 + 47*x^5 - x^3 - x^2 + 41*x - 47)/((x - 1)^3*(x^4 + x^3 + x^2 + x + 1)): ser := series(ogf, x, 44):
(0, 1, 2, 3, 4, 7, 10, 12, 16, 21, 24, 30, 35, 40), seq(coeff(ser, x, n), n=0..42); # Peter Luschny, Jan 14 2019

Prog

(PARI) concat(0, Vec(x*(1 + 2*x^4 - x^5 - x^6 + 2*x^7 + x^8 - 4*x^9 + 3*x^10 - 2*x^12 + x^13 + x^14 - 2*x^15 + 2*x^16 - 2*x^18 + x^19) / ((1 - x)^3*(1 + x + x^2 + x^3 + x^4)) + O(x^40))) \\ Colin Barker, Jan 14 2019

Crossrefs

Cf. A104519, A075324, A299029, A279404, A291297.

Sequence in context: A135419 A051914 A104519 * A117220 A118426 A082008

Adjacent sequences: A321681 A321682 A321683 * A321685 A321686 A321687

Keyword

nonn,easy

Author

Andrey Zabolotskiy, Jan 14 2019

Status

approved