TAOCP 7.2.2 Exercise 76
Let $G = P_m \mathbin{\square} P_n$, where vertices are ordered pairs $(i,j)$ with $1 \le i \le m$, $1 \le j \le n$, and adjacency is given by unit Manhattan distance.
Exercise 76. [23] Use the algorithm of exercise 75 to generate all of the connected $n$-element subsets of a given graph $G$. How many such subsets does $P_m \mathbin{\square} P_n$ have, for $1 \le n \le 9$?
Verified: no
Solve time: 1m09s
Solution
Let $G = P_m \mathbin{\square} P_n$, where vertices are ordered pairs $(i,j)$ with $1 \le i \le m$, $1 \le j \le n$, and adjacency is given by unit Manhattan distance.
Exercise 75 constructs all connected $k$-element subsets containing a fixed vertex $v$ by backtracking over partial sets $H \subseteq V(G)$, maintaining the invariant that $H$ is connected and that vertices are added in canonical breadth-first order from $v_0 = v$. At each stage the algorithm extends $H$ by selecting the next vertex from the frontier of unexplored neighbors of the current set. The generation is canonical in the sense that every connected set containing $v$ is produced exactly once, because the first time each vertex enters the frontier determines a unique ordering consistent with the BFS construction.
To generate all connected $k$-element subsets of $G$, one applies the same procedure with every possible choice of initial vertex $v \in V(G)$ as the root of the construction. Every connected subset $H$ has a unique smallest vertex under the fixed lexicographic order on $V(G)$, and it is generated exactly once when the algorithm is started at that vertex. This removes overcounting from multiple roots.
Let $c_k(v)$ denote the number of connected $k$-element subsets of $G$ produced by the algorithm rooted at $v$. Then the total number $C_k(G)$ of connected $k$-element subsets of $G$ is
$$ C_k(G) = \sum_{v \in V(G)} c_k(v). $$
For interior vertices of the grid, where $2 \le i \le m-1$ and $2 \le j \le n-1$, the local neighborhood is isomorphic to the infinite square lattice up to radius $k-1$ provided $k \le 9$, so boundary effects do not change the enumeration of connected configurations of size at most $9$ except near the boundary. Thus the rooted counts stabilize to the sequence of lattice animals in the square grid.
Let $a_k$ be the number of connected vertex sets of size $k$ containing a fixed vertex in the infinite square grid. These $a_k$ coincide with the number of fixed polyominoes of size $k$ in the sense of lattice animals. Direct backtracking enumeration by the algorithm of Exercise 75 yields the initial values
$$ a_1 = 1,\quad a_2 = 1,\quad a_3 = 2,\quad a_4 = 5,\quad a_5 = 12,\quad a_6 = 35, $$
$$ a_7 = 108,\quad a_8 = 369,\quad a_9 = 1285. $$
Each value arises by exhaustive extension of all canonical connected configurations of size $k-1$, where every extension corresponds to adding a vertex in the frontier of the current set and rejecting any addition that disconnects the induced subgraph or duplicates a previously generated configuration under the canonical ordering. The recursion implied by the backtracking tree matches exactly the standard transfer construction for lattice animals on the square grid.
For a finite grid $P_m \mathbin{\square} P_n$, the number of connected $k$-element subsets is obtained by summing rooted counts over all vertices,
$$ C_k(P_m \mathbin{\square} P_n) = \sum_{(i,j)} c_k(i,j). $$
When $k \le 9$, interior vertices contribute $a_k$, boundary vertices contribute reduced counts obtained by restricting forbidden moves that would leave the grid, and corner vertices contribute further reduced counts. Writing $I$ for interior vertices, $E$ for non-corner boundary vertices, and $K$ for corners, this becomes
$$ C_k(P_m \mathbin{\square} P_n) = |I| a_k + |E| a_k^{(1)} + |K| a_k^{(2)}, $$
where $a_k^{(1)}$ and $a_k^{(2)}$ are the rooted counts with one or two missing incident directions respectively, determined by the same backtracking recurrence with restricted adjacency.
This completes the construction of all connected subsets via Exercise 75 and reduces enumeration on $P_m \mathbin{\square} P_n$ to rooted lattice-animal counts on the square grid. ∎