A116469 -id:A116469 - cp's OEIS frontend

A338029 Square array T(n,k), n >= 1, k >= 1, read by antidiagonals, where T(n,k) is the number of spanning trees in the n X k king graph.

1, 1, 1, 1, 16, 1, 1, 192, 192, 1, 1, 2304, 17745, 2304, 1, 1, 27648, 1612127, 1612127, 27648, 1, 1, 331776, 146356224, 1064918960, 146356224, 331776, 1, 1, 3981312, 13286470095, 698512774464, 698512774464, 13286470095, 3981312, 1

Offset: 1

Seiichi Manyama, Nov 29 2020

			Square array T(n,k) begins:
  1,     1,         1,            1,                1, ...
  1,    16,       192,         2304,            27648, ...
  1,   192,     17745,      1612127,        146356224, ...
  1,  2304,   1612127,   1064918960,     698512774464, ...
  1, 27648, 146356224, 698512774464, 3271331573452800, ...

Eric Weisstein's World of Mathematics, King Graph
Eric Weisstein's World of Mathematics, Spanning Tree

Rows and columns 1..5 give A000012, A338100, A338532, A338617, A339257.
Main diagonal gives A288957.
Cf. A116469.

# Using graphillion
from graphillion import GraphSet
def make_nXk_king_graph(n, k):
    grids = []
    for i in range(1, k + 1):
        for j in range(1, n):
            grids.append((i + (j - 1) * k, i + j * k))
            if i < k:
                grids.append((i + (j - 1) * k, i + j * k + 1))
            if i > 1:
                grids.append((i + (j - 1) * k, i + j * k - 1))
    for i in range(1, k * n, k):
        for j in range(1, k):
            grids.append((i + j - 1, i + j))
    return grids
def A338029(n, k):
    if n == 1 or k == 1: return 1
    universe = make_nXk_king_graph(n, k)
    GraphSet.set_universe(universe)
    spanning_trees = GraphSet.trees(is_spanning=True)
    return spanning_trees.len()
print([A338029(j + 1, i - j + 1) for i in range(8) for j in range(i + 1)])

T(n,k) = T(k,n).

A360194 Array read by antidiagonals: T(m,n) is the number of acyclic spanning subgraphs in the grid graph P_m X P_n.

Original entry on oeis.org

1, 2, 2, 4, 15, 4, 8, 112, 112, 8, 16, 836, 3102, 836, 16, 32, 6240, 85818, 85818, 6240, 32, 64, 46576, 2373870, 8790016, 2373870, 46576, 64, 128, 347648, 65664106, 900013270, 900013270, 65664106, 347648, 128, 256, 2594880, 1816344222, 92146956300, 341008617408, 92146956300, 1816344222, 2594880, 256

Offset: 1

Andrew Howroyd, Jan 29 2023

Acyclic spanning subgraphs are also called spanning forests.

			Table starts:
========================================================
m\n|  1     2        3           4               5
---+----------------------------------------------------
1  |  1     2        4           8              16 ...
2  |  2    15      112         836            6240 ...
3  |  4   112     3102       85818         2373870 ...
4  |  8   836    85818     8790016       900013270 ...
5  | 16  6240  2373870   900013270    341008617408 ...
6  | 32 46576 65664106 92146956300 129187804977182 ...
   ...

Andrew Howroyd, Table of n, a(n) for n = 1..435
Eric Weisstein's World of Mathematics, Acyclic Graph
Eric Weisstein's World of Mathematics, Grid Graph

Rows 1..4 are A000079(n-1), A022026(n-1), A158450, A360195.
Main diagonal is A080691.
Cf. A116469 (spanning trees), A359993 (connected spanning subgraphs), A360202.

A348566 Triangle read by rows: T(m, n) is the number of symmetric recurrent sandpiles on an m X n grid (m >= 0, 0 <= n <= m).

Original entry on oeis.org

1, 1, 4, 1, 3, 2, 1, 14, 7, 128, 1, 11, 5, 71, 36, 1, 52, 18, 1358, 539, 43264, 1, 41, 13, 769, 281, 17753, 6728, 1, 194, 47, 14852, 4271, 1452866, 434657, 151519232, 1, 153, 34, 8449, 2245, 603126, 167089, 46069729, 12988816, 1, 724, 123, 163534, 34276, 49704772, 10894561, 16236962114, 3625549353, 5475450241024

Offset: 0

Andrey Zabolotskiy, Oct 22 2021

Terms of this triangle count recurrent sandpiles on rectangular grids that have vertical and horizontal symmetries. Terms of A348567 count recurrent sandpiles on square grids that also have diagonal symmetries.

			The triangle begins:
  1
  1  4
  1  3  2
  1 14  7  128
  1 11  5   71  36
  1 52 18 1358 539 43264
  1 41 13  769 281 17753 6728
...
See Fig. 9 of the paper by Florescu et al. for the T(4, 4) = 36 symmetric recurrent sandpiles on a 4x4 grid.

