Counting the number of grids with certain disallowed dominoes 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.
 A: 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.
A: I want to expand on Brendan McKay's comment that there exists "a recurrence with very many variables". Indeed, it's possible to make a such a recurrence for the sequence $j \mapsto a_{i,j}$ with $i$ fixed. Here's the general strategy:
If $i = 1$, we are looking for all strings formed from $\{1, \dots, n\}$ which don't contain certain length-$2$ substrings. This can be done as follows:


*

*Let $M$ be the $n \times n$ real matrix defined by
$$M_{j,k} = \begin{cases} 1 &: [j \; k] \notin \mathcal{S} \\ 0 &: \text{otherwise} \end{cases}$$

*It's easy to show by induction that $a_{1,\ell}$ is the sum of entries of $M^{\ell-1}$ for all $\ell \geq 1$, which is to say $a_{1,\ell}$ is the sum of entries of $M^{\ell-1} v$ where $v$ is the vector consisting of all $1$'s. $M$ gives a recurrence relation for each entry of $M^{\ell-1} v$, from which you can get a recurrence relation for $a_{1,\ell}$. More directly, you can have a computer determine the matrix $M$ and take powers of it to give you $a_{1,\ell}$ for reasonable values of $\ell$.


Now, if $i > 1$, we can reduce to the case $i=1$ (for a different value of $n$) by viewing an $i \times j$ grid as a $1 \times j$ grid of $i \times 1$ grids!
