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,3

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.

In other words, the feedback vertex set (or decycling) number of the n X n grid graph. - Eric W. Weisstein, Jan 27 2026

Links

Table of n, a(n) for n=1..57.

Giedrius Alkauskas, Maximal subsets of n X n board without cycles, 2022.

Eric Weisstein's World of Mathematics, Feedback Vertex Set Number.

Eric Weisstein's World of Mathematics, Grid Graph.

Index entries for linear recurrences with constant coefficients, signature (2,-1,0,0,0,1,-2,1).

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)

a(n) = n^2 - A360921(n). - Andrew Howroyd, Jan 27 2026

Example

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

Mathematica

Table[Piecewise[{{n - 1, n == 1 || n == 2}}, Ceiling[n^2/3 - n/6 + 4/3] - Ceiling[n/2]], {n, 20}] (* Eric W. Weisstein, Jan 27 2026 *)
Join[{0, 1}, LinearRecurrence[{2, -1, 0, 0, 0, 1, -2, 1}, {2, 4, 6, 10, 13, 18, 22, 28}, 20]] (* Eric W. Weisstein, Jan 27 2026 *)
CoefficientList[Series[-x (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)), {x, 0, 20}], x] (* Eric W. Weisstein, Jan 27 2026 *)

Crossrefs

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

Sequence in context: A334821 A275489 A153817 * A309616 A365321 A267452

Adjacent sequences: A354670 A354671 A354672 * A354674 A354675 A354676

Keyword

nonn,easy

Author

Giedrius Alkauskas, Jun 02 2022

Status

approved