Exact Adjacency Bounds for Rectangular Grid Subsets

We study the minimum and maximum possible numbers of horizontal and vertical adjacencies that can occur among subsets of fixed size in rectangular grid graphs. For an r × c grid and an occupancy size o, we define a min (r, c, o) and a max (r, c, o) as the smallest and largest achievable adjacency counts, respectively. We present explicit, closed-form, piecewise formulas for both quantities. These formulas are validated against exhaustive dynamic programming (DP) enumerations for 242 grid sizes, covering a wide range of geometries and parity classes. The results provide sharp, exact bounds on the support of the adjacency distribution m(r, c, o, a), and enable fast, DP-free analysis of extremal configurations.