Mazes. & Coprime Grids

[hv at crypt.org]

Leroy Quet <qq-quet at mindspring.com> wrote:
:1) What is the array where a(m,n) = number of mazes in an m by n grid?
:(And,more specifically, what is the sequence where a(n) is the number of 
:mazes in an n-by-n grid?)

I've ignored the start/end points here, and therefore also all chances
to introduce a break in the outer wall: I'm counting grids where for
every pair of squares there is a unique path connecting them.

(Since by this definition all squares are equivalent, such a maze is a
solution for any choice of start/end squares, so additional complexities
can all be derived from this sequence.)

In this case, we have a(n,1) = 1 (trivially);

a(n,2) = [ 1, 4, 15, 56, 209, ... ] = A001353(n)
    = I A_2^(n-1) V_2 with:

I = [ 1 ], A_2 = [ 3, 2 ], V_2 = [ 1, 1 ]
    [ 0 ]        [ 1, 1 ]

a(n,3) = [ 1, 15, 192, 2409, ... ] (not in OEIS)
    = I A_3^(n-1) V_3 with:

    [ 1 ]        [ 8, 8, 3, 1 ]
I = [ 0 ], A_3 = [ 3, 5, 2, 0 ], V_3 = [ 1, 2, 1, 0 ]
    [ 0 ]        [ 1, 2, 1, 0 ]
    [ 0 ]        [ 4, 2, 2, 1 ]

... if I have calculated correctly.

In general, sum(V_n) = 2^(n-1) and dimension of A_n would be 2^(2n-3) if
the symmetric and always-zero entries were not collapsed. I may have
a go at writing a program to determine the matrices for higher n if time
permits.

Hugo