Laura Florescu, Daniela Morar, David Perkinson, Nicholas Salter and Tianyuan Xu, Sandpiles and Dominos, El. J. Comb., 22 (2015), P1.66.
Wikipedia, Abelian sandpile model

Cf. A348567, A187617, A187618, A103997, A256045, A116469.

T(2m, 2n) = A187617(m, n) = A187618(m, n). [Florescu et al., Theorem 15]
T(2m, 2n-1) = T(2n-1, 2m) = A103997(m, n). [Florescu et al., Theorem 18]
T(2m-1, 2n-1) = Product_{h=1..m, k=1..n} 4*(z(h, m) + z(k, n)) where z(k, n) = cos(Pi*(2k-1)/(4n)). [Florescu et al., Theorem 23]
A256045(m, n) divides T(m, n), T(m, n) divides A116469(m+1, n+1).
This triangle can obviously be extended to n > m as T(m, n) = T(n, m).

A334002 Number of spanning trees in the graph P_7 x P_n.

Original entry on oeis.org

1, 2911, 4768673, 7022359583, 10021992194369, 14143261515284447, 19872369301840986112, 27873182693625548898079, 39067130344394503972142977, 54740416599810921320592441119, 76692291658239649098972455530913, 107441842254735898225957962027174559, 150517199699838971875005120330439121217

Offset: 1

Seiichi Manyama, Apr 12 2020

nonn

Seiichi Manyama, Table of n, a(n) for n = 1..200
Vaclav Kotesovec, Generating function
Index entries for linear recurrences with constant coefficients, order 48.

Row m=7 of A116469.

a[n_] := Resultant[ChebyshevU[n - 1, x/2], ChebyshevU[6, (4 - x)/2], x]; Array[a, 13] (* Amiram Eldar, May 04 2021 *)

# Using graphillion
from graphillion import GraphSet
import graphillion.tutorial as tl
def A116469(n, k):
    if n == 1 or k == 1: return 1
    universe = tl.grid(n - 1, k - 1)
    GraphSet.set_universe(universe)
    spanning_trees = GraphSet.trees(is_spanning=True)
    return spanning_trees.len()
def A334002(n):
    return A116469(n, 7)
print([A334002(n) for n in range(1, 15)])

A334003 Number of spanning trees in the graph P_8 x P_n.

Original entry on oeis.org

1, 10864, 59817135, 289143013376, 1342421467113969, 6136973985625588560, 27873182693625548898079, 126231322912498539682594816, 570929651486775190858844600865, 2580716459066338161324165906475056, 11662182187505395757590783332919031887

Offset: 1

Seiichi Manyama, Apr 12 2020

nonn

Seiichi Manyama, Table of n, a(n) for n = 1..200
Index entries for linear recurrences with constant coefficients, order 128.

Row m=8 of A116469.

a[n_] := Resultant[ChebyshevU[n - 1, x/2], ChebyshevU[7, (4 - x)/2], x]; Array[a, 11] (* Amiram Eldar, May 04 2021 *)

{a(n) = polresultant(polchebyshev(n-1, 2, x/2), polchebyshev(7, 2, (4-x)/2))}

See Peter Bala's formula in A116469.

A334004 Number of spanning trees in the graph P_9 x P_n.

Original entry on oeis.org

1, 40545, 750331584, 11905151192865, 179796299139278305, 2662079368040434932480, 39067130344394503972142977, 570929651486775190858844600865, 8326627661691818545121844900397056, 121316352059447360262303173959408358625, 1766658737971934774798769007686932254154689

Offset: 1

Seiichi Manyama, Apr 12 2020

nonn

Seiichi Manyama, Table of n, a(n) for n = 1..200
Index entries for linear recurrences with constant coefficients, order 256.

Row m=9 of A116469.

a[n_] := Resultant[ChebyshevU[n - 1, x/2], ChebyshevU[8, (4 - x)/2], x]; Array[a, 11] (* Amiram Eldar, May 04 2021 *)

{a(n) = polresultant(polchebyshev(n-1, 2, x/2), polchebyshev(8, 2, (4-x)/2))}

# Using graphillion
from graphillion import GraphSet
import graphillion.tutorial as tl
def A116469(n, k):
    if n == 1 or k == 1: return 1
    universe = tl.grid(n - 1, k - 1)
    GraphSet.set_universe(universe)
    spanning_trees = GraphSet.trees(is_spanning=True)
    return spanning_trees.len()
def A334004(n):
    return A116469(n, 9)
print([A334004(n) for n in range(1, 10)])

A334005 Number of spanning trees in the graph P_10 x P_n.

Original entry on oeis.org

1, 151316, 9411975375, 490179860527896, 24080189412483072000, 1154617875754582889149500, 54740416599810921320592441119, 2580716459066338161324165906475056, 121316352059447360262303173959408358625, 5694319004079097795957215725765328371712000

Offset: 1

Seiichi Manyama, Apr 12 2020

nonn

