Mazes. & Coprime Grids

[hv at crypt.org]

(For Neil) Here is the tabulated sequence:

%I A000001
%S A000001 1,1,1,1,4,1,1,15,15,1,1,56,192,56,1,1,209,2415,2415,209,1,1,780
%T A000001 30305,100352,30305,780,1,1,2911,380160,4140081,4140081,380160,2911
%U A000001 1,1,10864,4768673,170537640,557568000,170537640,4768673,10864,1,1
%N A000001 Number of spanning trees in an m x n grid read by antidiagonals
%C A000001 This is the number of ways the points in an m x n grid can be connected to their orthogonal neighbours such that for any pair of points there is precisely one path connecting them
%C A000001 a(n,n) = A007341(n)
%e A000001 a(2,2) = 4, since we must have exactly 3 of the 4 possible connections: if we have all 4 there are multiple paths between points; if we have fewer some points will be isolated from others.
%O A000001 1,5
%Y A000001 Cf A007341
%K A000001 nonn,tabl
%A A000001 Calculated by Hugo van der Sanden (hv at crypt.org) after a suggestion from Leroy Quet, Mar 20 2006.

A007341 should also gain a return crossreference to this table.

More commentary below.

Earlier I 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.

Corrected A_3 is:
      [ 8, 8, 3, 1 ]
A_3 = [ 3, 5, 2, 0 ]
      [ 1, 2, 1, 0 ]
      [ 4, 4, 2, 1 ]

Results for a(1..9, 1..11):
a(1, n) => 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1
a(2, n) => 1, 4, 15, 56, 209, 780, 2911, 10864, 40545, 151316, 564719
a(3, n) => 1, 15, 192, 2415, 30305, 380160, 4768673, 59817135, 750331584,
  9411975375, 118061508289
a(4, n) => 1, 56, 2415, 100352, 4140081, 170537640, 7022359583, 289143013376,
  11905151192865, 490179860527896, 20182531537581071
a(5, n) => 1, 209, 30305, 4140081, 557568000, 74795194705, 10021992194369,
  1342421467113969, 179796299139278305, 24080189412483072000,
  3225041354570508955681
a(6, n) => 1, 780, 380160, 170537640, 74795194705, 32565539635200,
  14143261515284447, 6136973985625588560, 2662079368040434932480,
  1154617875754582889149500, 500769437567956298239402223
a(7, n) => 1, 2911, 4768673, 7022359583, 10021992194369, 14143261515284447,
  19872369301840986112, 27873182693625548898079, 39067130344394503972142977,
  54740416599810921320592441119, 76692291658239649098972455530913
a(8, n) => 1, 10864, 59817135, 289143013376, 1342421467113969,
  6136973985625588560, 27873182693625548898079, 126231322912498539682594816,
  570929651486775190858844600865, 2580716459066338161324165906475056,
  11662182187505395757590783332919031887
a(9, n) => 1, 40545, 750331584, 11905151192865, 179796299139278305,
  2662079368040434932480, 39067130344394503972142977,
  570929651486775190858844600865, 8326627661691818545121844900397056,
  121316352059447360262303173959408358625,
  1766658737971934774798769007686932254154689

So a(n, n) resolves to:
  1, 4, 192, 100352, 557568000, 32565539635200, 19872369301840986112,
  126231322912498539682594816, 8326627661691818545121844900397056
which is A7341(n), which caused me to look up what a spanning tree was.
Since these mazes are clearly identical to spanning trees, matching
A7341(n) correctly gives me confidence in the correctness of the new
results.

That last number, a(9, 11), factorises as:
  89.109.199.683.2089.2267.3191.68597.293149.380557.11585969
I note that each factor is +/-1 mod(9) and mod(11), but I don't know
why it should be so: there are interesting research possibilities here.
(Since A7341(n) shows a formula for a(n,n) someone may already have
done that research.)

My program calculates the complete d x d matrix A_n, where d = A85(n),
then uses it to calculate the sequence values; with this approach I don't
have the resources to find A_10 (with d=9496), and therefore cannot
get to a(10, 10) or beyond.

The raw matrices up to A_9 (21MB) and/or the program I used to calculate them
(4.5KB) are available on request.

Hugo