Mazes. & Coprime Grids

[hv at crypt.org]

hv at crypt.org wrote:
: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.
[...]
: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.

I'm working on a program which suggests the A_3 figures are wrong,
but it clearly isn't correct yet since the computed A_3 and A_4
give different results for a(3,4).

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

That's wrong too: the dimension of A_n would be A110(n) ("Bell numbers")
if the symmetric and always-zero entries are not collapsed.

In this context, the Bell partitions represent connected rows: for example
in A_3 and V_3 above, the columns represent partitions (aaa, aab, abc, aba)
respectively, so that for example "aba" represents a maze such as:

  +-+-...
  |
  + +-...
  | |
  + +-...
  |
  +-+-...

The always-zero entries are the partitions that cross themselves, so
the non-zero entries are precisely the non-crossing partitions, A108(n)
("Catalan numbers").

Defining a self-symmetric partition as one which yields itself when
reversed and normalised (eg "abacbc" reverses to "cbcaba", which is
normalised to "abacbc"), the number of self-symmetric non-crossing
partitions appears to be A1405(n) ("central binomial coefficients"),
and so D(n), the dimension of the simplified A_n matrices, is
(A108(n) + A1405(n)) / 2, which looks to be A85(n) ("number of
self-inverse permutations on n letters").

If these identifications with existing sequences are correct (can
anyone confirm?) they probably merit some new comments, particularly
the identity A85 = (A108 + A1405)/2, and its justification as
"non-crossing partitions counting symmetric pairs only once".

Hugo