How many valid mazes of some size are there?

Solution 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.