A239072 -id:A239072 - cp's OEIS frontend

A239231 Heyawake numbers: maximum number of painted cells in an n X n grid, such that no two painted cells are orthogonally adjacent and the unpainted cells form a contiguous area.

0, 1, 1, 4, 5, 9, 12, 17, 21, 27, 33, 41, 48, 56, 65, 75, 85, 96, 108, 121, 133, 146, 161, 176, 190, 208

Offset: 0

Elliott Line, Mar 13 2014

Inspired by the Japanese puzzle of the same name.

			If n=6, the painted cells could be A1, A3, A6, B5, C1, C3, D4, D6, E2, F1, F4, F6 (12 cells in all).

Wikipedia, Heyawake.

Cf. A239072 (makes up the inner n-4 X n-4 square of the grid).

a(n) = A239072(n-4) + 2*n - 2 for n > 4.

Some values corrected, incorrect values removed by Elliott Line, Aug 21 2014

a(16) and a(20) corrected by Elliott Line at the suggestion of Greg Malen, Sep 02 2020

A354673 Smallest number of unit cells that must be removed from an n X n square board in order to avoid any cycles.

Original entry on oeis.org

0, 1, 2, 4, 6, 10, 13, 18, 22, 28, 34, 42, 49, 58, 66, 76, 86, 98, 109, 122, 134, 148, 162, 178, 193, 210, 226, 244, 262, 282, 301, 322, 342, 364, 386, 410, 433, 458, 482, 508, 534, 562, 589, 618, 646, 676, 706, 738, 769, 802, 834, 868, 902, 938, 973, 1010, 1046

Offset: 1

Giedrius Alkauskas, Jun 02 2022

A "cycle" means a rook-connected closed path of squares.
The proof of this result is given in the Links section.
a(n+1) is very close to A239231(n); more precisely, the difference is the sequence 1,0,1,1,1,1,1,1,1,1,1,2,1,1,1,2,1,1,1,2,1,2,3,2.

			For n = 2, a(2) = 1, since removing any unit square from the 2 X 2 board leaves no cycles.
For n = 5, a(5) = 6 removed unit squares can be arranged as follows:
  x****
  *x*x*
  **x**
  *x*x*
  *****

Giedrius Alkauskas, Maximal subsets of n X n board without cycles, 2022.
Index entries for linear recurrences with constant coefficients, signature (2,-1,0,0,0,1,-2,1).

Cf. A085577, A239072, A085577, A104519, A000170, A239231.

a(n) = ceiling(n^2/3 - n/6 + 4/3) - ceiling(n/2) for n >= 3.
From Stefano Spezia, Jun 02 2022: (Start)
G.f.: x^2*(1 + x^2 + 2*x^4 - x^5 + x^6 - x^7 + x^8)/((1 - x)^3*(1 + x)*(1 - x + x^2)*(1 + x + x^2)).
a(n) = 2*a(n-1) - a(n-2) + a(n-6) - 2*a(n-7) + a(n-8) for n > 2. (End)

cp's OEIS Frontend

A239231 Heyawake numbers: maximum number of painted cells in an n X n grid, such that no two painted cells are orthogonally adjacent and the unpainted cells form a contiguous area.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions