cp's OEIS Frontend

A349718 Number of spanning trees in the n X n grid graph where rotations and reflections are not counted as distinct.

%I A349718 #35 Feb 16 2025 08:34:02
%S A349718 1,1,28,12600,69699849,4070693024640,2484046163254367574,
%T A349718 15778915364062895746351104,1040828457711477326843036225608036,
%U A349718 711789875509887224494712166194197254144000,5040627715175514814159607456023227379139001458908168
%N A349718 Number of spanning trees in the n X n grid graph where rotations and reflections are not counted as distinct.
%C A349718 The number of perfect mazes on an n X n grid of cells where rotations and reflections are not counted as distinct.
%C A349718 The sequence A007341 enumerates the same spanning trees or mazes but with duplicates due to symmetries of the square counted.
%C A349718 A lower bound for a(n) is the elements of A007341 divided by 8.
%C A349718 Terms can be computed using Burnside's lemma and Kirchhoff's matrix tree theorem applied to various graphs. See the PARI program link for technical details. - _Andrew Howroyd_, Nov 27 2021
%H A349718 Andrew Howroyd, <a href="/A349718/b349718.txt">Table of n, a(n) for n = 1..40</a>
%H A349718 Andrew Howroyd, <a href="/A349718/a349718.txt">PARI program using Kirchhoff's Matrix Tree Theorem</a>, 2021.
%H A349718 Paul Kim, <a href="http://rave.ohiolink.edu/etdc/view?acc_num=osu1563286393237089">Intelligent Maze Generation</a>, Doctoral dissertation, Ohio State University, 2019.
%H A349718 Mike Koss, <a href="https://github.com/mckoss/maze-canvas">Maze Canvas</a>, Open source unique maze generator, 2021.
%H A349718 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/GridGraph.html">Grid Graph</a>
%H A349718 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/SpanningTree.html">Spanning Tree</a>
%H A349718 Wikipedia, <a href="https://en.wikipedia.org/wiki/Burnside%27s_lemma">Burnside's_lemma</a>, <a href="https://en.wikipedia.org/wiki/Kirchhoff%27s_theorem">Kirchhoff's_theorem</a>
%F A349718 a(n) ~ A007341(n) / 8; a(n) >= A007341(n) / 8.
%F A349718 a(2*n) = (A116469(2*n,2*n) + 4*n*A116469(2*n,n))/8. - _Andrew Howroyd_, Nov 27 2021
%e A349718 While there are 192 mazes on a 3 X 3 grid, only a(3) = 28 are distinct mod rotations and reflections.
%e A349718 21 are asymmetric:
%e A349718     _____     _____     _____     _____     _____     _____     _____     _____
%e A349718    |     |   |     |   |     |   |    _|   |    _|   |    _|   |    _|   |    _|
%e A349718    | | |_|   | |_| |   | |_|_|   | |   |   | |  _|   | |_  |   | |_  |   | |_ _|
%e A349718    |_|_ _|   |_ _|_|   |_ _ _|   |_|_|_|   |_|_ _|   |_ _|_|   |_|_ _|   |_ _ _|
%e A349718     _____     _____     _____     _____     _____     _____     _____     _____
%e A349718    |    _|   |    _|   |    _|   |    _|   |    _|   |  _  |   |  _  |   |  _  |
%e A349718    |_|   |   |_|  _|   |_|_  |   | | | |   | |_| |   |_  | |   |_  |_|   |_ _| |
%e A349718    |_ _|_|   |_ _ _|   |_ _ _|   |_|_ _|   |_ _ _|   |_ _|_|   |_ _ _|   |_ _ _|
%e A349718     _____     _____     _____     _____     _____
%e A349718    |  _ _|   |  _ _|   |_   _|   |_   _|   |_   _|
%e A349718    |_    |   |_   _|   |    _|   |  _  |   |   | |
%e A349718    |_ _|_|   |_ _ _|   |_|_ _|   |_ _|_|   |_|_ _|
%e A349718 .
%e A349718 5 have 2-way symmetry:
%e A349718     _____     _____     _____     _____     _____
%e A349718    |     |   |     |   |    _|   |  _ _|   |_   _|
%e A349718    | | | |   |_| |_|   |_| | |   |_ _  |   |     |
%e A349718    |_|_|_|   |_ _ _|   |_ _ _|   |_ _ _|   |_|_|_|
%e A349718 .
%e A349718 2 have 4-way symmetry:
%e A349718     _____     _____
%e A349718    |_   _|   |_  | |
%e A349718    |_   _|   |    _|
%e A349718    |_ _ _|   |_|_ _|
%o A349718 (PARI) \\ See link. - _Andrew Howroyd_, Nov 27 2021
%Y A349718 Cf. A007341, A116469.
%K A349718 nonn
%O A349718 1,3
%A A349718 _Mike Koss_, Nov 26 2021
%E A349718 Terms a(7) and beyond from _Andrew Howroyd_, Nov 27 2021