A007341 -id:A007341 - cp's OEIS frontend

A340176 Number of spanning trees in the halved Aztec diamond HMD_n.

1, 1, 4, 208, 121856, 772189440, 51989627289600, 36837279603595907072, 273129993621426778551615488, 21114078836429317912110529666154496, 16975032309392309949804839529585109326888960

Offset: 0

Seiichi Manyama, Dec 31 2020

nonn

                                  *---*
                                  |   |
              *---*           *---*---*---*
              |   |           |   |   |   |
  *---*   *---*---*---*   *---*---*---*---*---*
  HMD_1       HMD_2               HMD_3
-------------------------------------------------
              *---*
              |   |
          *---*---*---*
          |   |   |   |
      *---*---*---*---*---*
      |   |   |   |   |   |
  *---*---*---*---*---*---*---*
              HMD_4

			a(2) = 4;
      *   *           *---*           *---*           *---*
      |   |               |           |               |   |
  *---*---*---*   *---*---*---*   *---*---*---*   *---*   *---*

Seiichi Manyama, Table of n, a(n) for n = 0..45
Mihai Ciucu, Symmetry classes of spanning trees of Aztec diamonds and perfect matchings of odd squares with a unit hole, arXiv:0710.4500 [math.CO], 2007. See Corollary 3.6.
Wikipedia, Chebyshev polynomials
Wikipedia, Resultant

Cf. A007341, A007725, A007726, A334088, A334089, A340139, A340166, A340185 (halved Aztec diamond HOD_n).

default(realprecision, 120);
{a(n) = round(prod(j=1, 2*n-1, prod(k=j+1, 2*n-1-j, 4-4*cos(j*Pi/(2*n))*cos(k*Pi/(2*n)))))}

{a007341(n) = polresultant(polchebyshev(n-1, 2, x/2), polchebyshev(n-1, 2, (4-x)/2))};
{a334088(n) = sqrtint(polresultant(polchebyshev(2*n, 1, x/2), polchebyshev(2*n, 1, I*x/2)))};
{a(n) = if(n==0, 1, sqrtint(a007341(n)*a334088(n)/n))}

default(realprecision, 120);
{a(n) = if(n==0, 1, round(4^((n-1)^2)*prod(j=1, n-1, prod(k=j+1, n-1, 1-(cos(j*Pi/(2*n))*cos(k*Pi/(2*n)))^2))))} \\ Seiichi Manyama, Jan 02 2021

# Using graphillion
from graphillion import GraphSet
def make_HMD(n):
    s = 1
    grids = []
    for i in range(2 * n, 0, -2):
        for j in range(i - 2):
            a, b, c = s + j, s + j + 1, s + i + j
            grids.extend([(a, b), (b, c)])
        grids.append((s + i - 2, s + i - 1))
        s += i
    return grids
def A340176(n):
    if n == 0: return 1
    universe = make_HMD(n)
    GraphSet.set_universe(universe)
    spanning_trees = GraphSet.trees(is_spanning=True)
    return spanning_trees.len()
print([A340176(n) for n in range(7)])

