OFFSET
0,3
COMMENTS
List of quadruples: 2*n*(3*n+1), (2*n+1)*(3*n+1), 6*n^2+8*n+3, (n+1)*(6*n+5). These terms belong to the sequences A033580, A033570, A126587 and A049452, respectively. See links for all the permutations.
After 0, subsequence of A025767.
It seems that a(n) is the smallest number of cells that need to be painted in a (n+1) X (n+1) grid, such that it has no unpainted hexominoes (see link to Kamenetsky and Pratt). - Rob Pratt, Dmitry Kamenetsky, Aug 30 2020
LINKS
Harvey P. Dale, Table of n, a(n) for n = 0..1000
Luce ETIENNE, Permutations
Dmitry Kamenetsky and Rob Pratt, 10x10 grid with no unpainted hexominoes, Puzzling StackExchange, October 2019.
Rob Pratt, Optimal solution for n=11.
Index entries for linear recurrences with constant coefficients, signature (2,-1,0,1,-2,1).
FORMULA
G.f.: x*(1 + x + x^3)/((1 + x)*(1 + x^2)*(1 - x)^3).
a(n) = 2*a(n-1) - a(n-2) + a(n-4) - 2*a(n-5) + a(n-6) for n>5.
a(n) = floor((3*n + 2)^2/24 + 2/3).
a(n) = (6*n^2 + 8*n + 3 + (-1)^n - 2*((-1)^((2*n - 1 + (-1)^n)/4) + (-1)^((2*n + 1 - (-1)^n)/4)))/16. Therefore:
a(2*k) = (6*k^2 + 4*k + 1 - (-1)^k)/4,
a(2*k+1) = (k + 1)*(3*k + 2)/2.
a(n) = (6*n^2 + 8*n + 3 + cos(n*Pi) - 4*cos(n*Pi/2))/16.
a(n) = (3*n + 2)^2/24 + 1/3 + (-6 + (1 + (-1)^n)*(1 + 2*i^((n+1)*(n+2))))/16, where i=sqrt(-1).
EXAMPLE
Rectangular array with four columns:
. 0, 1, 3, 5;
. 8, 12, 17, 22;
. 28, 35, 43, 51;
. 60, 70, 81, 92;
. 104, 117, 131, 145, etc.
From Rob Pratt, Aug 30 2020: (Start)
For n = 3, painting only 2 cells would leave an unpainted hexomino, but painting the following 3 cells avoids all unpainted hexominoes:
. . .
. . X
X X .
(End)
MATHEMATICA
Table[Floor[(3 n + 2)^2/24 + 1/3], {n, 0, 50}] (* or *) CoefficientList[Series[x (1 + x + x^3)/((1 + x) (1 + x^2) (1 - x)^3), {x, 0, 50}], x] (* or *) Table[(6 n^2 + 8 n + 3 + Cos[n Pi] - 4 Cos[n Pi/2])/16, {n, 0, 50}] (* or *) Table[(3 n + 2)^2/24 + 1/3 + (-6 + (1 + (-1)^n) (1 + 2 I^((n + 1) (n + 2))))/16, {n, 0, 50}] (* Michael De Vlieger, Feb 17 2017 *)
LinearRecurrence[{2, -1, 0, 1, -2, 1}, {0, 1, 3, 5, 8, 12}, 60] (* Harvey P. Dale, Aug 10 2024 *)
PROG
(PARI) a(n)=(3*n^2 + 4*n + 4)\8 \\ Charles R Greathouse IV, Feb 17 2017
(Magma) [(3*n^2+4*n+4) div 8: n in [0..50]]; // Bruno Berselli, Feb 17 2017
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Luce ETIENNE, Feb 17 2017
EXTENSIONS
Corrected and extended by Bruno Berselli, Feb 17 2017
STATUS
approved