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.
Best Answer
Rewrite the recurrence: $$B_{n+1}=\sum_{k=0}^n\binom{n}kB_k=\sum_{k=0}^n\binom{n}{n-k}B_k=\sum_{k=0}^n\binom{n}kB_{n-k}\;.$$
To form a partition of $[n+1]$, first fix the part containing $n+1$; say that it has $k$ other elements. There are $\binom{n}k$ ways to choose these other elements, and there are $B_{n-k}$ ways to partition the remaining $n-k$ elements of $[n+1]$, so there are $\binom{n}kB_{n-k}$ partitions of $[n+1]$ that have $n+1$ in a part with exactly $k$ other elements. Summing over the possible values of $k$ yields the recurrence.
There isn’t a nice closed form; see Wikipedia for a not so nice expression involving Stirling numbers of the second kind and for asymptotic results.