Mike Koss - cp's OEIS frontend

User: Mike Koss

Mike Koss has authored 2 sequences.

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

Mike Koss, Nov 26 2021

nonn

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

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

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

Cf. A007341, A116469.

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

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

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

A344538 Lexicographically earliest sequence such that |a(n+1)-a(n)| is a cube > 1 and no number occurs twice; a(0) = 0.

Original entry on oeis.org

0, 8, 16, 24, 32, 5, 13, 21, 29, 2, 10, 18, 26, 34, 7, 15, 23, 31, 4, 12, 20, 28, 1, 9, 17, 25, 33, 6, 14, 22, 30, 3, 11, 19, 27, 35, 43, 51, 59, 67, 40, 48, 56, 64, 37, 45, 53, 61, 69, 42, 50, 58, 66, 39, 47, 55, 63, 36, 44, 52, 60, 68, 41, 49, 57, 65, 38

Offset: 0

Mike Koss, May 22 2021

The difference between successive terms, a(n+1)-a(n), is either +8 or -27. This sequence is a permutation of the nonnegative integers (with no "gaps").

Mike Koss, Derivation and proof.
Index entries for linear recurrences with constant coefficients, signature (2,-1,0,0,0,0,-1,2,-1,0,0,0,0,-1,2,-1,0,0,0,0,-1,2,-1,0,0,0,0,-1,2,-1).
Index entries for sequences that are permutations of the nonnegative integers

Cf. A277616.

a[0]=0;a[n_]:=a[n]=(k=1;While[!IntegerQ[s=Abs[k-a[n-1]]^(1/3)]||s==1||MemberQ[Array[a,n-1],k],k++];k);Array[a,100,0] (* Giorgos Kalogeropoulos, May 27 2021 *)

a(n+35) = a(n) + 35 for all n.

a(n) = 2*a(n-1) - a(n-2) - a(n-7) + 2*a(n-8) - a(n-9) - a(n-14) + 2*a(n-15) - a(n-16) - a(n-21) + 2*a(n-22) - a(n-23) - a(n-28) + 2*a(n-29) - a(n-30) for n > 29. - Stefano Spezia, May 23 2021

cp's OEIS Frontend

User: Mike Koss

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions