How many valid mazes of some size are there?

Question

A square grid of size $n\times m$ is given, where each tile can either be a floor tile or a wall tile.

One corner tile represents the entrance, and the opposite corner tile of that is called the exit.
These two tiles cannot be a wall tile and are classified as a floor tile.

A grid configuration is a valid maze if both properties hold:

• Entrance and exit tiles are connected. That is, one should be able to move from the entrance to the exit tile by only moving up, down, left or right at each step, walking over floor tiles.

• No floor tile is fully enclosed by wall tiles. That is, starting at any floor tile, one should be able to visit every other floor tile by moving only in those four directions, on floor tiles.

Let there be only one unique entrance-exit configuration, so one can assume that the entrance tile is at the bottom left corner and that the exit tile is at the upper right corner

How many valid mazes are there for a grid of size $n\times m$? ($n,m\ge2$)

That is, how can we find $N(n,m)$ - number of valid mazes as descrbed above?

Trivially, we have a simple bound;

$$N(n,m)\le \sum_{k=0}^{nm-2-(n+m-3)}\binom{nm-2}{k}\lt2^{nm-2}$$

Since the grid has $(nm-2)$ tiles that can either be a wall or floor, and at least $(n+m-3)$ of those tiles must be floor tiles, or we would not have a connected path from entrance to exit.

But I'm not sure how to count all of the invalid mazes that have unreachable floor tiles.

I've tried observing cases split into sets each with cases with $k$ walls to see how many invalid cases I can count depending on $k$ and $m,n$, but wasn't able to find a general pattern, nor was sure about it as I kept noticing I was missing cases or counting some more than once as I was not sure how to do it properly.

Answer 1

Trivially, $N(n,1)=1$, for all positive integers $n$.

For $m > 1$, some results are known . . .

• For $N(n,2)$, a generating function is known:

$\qquad\qquad$https://oeis.org/A048739

• For $N(n,3)$, a generating function is known:

$\qquad\qquad$https://oeis.org/A163003

• For $N(n,4)$, data is known for $1 \le n \le 18$:

$\qquad\qquad$https://oeis.org/A163004

• For $N(n,5)$, data is known for $1 \le n \le 17$:

$\qquad\qquad$https://oeis.org/A163005

• For $N(n,6)$, data is known for $1 \le n \le 12$:

$\qquad\qquad$https://oeis.org/A163006

It's fairly clear that for $m > 3$, only limited data is known, with no suggestion of a formula, recursion, or generating function.

Answer 2

In addition to quasi's answer and your calculated upper bound, there is also a trivial lower bound. There is a subset of mazes where the shortest path from the southwest corner to the northeast corner consists of only eastward steps and northward steps. By analyzing the number of combinations of the steps in such paths, it can be shown that the minimal size of this set of mazes is $${}_{\alpha+\beta} \mathrm{ C }_\alpha={}_{\alpha+\beta} \mathrm{ C }_\beta=\frac{(\alpha+\beta)!}{\alpha!\beta!}$$ where $\alpha=m-1$ and $\beta=n-1$ with $m,n\ge2$.

Hence, $$N(m,n)\ge\frac{(\alpha+\beta)!}{\alpha!\beta!}=\frac{(m+n-2)!}{(m-1)!(n-1)!}$$