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

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

Author

Giedrius Alkauskas, Jun 02 2022

Keywords

• nonn
• easy

Comments

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.

Examples

			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*
  *****
		

Links

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

Crossrefs

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

Formula

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)