a(n) = Product_{1<=j

a(n) = 2^(n-1) * A007726(n) * A334089(n) = sqrt(A007341(n) * A334088(n) / n) for n > 0.

a(n) = 4^(n-1) * A340139(n) = 4^((n-1)^2) * Product_{1<=j 0. - Seiichi Manyama, Jan 02 2021

a(n) ~ sqrt(Gamma(1/4)) * exp(4*G*n^2/Pi) / (Pi^(3/8) * n^(3/4) * 2^(n - 1/4) * (1 + sqrt(2))^n), where G is Catalan's constant A006752. - Vaclav Kotesovec, Jan 05 2021

A359992 Number of connected spanning subgraphs in the n X n grid graph.

Original entry on oeis.org

1, 5, 431, 555195, 10286937043, 2692324030864335, 9852929684161379901975, 501079193080617800221189943995, 352690403996687922642590703716802346343, 3426297680513758764075706102615040790667832304415, 458508006189588425325361635000918336126387961057365005349963

Offset: 1

Andrew Howroyd, Jan 28 2023

nonn

For n > 1, a(n) is the number of connected edge covers in the n X n grid graph.

			The a(2) = 5 connected spanning subgraphs are the following subgraphs and their rotations and reflections.
   o---o   o---o
   |       |   |
   o---o   o---o

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

Main diagonal of A359993.

Cf. A007341, A053765, A080691, A286913, A359989.

a(n) = A053765(n) - A359989(n).

A067518 Number of spanning trees in n X n X 2 grid.

Original entry on oeis.org

1, 384, 49766400, 2200248344641536, 32699232783861202944000000, 161655300770215803222365206216704000000, 264237966861625003904099008804894577790426446838104064

Offset: 1

Sharon Sela (sharonsela(AT)hotmail.com), Jun 08 2002

nonn

W.-J. Tzeng and F. Y. Wu, Spanning Trees on Hypercubic Lattices and Non-orientable Surfaces, arXiv:cond-mat/0001408 [cond-mat.stat-mech], 2002.

Cf. A071763, A007341, A340396.

a[n_] := 2^(2*n^2 - 2)/n^2*Product[If[n1+n2+n3 > 0, 3 - Cos[Pi*n1/n] - Cos[Pi*n2/n] - Cos[Pi*n3/2], 1], {n1, 0, n-1}, {n2, 0, n-1}, {n3, 0, 1}];
Table[a[n] // Round, {n, 1, 7}] (* Jean-François Alcover, Feb 18 2019 *)

a(n) = 2^(2*n^2-2) / n^2 * Product_{n1=0..n-1, n2=0..n-1, n3=0..1, n1+n2+n3>0} (3 - cos(Pi*n1/n) - cos(Pi*n2/n) - cos(Pi*n3/2)).

a(n) ~ c * d^n * 2^(n^2) * exp(4*n^2*(G/Pi + m/Pi^2)) / sqrt(n), where m = Integral_{x=0..Pi/2, y=0..Pi/2} log(1 + 2*sin(x)^2 + 2*sin(y)^2) dy dx = A340422 = 2.5516988064039243609935616786056293143254369265492957275912213393835172..., d = (2*sqrt(2)-3)*(2+sqrt(3))*(sqrt(15)-4) = 0.08133113706589390743806107..., c = 5^(1/4) * Gamma(1/4) / (sqrt(3) * (2*Pi)^(3/4)) = 0.788729432659299631982768... and G is Catalan's constant A006752. Equivalently, m = Pi * Integral_{x=0..Pi/2} (log(1 + sqrt(1 + 2/(3 - 2*cos(x)^2))) + log((1 + 2*sin(x)^2)/4)/2) dx. - Vaclav Kotesovec, Jan 06 2021, updated Mar 17 2024

More terms from André Pönitz (poenitz(AT)htwm.de), Jun 11 2003

A340183 a(n) = Product_{1<=j,k,m<=n-1} (4sin(jPi/(2n))^2 + 4sin(kPi/(2n))^2 + 4sin(mPi/(2*n))^2).

Original entry on oeis.org

1, 6, 1157625, 170875128460147163136, 448524809573174705684873233798538664686384705625

Offset: 1

Seiichi Manyama, Dec 31 2020

nonn

(a(n)/(n*3^(n-1)))^(1/3) is an integer.

Cf. A007341, A124647, A340181, A340182.

Round[Table[2^((n-1)^3)* Product[3 - Cos[j*Pi/n] - Cos[k*Pi/n] - Cos[m*Pi/n], {j, 1, n-1}, {k, 1, n-1}, {m, 1, n-1}], {n, 1, 5}]] (* Vaclav Kotesovec, Jan 04 2021 *)

default(realprecision, 500);
{a(n) = round(prod(j=1, n-1, prod(k=1, n-1, prod(m=1, n-1, 4*sin(j*Pi/(2*n))^2+4*sin(k*Pi/(2*n))^2+4*sin(m*Pi/(2*n))^2))))}

a(n) = Product_{1<=i,j,k<=n-1} (4*f(i*Pi/(2*n))^2 + 4*g(j*Pi/(2*n))^2 + 4*h(k*Pi/(2*n))^2), where f(x), g(x) and h(x) are sin(x) or cos(x).

Limit_{n->infinity} a(n)^(1/n^3) = exp(8*A340322/Pi^3). - Vaclav Kotesovec, Jan 05 2021

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

A351379 The number of grains of sand in the identity element for the 3D sandpile group on an n X n X n cubic grid.

Original entry on oeis.org

24, 54, 288, 480, 744, 1062, 1968, 2616, 3480, 4398, 6000, 7344, 9744, 11628, 14256, 16632, 20376, 23436, 27312, 30984, 37104, 41652, 47424, 52776, 60432, 66636, 75552, 82752, 93288, 101676, 112488, 121968, 135768, 146436, 163032, 175182, 191256, 204690, 221784, 236646, 257400, 273738, 296784

Offset: 2

Scott R. Shannon and Zach J. Shannon, Feb 09 2022

nonn

The 3D sandpile model follows the same rules as the 2D model except that cells topple and transfer one grain of sand to their six nearest neighbors when the cell contains 6 or more grains. Cells containing 0 to 5 grains are stable.

See A307652 for details of the sandpile group identity.

			a(2) = 2 X 2 X 2 grid. Identity:
       Layer 1: | 3 3 |  Layer 2: | 3 3 |
                | 3 3 |           | 3 3 |  = 24 grains.
a(3) = 3 X 3 X 3 grid. Identity:
       Layer 1: | 3 2 3 |  Layer 2: | 2 1 2 |  Layer 3: | 3 2 3 |
                | 2 1 2 |           | 1 0 1 |           | 2 1 2 |
                | 3 2 3 |           | 2 1 2 |           | 3 2 3 |  = 54 grains.

Noah Doman, The Identity of the Abelian Sandpile Group, Bachelor Thesis, University of Groningen, January 2020.
Luis David Garcia-Puente and Brady Haran, Sandpiles, Numberphile video, YouTube.com, Jan. 13, 2017.
Yvan Le Borgne and Dominique Rossin, On the identity of the sandpile group, Discrete Mathematics, 256 (2002) 775-790.
Scott R. Shannon, Middle layer of the 100x100x100 identity. This contains 3486864 grains. For this and other images, white=0, red=1, green=2, blue=3, violet=4, yellow=5 grains per cell.
Scott R. Shannon, Top layer of the 100x100x100 identity.
Scott R. Shannon, Middle layer of the 101x101x101 identity. Similarly to the 2D sandpile model, when n is odd the middle layers have a cross-like pattern.
Zach J. Shannon, 3D image of the full 80x80x80 identity. The same colors as above are used except cells with no grains are shown as vacancies, not white.
Zach J. Shannon, 3D image of half the 80x80x80 identity.
Zach J. Shannon, 3D image of half the 80x80x80 identity without the cells containing 5 grains.
Zach J. Shannon, 3D image of half the 80x80x80 identity showing only the cells containing 5 grains.

Cf. A307652 (square grid), A259013, A180230, A300006, A007341.

Identity element = ([10n] - ([10n])*)* , where [10n] is the all 10's grid of size n X n X n, and (x)* represents the topple stabilization of the grid x.

The sequence is approximately fitted by the cubic a(n) ~ 3.48*n^3, where 3.48 corresponds to the approximate grains-per-cube density of the identity element configurations.

A189002 Number of domino tilings of the n X n grid with upper left corner removed iff n is odd.

Original entry on oeis.org

1, 1, 2, 4, 36, 192, 6728, 100352, 12988816, 557568000, 258584046368, 32565539635200, 53060477521960000, 19872369301840986112, 112202208776036178000000, 126231322912498539682594816, 2444888770250892795802079170816, 8326627661691818545121844900397056

Offset: 0

Alois P. Heinz, Apr 15 2011

nonn

			a(3) = 4 because there are 4 domino tilings of the 3 X 3 grid with upper left corner removed:
  . .___.  . .___.  . .___.  . .___.
  ._|___|  ._|___|  ._| | |  ._|___|
  | |___|  | | | |  | |_|_|  |___| |
  |_|___|  |_|_|_|  |_|___|  |___|_|

Alois P. Heinz, Table of n, a(n) for n = 0..50
Index entries for sequences related to dominoes

Main diagonal of A189006.

Bisection gives: A004003 (even part), A007341 (odd part).

A[1, 1] = 1;
A[m_, n_] := A[m, n] = Module[{i, j, s, t, M}, Which[m == 0 || n == 0, 1, m < n, A[n, m], True, s = Mod[n*m, 2]; M[i_, j_] /; j < i := -M[j, i]; M[, ] = 0; For[i = 1, i <= n, i++, For[j = 1, j <= m, j++, t = (i - 1)*m + j - s; If[i > 1 || j > 1 || s == 0, If[j < m, M[t, t + 1] = 1]; If[i < n, M[t, t + m] = 1 - 2*Mod[j, 2]]]]]; Sqrt[Det[Array[M, {n*m - s, n*m - s}]] ]]];
a[n_] := A[n, n];
a /@ Range[0, 17] (* Jean-François Alcover, Feb 27 2020, after Alois P. Heinz in A189006 *)

a(n) = A189006(n,n).

A307097 Number of configurations in the repeating cycle of the sandpile model in a bounded square of size 2n+1.

Original entry on oeis.org

2, 4, 4, 4, 6, 6, 8, 6, 10, 18, 26, 10, 10, 8, 12, 30, 8, 32, 14, 32, 52, 26, 60, 52, 34, 74, 14, 80, 36, 38, 24, 54, 26, 30, 36, 58, 22, 14, 26, 36, 38, 20, 36, 60, 24, 24, 18, 14, 24, 34, 70, 104, 48, 56, 36, 50, 50, 48, 152, 28, 110, 30, 172, 64, 104, 158, 150, 60, 36, 186, 52, 50

Offset: 1

Scott R. Shannon, Mar 24 2019

nonn

The Abelian sandpile model considers the behavior of grains of sand on a square grid when a square topples sand to its nearest neighbors when the number of grains in the square is greater than or equal to 4, where 4 is the number of nearest neighbors. If the grid is instead bounded by a square box then it is natural to extend this rule so that squares on the border also topple when they contain more or the same number of grains as the number of their nearest neighbors, i.e., 2 for corner squares, 3 for edge squares. Unlike the standard Abelian sandpile model on a finite grid, the square grid in this model does not lose sand, and assuming one keeps adding sand to the grid after each topple stabilization, eventually a critical number of grains will be added such that the resulting configurations will cycle. This sequence {a(n)} is the number of configurations in the cycle, for the sandpile model bounded by a square of size 2n+1, assuming the square grid starts with no sand and sand is continuously added to the center square until a cycle first occurs. As the toppling in a given area will repeat indefinitely, once the repeating cycle state is reached, one cannot topple the unstable squares in any random order and reach a stable configuration. To avoid such issues all squares are toppled simultaneously.

			For n=1 the square size is 2*1+1 = 3. The number of sand grains in each square is shown below, after the addition of 4, 8 and 12 grains to the central square:
.
   After 4         After 8         After 12
+---+---+---+   +---+---+---+   +---+---+---+
| 0 | 1 | 0 |   | 0 | 2 | 0 |   | 0 | 3 | 0 |
+---+---+---+   +---+---+---+   +---+---+---+
| 1 | 0 | 1 |   | 2 | 0 | 2 |   | 3 | 0 | 3 |
+---+---+---+   +---+---+---+   +---+---+---+
| 0 | 1 | 0 |   | 0 | 2 | 0 |   | 0 | 3 | 0 |
+---+---+---+   +---+---+---+   +---+---+---+
.
The edge squares now contain 3 grains, which means they are unstable as 3 equals their nearest neighbor count. This configuration thus topples to:
.
+---+---+---+
| 2 | 0 | 2 |
+---+---+---+
| 0 | 4 | 0 |
+---+---+---+
| 2 | 0 | 2 |
+---+---+---+
.
The central square is again unstable, as are the four corner squares as they contain 2 grains. This configuration topples to:
.
+---+---+---+
| 0 | 3 | 0 |
+---+---+---+
| 3 | 0 | 3 |
+---+---+---+
| 0 | 3 | 0 |
+---+---+---+
.
This is the same as the configuration after 12 grains above. These last two configurations cycle forever, thus a(1) = 2.

Scott R. Shannon, Table of n, a(n) for n = 1..500
Per Bak, Chao Tang, Kurt Wiesenfeld, Self-organized criticality: An explanation of the 1/f noise, Phys. Rev. Lett. 59 (1987), 381-384.
Laura Florescu, Daniela Morar, David Perkinson, Nicholas Salter, and Tianyuan Xu, Sandpiles and Dominos, Electronic Journal of Combinatorics, Volume 22(1), 2015.
Luis David Garcia-Puente and Brady Haran, Sandpiles, Numberphile video, YouTube.com, Jan. 13, 2017.
L. Levine, W. Pegden, C. K. Smart, Apollonian structure in the Abelian sandpile, Geom. Funct. Anal. (2016) 26:306.
Scott R. Shannon, Cycle for square of size 2*2+1 = 5. This cycle of 4 configurations is reached after the addition of 40 grains of sand. This is the first square size in a sequence of three sizes that have a cycle of 4: a(2), a(3), a(4). For this, and other images, white=0, yellow=1, green=2, blue=3, red=4, black>=5 grains.
Scott R. Shannon, Cycle for square of size 2*3+1 = 7. The second square to have a cycle of 4. This is reached after the addition of 100 grains.
Scott R. Shannon, Cycle for square of size 2*4+1 = 9. The third square to have a cycle of 4. This is reached after the addition of 160 grains.
Scott R. Shannon, Complete growth and cycle for square of size 2*7+1 = 15. This shows the addition of 468 grains (each image is pre-topple after the central square has regained 4 grains) followed by each iteration for the resulting 8-cycle configuration. The cycle is shown ten times.
Wikipedia, Abelian Sandpile Model.

Cf. A259013, A180230, A056219, A307652.

Cf. A007341 (order of the sandpile group of the (n-1)X(n-1) grid graph).

A351994 Number of spanning trees in a hexagon of size n in the triangular grid.

Original entry on oeis.org

1, 320, 2300606464, 289899537900576358400, 614482906548854364363387716704247808, 21564742087547836976004856537464240189331001616154755072, 12433415382338420812828401445037903120443542018197863908895102595928462876835840

Offset: 0

Peter Kagey, Feb 28 2022

nonn

The hexagon of size n in the triangular grid has A003215(n) vertices.

Peter Kagey, Image of one of the a(4) = 614482906548854364363387716704247808 spanning trees of size 4.

Cf. A007341 (square in square grid), A116469 (rectangle in square grid), A174579 (triangle in triangular grid), A351888 (triangle in hexagonal grid), A352022 (hexagon in hexagonal grid).

Previous Showing 11-20 of 23 results. Next

cp's OEIS Frontend

A229728 Decimal expansion of the square of the constant A130834.

Views

Author

Keywords

Examples

References

Crossrefs

Programs

Mathematica

PARI

Formula

A340176 Number of spanning trees in the halved Aztec diamond HMD_n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

PARI

PARI

Python

Formula

A359992 Number of connected spanning subgraphs in the n X n grid graph.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A067518 Number of spanning trees in n X n X 2 grid.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A340183 a(n) = Product_{1<=j,k,m<=n-1} (4*sin(j*Pi/(2*n))^2 + 4*sin(k*Pi/(2*n))^2 + 4*sin(m*Pi/(2*n))^2).

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

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

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A351379 The number of grains of sand in the identity element for the 3D sandpile group on an n X n X n cubic grid.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A189002 Number of domino tilings of the n X n grid with upper left corner removed iff n is odd.

Views

Author

Keywords

A340183 a(n) = Product_{1<=j,k,m<=n-1} (4sin(jPi/(2n))^2 + 4sin(kPi/(2n))^2 + 4sin(mPi/(2*n))^2).