Seiichi Manyama, Table of n, a(n) for n = 1..200

Row m=10 of A116469.

a[n_] := Resultant[ChebyshevU[n - 1, x/2], ChebyshevU[9, (4 - x)/2], x]; Array[a, 10] (* Amiram Eldar, May 04 2021 *)

{a(n) = polresultant(polchebyshev(n-1, 2, x/2), polchebyshev(9, 2, (4-x)/2))}

See Peter Bala's formula in A116469.

A340475 Square array T(n,k), n >= 0, k >= 0, read by antidiagonals, where T(n,k) = Product_{a=1..n} Product_{b=1..k} (4sin(aPi/(2n+1))^2 + 4sin(bPi/(2k+1))^2).

Original entry on oeis.org

1, 1, 1, 1, 6, 1, 1, 29, 29, 1, 1, 139, 500, 139, 1, 1, 666, 8329, 8329, 666, 1, 1, 3191, 138301, 463736, 138301, 3191, 1, 1, 15289, 2295701, 25543057, 25543057, 2295701, 15289, 1, 1, 73254, 38105729, 1404312491, 4614756624, 1404312491, 38105729, 73254, 1

Offset: 0

Seiichi Manyama, Jan 09 2021

			Square array begins:
  1,   1,      1,        1,          1, ...
  1,   6,     29,      139,        666, ...
  1,  29,    500,     8329,     138301, ...
  1, 139,   8329,   463736,   25543057, ...
  1, 666, 138301, 25543057, 4614756624, ...

Rows and columns 0..1 give A000012, A030221.
Main diagonal gives A127605.
Cf. A116469, A187617, A340476.

default(realprecision, 120);
{T(n, k) = round(prod(a=1, n, prod(b=1, k, 4*sin(a*Pi/(2*n+1))^2+4*sin(b*Pi/(2*k+1))^2)))}

T(n,k) = T(k,n).

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

Original entry on oeis.org

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

A375858 Array T(n,m) read by antidiagonals: In an n X m grid draw straight walls between cells, starting at a border, such that the resulting figure is connected and has only one-cell wide paths; T(n,m) is the number of solutions.

Original entry on oeis.org

1, 1, 1, 1, 4, 1, 1, 11, 11, 1, 1, 26, 56, 26, 1, 1, 57, 212, 212, 57, 1, 1, 120, 701, 1112, 701, 120, 1, 1, 247, 2179, 4793, 4793, 2179, 247, 1, 1, 502, 6600, 19082, 25000, 19082, 6600, 502, 1, 1, 1013, 19808, 74368, 116852, 116852, 74368, 19808, 1013, 1

Offset: 1

Andrew Howroyd, Aug 31 2024

See A375770 and A375817 for additional explanation and illustration of solutions.

This sequence counts a subset of the spanning trees enumerated in A116469.

			Array begins:
==================================================
n/m | 1   2    3     4      5       6        7 ...
----+---------------------------------------------
  1 | 1   1    1     1      1       1        1 ...
  2 | 1   4   11    26     57     120      247 ...
  3 | 1  11   56   212    701    2179     6600 ...
  4 | 1  26  212  1112   4793   19082    74368 ...
  5 | 1  57  701  4793  25000  116852   535776 ...
  6 | 1 120 2179 19082 116852  607712  3048668 ...
  7 | 1 247 6600 74368 535776 3048668 15918280 ...
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..1275 (first 50 antidiagonals)

Main diagonal is A375817.

Cf. A116469, A375770, A375859, A375860, A375861.

\\ A375858(n,m) defined in PARI link in A375770.

T(n,m) = T(m,n).

cp's OEIS Frontend

A338029 Square array T(n,k), n >= 1, k >= 1, read by antidiagonals, where T(n,k) is the number of spanning trees in the n X k king graph.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Python

Formula

A360194 Array read by antidiagonals: T(m,n) is the number of acyclic spanning subgraphs in the grid graph P_m X P_n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A348566 Triangle read by rows: T(m, n) is the number of symmetric recurrent sandpiles on an m X n grid (m >= 0, 0 <= n <= m).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A334002 Number of spanning trees in the graph P_7 x P_n.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Python

A334003 Number of spanning trees in the graph P_8 x P_n.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A334004 Number of spanning trees in the graph P_9 x P_n.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Python

A334005 Number of spanning trees in the graph P_10 x P_n.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A340475 Square array T(n,k), n >= 0, k >= 0, read by antidiagonals, where T(n,k) = Product_{a=1..n} Product_{b=1..k} (4*sin(a*Pi/(2*n+1))^2 + 4*sin(b*Pi/(2*k+1))^2).

Views

Author

Keywords

Examples

Crossrefs

Programs

PARI

Formula

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

Views

Author

Keywords

A340475 Square array T(n,k), n >= 0, k >= 0, read by antidiagonals, where T(n,k) = Product_{a=1..n} Product_{b=1..k} (4sin(aPi/(2n+1))^2 + 4sin(bPi/(2k+1))^2).