A239231 -id:A239231 - cp's OEIS frontend

A239072 Maximum number of cells in an n X n square grid that can be painted such that no two orthogonally adjacent cells are painted and every unpainted cell can be reached from the edge of the grid by a series of orthogonal steps to unpainted cells.

0, 1, 2, 5, 7, 11, 15, 21, 26, 32, 39, 47, 55, 64, 74, 85, 95, 107, 119, 132, 146, 160, 175, 191, 207, 224

Offset: 0

Elliott Line, Mar 10 2014

This sequence has implications for constructing Steiner trees for square unit arrays of dots: an orthogonal-only tree for an m X m dot array would need m^2-1 units. The value of a(m-1) tells you how many (1+sqrt(3)) 'X' shapes you can place in the grid, each saving (2-sqrt(3)) units.
Unfortunately this doesn't generally lead to the minimal Steiner tree.
An upper bound for this sequence is (((n+1)^2)-1)/3, which is reached iff n = 2^k-1.
The value of a(n)/n^2 (the painted cells as a proportion of all of the cells) converges extremely slowly to 1/3.
This sequence is related to the sequence of Heyawake numbers A239231, which has the additional criterion that the unpainted area should be contiguous. For sufficiently large Heyawake grids, this sequence forms the central (n-4) X (n-4) square of the Heyawake grid.

			For example, if n=6, the painted cells could be A1, A3, A5, B2, B6, C1, C3, C5, D6, E1, E3, E5, F2, F4, F6 (15 cells in all).

Cf. A239231, a similar sequence, with one extra criterion - that the unpainted cells should be contiguous.

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

a(12), a(16), a(22), a(24), a(25) have been 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

A239072 Maximum number of cells in an n X n square grid that can be painted such that no two orthogonally adjacent cells are painted and every unpainted cell can be reached from the edge of the grid by a series of orthogonal steps to unpainted cells.

Views

Author

Keywords

Comments

Examples

Crossrefs

Extensions