I'm curious if there is a general strategy for solving the following kind of counting problem.


Fix a positive integer $n$, and let $[n] = \{1, \dots, n\}$.




---


**Preliminaries**


*Definition* An $n$-grid of size $i \times j$ is a function $[i] \times [j] \to [n]$. Equivalently, this is an $i \times j$ matrix with entries in $[n]$.


*Definition* An $n$-domino is an $n$-grid of size $1 \times 2$ or $2 \times 1$.


*Definition* If $G\_1$ and $G\_2$ are $n$-grids, we say that $G\_1 \preceq G\_2$ if $G\_1$ occurs as a contiguous sub-grid of $G\_2$.


More precisely, if $G\_1 : [i\_1] \times [j\_1] \to [n]$ and $G\_2 : [i\_2] \times [j\_2] \to [n]$ then $G\_1 \preceq G\_2$ if and only if there exist non-negative integers $s, t$ such that $i\_1 + s \leq i\_2$, $j\_1 + t \leq j\_2$, and $G\_2(x+s,y+t) = G\_1(x,y)$ for all $(x,y) \in [i\_1] \times [j\_1]$.


$\preceq$ is actually a partial order on $n$-grids, so this notation is not evil.


Let $\mathcal{G}\_{i,j}$ be the set of $n$-grids of size $i \times j$. Let $\mathcal{D} = \mathcal{G}\_{1,2} \cup \mathcal{G}\_{2,1}$ be the set of $n$-dominoes.




---


**Problem** Given $\mathcal{S} \subseteq \mathcal{D}$, can we find a recurrence relation (or something) for the 2-dimensional sequence
$$a\_{i,j} = \lvert \{G \in \mathcal{G}\_{i,j} : \forall D \in \mathcal{S} (D \not\preceq G)\} \rvert?$$


In other words, I'm wondering if there is a strategy for counting the number of $i \times j$ $n$-grids which don't contain certain disallowed dominoes.



Counting the number of grids with certain disallowed dominoes
The case of $n=2$ and $\mathcal{S}=\lbrace[2,2],[2,2]^T\rbrace$ is the much studied "hard square entropy" problem. No simple formula or recurrence is known, though a recurrence with very many variables (basically, dynamic programming) allows computation of small values. It is known in this case that $a\_{i,i}^{1/i^2}$ converges to a constant about 1.503. This "hard square entropy constant" is known to many digits but not exactly identified. Probably a similar limit exists for other values of $\mathcal{S}$.


Also see <http://oeis.org/A006506>.


