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

1, 1, 28, 12600, 69699849, 4070693024640, 2484046163254367574, 15778915364062895746351104, 1040828457711477326843036225608036, 711789875509887224494712166194197254144000, 5040627715175514814159607456023227379139001458908168

Offset: 1

Author

Mike Koss, Nov 26 2021

Keywords

• nonn

Comments

The number of perfect mazes on an n X n grid of cells where rotations and reflections are not counted as distinct.

The sequence A007341 enumerates the same spanning trees or mazes but with duplicates due to symmetries of the square counted.

A lower bound for a(n) is the elements of A007341 divided by 8.

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

Examples

			While there are 192 mazes on a 3 X 3 grid, only a(3) = 28 are distinct mod rotations and reflections.
21 are asymmetric:
    _____     _____     _____     _____     _____     _____     _____     _____
   |     |   |     |   |     |   |    _|   |    _|   |    _|   |    _|   |    _|
   | | |_|   | |_| |   | |_|_|   | |   |   | |  _|   | |_  |   | |_  |   | |_ _|
   |_|_ _|   |_ _|_|   |_ _ _|   |_|_|_|   |_|_ _|   |_ _|_|   |_|_ _|   |_ _ _|
    _____     _____     _____     _____     _____     _____     _____     _____
   |    _|   |    _|   |    _|   |    _|   |    _|   |  _  |   |  _  |   |  _  |
   |_|   |   |_|  _|   |_|_  |   | | | |   | |_| |   |_  | |   |_  |_|   |_ _| |
   |_ _|_|   |_ _ _|   |_ _ _|   |_|_ _|   |_ _ _|   |_ _|_|   |_ _ _|   |_ _ _|
    _____     _____     _____     _____     _____
   |  _ _|   |  _ _|   |_   _|   |_   _|   |_   _|
   |_    |   |_   _|   |    _|   |  _  |   |   | |
   |_ _|_|   |_ _ _|   |_|_ _|   |_ _|_|   |_|_ _|
.
5 have 2-way symmetry:
    _____     _____     _____     _____     _____
   |     |   |     |   |    _|   |  _ _|   |_   _|
   | | | |   |_| |_|   |_| | |   |_ _  |   |     |
   |_|_|_|   |_ _ _|   |_ _ _|   |_ _ _|   |_|_|_|
.
2 have 4-way symmetry:
    _____     _____
   |_   _|   |_  | |
   |_   _|   |    _|
   |_ _ _|   |_|_ _|
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 1..40
• Andrew Howroyd, PARI program using Kirchhoff's Matrix Tree Theorem, 2021.
• Paul Kim, Intelligent Maze Generation, Doctoral dissertation, Ohio State University, 2019.
• Mike Koss, Maze Canvas, Open source unique maze generator, 2021.
• Eric Weisstein's World of Mathematics, Grid Graph
• Eric Weisstein's World of Mathematics, Spanning Tree
• Wikipedia, Burnside's_lemma, Kirchhoff's_theorem

Crossrefs

Cf. A007341, A116469.

Programs

PARI

\\ See link. - Andrew Howroyd, Nov 27 2021

Formula

a(n) ~ A007341(n) / 8; a(n) >= A007341(n) / 8.

a(2*n) = (A116469(2*n,2*n) + 4*n*A116469(2*n,n))/8. - Andrew Howroyd, Nov 27 2021

Extensions

Terms a(7) and beyond from Andrew Howroyd, Nov 27 2021