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
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).
Programs
-
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
-
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
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)