I had my student, Tim Michaels, work on this. We came up with a complicated recurrence relation,
indicated below. The first few answers are 1, 2, 6, 25, 128, 758, 5014, 36194, 280433, 2303918, 19885534, 179028087, 1671644720, 16114138846, 159761516110, 1623972412726,
16880442523007, 179026930243822, 1933537655138482, 21231023519199575,
236674460790503286, 2675162663681345170, 30625903703241927542,
354767977792683552908, 4154708768196322925749,
49152046198035152483150, 587011110939295781585102,
7072674305834582713614923. Note that we are counting rotations and reflections as distinct tilings. An interesting pattern is that mod 2, there is an 8-fold periodicity which we don't understand and can't prove in general.
Here's a picture of the cases n=1,2,3,4, with 1,2,6,25 tilings in each case.The way to systematically generate these is to "push in" a vertical line from the right to all previously constructed tilings in all possible ways. That's how the recurrence relation is defined.
Okay, here is the recurrence:
Let $a_{\ell,j,m}$ be the number of distinct tilings with $\ell$ tiles, $j$ edges that meet the right-hand side of the square and $m$ 4-valent vertices.
$$a_{\ell,j,m}=\sum_{p=1}^\ell(-1)^{p+1}\sum_{i=0}^m\sum_{n=1}^{\ell-1}\sum_{k=0}^{n-1}\alpha_{n,k,i,\ell,j,m,p} a_{n,k,i}$$
where, letting $t=m-i, s=\ell-n-p-t$ and $r=k+s+t+p-j$,
$$\alpha_{n,k,i,l,j,m,p}=\binom{r-1}{p-1}\binom{k-r+2}{p}\binom{s+r-1}{r-1}\binom{r-p}{t}.$$
Edit: I have posted a preprint describing the recurrence relation here. Comments are welcome. Is this sort of thing publishable anywhere to anyone's knowledge?
Edit 2: Nathan Reading has just posted a relevant preprint. He finds a bijection between generic tilings (no 4-valent vertices) and a set of permutations that avoid a certain pattern.
Edit 3: The paper has been published in the Annals of Combinatorics.
We will count $n\!\times\!3$ grids containing no $2\!\times\!2$ block of $1$s ("three-row square-free grids"):
If we encode the columns by integers using the entries as the digits of a binary number, then for three rows, we have three classes of columns: $A=\{0,1,2,4,5\}$, $B=\{3,6\}$ and $C=\{7\}$, with transfer matrix $M=\Big(\begin{smallmatrix}5&2&1\\5&1&0\\5&0&0\end{smallmatrix}\Big)$.
The number of three-row square-free grids is thus the sum of the entries in the vector $$(5,2,1)\,M^{n-1}.$$
The closed form is complex, involving roots of cubic polynomials.
The first few terms are $8, 57, 417, 3032, 22077, 160697, 1169792, 8515337, 61986457, 451223152$. This is A181246 in OEIS.
Alternatively, if we let $a(z)$, $b(z)$ and $c(z)$ be the (ordinary) generating functions for $n\!\times\!3$ square-free grids where the final column is in classes $A$, $B$ and $C$ respectively, and we let $g_3(z)$ be the OGF for all three-row square-free grids, then solving the equations
$$\begin{array}{rcl}a(z) &=& 5 z + z\:\! (5 a(z) + 5 b(z) + 5 c(z))\\ b(z) &=& 2 z + z\:\! (2 a(z) + b(z))\\c(z) &=& z + z\:\! a(z)\\g_3(z)&=&a(z)+b(z)+c(z)\end{array}$$
gives
$$g_3(z)\;=\;\frac{z\:\! (8 + 9 z - 5 z^2)}{1 - 6 z - 10 z^2 + 5 z^3}.$$
For four-row grids, five classes are required, with transfer matrix $\left(
\begin{smallmatrix}
8 & 4 & 1 & 2 & 1 \\
8 & 2 & 1 & 1 & 0 \\
8 & 4 & 0 & 0 & 0 \\
8 & 2 & 0 & 0 & 0 \\
8 & 0 & 0 & 0 & 0
\end{smallmatrix}
\right)$, giving generating function $\frac{8 z (2+7 z+z^2-8 z^3)}{1-10 z-54 z^2-16 z^3+64 z^4}$.
There are many numerical results in OEIS: three rows, four rows, five rows, six rows, seven rows, eight rows, and nine rows.
Best Answer
You are asking about partitions if the order doesn't matter, and compositions if it does. It sounds like 13 is different from 31, so compositions are what you are after.