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,3

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

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

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

Example

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:
    _____     _____
   |_   _|   |_  | |
   |_   _|   |    _|
   |_ _ _|   |_|_ _|

Prog

(PARI) \\ See link. - Andrew Howroyd, Nov 27 2021

Crossrefs

Cf. A007341, A116469.

Sequence in context: A221691 A159415 A209177 * A134772 A085408 A159419

Adjacent sequences: A349715 A349716 A349717 * A349719 A349720 A349721

Keyword

nonn

Author

Mike Koss, Nov 26 2021

Extensions

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

Status

approved