login
Independent domination number of the n X n grid graph.
2

%I #52 May 07 2019 15:10:20

%S 0,1,2,3,4,7,10,12,16,21,24,30,35,40,47,53,60,68,76,84,92,101,111,121,

%T 131,141,152,164,176,188,200,213,227,241,255,269,284,300,316,332,348,

%U 365,383,401,419,437,456,476,496,516,536,557,579,601,623,645,668

%N Independent domination number of the n X n grid graph.

%H Colin Barker, <a href="/A321684/b321684.txt">Table of n, a(n) for n = 0..1000</a>

%H Simon Crevals, Patric R. J. Östergård, <a href="https://doi.org/10.1016/j.disc.2015.02.015">Independent domination of grids</a>, Discrete Math., 338 (2015), 1379-1384.

%H <a href="/index/Rec#order_07">Index entries for linear recurrences with constant coefficients</a>, signature (2,-1,0,0,1,-2,1).

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

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

%F From _Colin Barker_, Jan 14 2019: (Start)

%F 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)).

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

%F (End)

%p 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):

%p (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

%o (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

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

%K nonn,easy

%O 0,3

%A _Andrey Zabolotskiy_, Jan 14 2019