A007726 -id:A007726 - cp's OEIS frontend

A007341 Number of spanning trees in n X n grid.

1, 4, 192, 100352, 557568000, 32565539635200, 19872369301840986112, 126231322912498539682594816, 8326627661691818545121844900397056, 5694319004079097795957215725765328371712000, 40325021721404118513276859513497679249183623593590784, 2954540993952788006228764987084443226815814190099484786032640000

Offset: 1

N. J. A. Sloane

Kreweras calls this the complexity of the n X n grid.
a(n) is the number of perfect mazes made from a grid of n X n cells. - Leroy Quet, Sep 08 2007
Also number of domino tilings of the (2n-1) X (2n-1) square with upper left corner removed.  For n=2 the 4 domino tilings of the 3 X 3 square with upper left corner removed are:
. ._. . ._. . ._. . ._.
.|__| .|__| .| | | .|___|
| |_| | | | | | ||| |_| |
||__| |||_| ||__| |_|_| - Alois P. Heinz, Apr 15 2011
Indeed, more is true. Let L denote the (2*n - 1) X (2*n - 1) square lattice graph with vertices (i,j), 1 <= i,j <= 2*n-1. Call a vertex (i,j) odd if both coordinates i and j are odd. Then there is a bijection between the set of spanning trees on the square n X n grid and the set of domino tilings of L with an odd boundary point removed. See Tzeng and Wu, 2002. This is a divisibility sequence, i.e., if n divides m then a(n) divides a(m). - Peter Bala, Apr 29 2014
Also, a(n) is the order of the sandpile group of the (n-1)X(n-1) grid graph. This is because the n X n grid is dual to (n-1)X(n-1) grid + sink vertex, and the latter is related to the sandpiles by the burning bijection. See Járai, Sec. 4.1, or Redig, Sec. 2.2. In M. F. Hasler's comment below, index n refers to the size of the grid underlying the sandpile. - Andrey Zabolotskiy, Mar 27 2018
From M. F. Hasler, Mar 07 2018: (Start)
The sandpile addition (+) of two n X n matrices is defined as the ordinary addition, followed by the topple-process in which each element larger than 3 is decreased by 4 and each of its von Neumann neighbors is increased by 1.
For any n, there is a neutral element e_n such that the set S(n) = { A in M_n({0..3}) | A (+) e_n = A } of matrices invariant under sandpile addition of e_n, forms a group, i.e., each element A in S(n) has an inverse A' in S(n) such that A (+) A' = e_n. (For n > 1, e_n cannot be the zero matrix O_n, because for this choice S(n) would include, e.g., the all 1's matrix 1_n which cannot have an inverse X such that 1_n (+) X = O_n. The element e_n is the unique nonzero matrix such that e_n (+) e_n = e_n.)
The present sequence lists the size of the abelian group (S(n), (+), e_n). See the example section for the e_n. The elements of S(2) are listed as A300006 and their inverses are listed as A300007. (End)

			From _M. F. Hasler_, Mar 07 2018: (Start)
For n = 1, there exists only one 0 X 0 matrix, e_0 = []; it is the neutral element of the singleton group S(0) = {[]}.
For n = 2, the sandpile addition is isomorphic to addition in Z/4Z, the neutral element is e_1 = [0] and we get the group S(1) isomorphic to (Z/4Z, +).
For n = 3, one finds that e_2 = [2,2;2,2] is the neutral element of the sandpile addition restricted to S(2), having 192 elements, listed in A300006.
For n = 4, one finds that e_3 = [2,1,2;1,0,1;2,1,2] is the neutral element of the sandpile addition restricted to S(3), having 100352 elements.
For n = 5, the neutral element is e_4 = [2,3,3,2; 3,2,2,3; 3,2,2,3; 2,3,3,2]. (End)

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Alois P. Heinz, Table of n, a(n) for n = 1..45
Anakin Dey, Sam Ruggerio, and Melkior Ornik, Optimizing a Model-Agnostic Measure of Graph Counterdeceptiveness via Reattachment, arXiv:2311.15093 [math.OC], 2023. See p. 10.
Noah Doman, The Identity of the Abelian Sandpile Group, Bachelor Thesis, University of Groningen (Netherlands 2020).
Laura Florescu, Daniela Morar, David Perkinson, Nick Salter and Tianyuan Xu, Sandpiles and Dominos, Electronic Journal of Combinatorics, Volume 22, Issue 1 (2015), Paper #P1.66
Luis David Garcia-Puente and Brady Haran, Sandpiles, Numberphile video, on YouTube.com, Jan. 13, 2017
Antal A. Járai, Sandpile models, arXiv:1401.0354 [math.PR], 2014.
Germain Kreweras, Complexite et circuits Euleriens dans les sommes tensorielles de graphes, J. Combin. Theory, B 24 (1978), 202-212.
Lionel Levine and James Propp, What is... a sandpile?, Notices of the AMS, Volume 57 (2010), Number 8, 976-979.
F. Redig, Mathematical aspects of the abelian sandpile model (2005)
W.-J. Tzeng, F. Y. Wu, Spanning Trees on Hypercubic Lattices and Non-orientable Surfaces. arXiv:cond-mat/0001408v1 [cond-mat.stat-mech], Jan 2000.
W.-J. Tzeng and F. Y. Wu, Dimers on a simple-quartic net with a vacancy, arXiv:cond-mat/0203149v2 [cond-mat.stat-mech], Mar 2002.
Eric Weisstein's World of Mathematics, Grid Graph
Eric Weisstein's World of Mathematics, Spanning Tree
David B. Wilson, Local statistics of the abelian sandpile model (2014)
F. Y. Wu, Number of spanning trees on a lattice, J. Phys. A: Math. Gen., 10 (1977) no. 6, L113-L115.
Index to divisibility sequences

Main diagonal of A116469.
Cf. A300006, A300007, A300008, A300009; A256043, A256045.
Cf. A080690 (number of acyclic orientations), A080691 (number of spanning forests), A349718 (number of spanning trees, reduced for symmetry).

a:= n-> round(evalf(2^(n^2-1) /n^2 *mul(mul(`if`(j<>0 or k<>0, 2 -cos(Pi*j/n) -cos(Pi*k/n), 1), k=0..n-1), j=0..n-1), 15 +n*(n+1)/2)): seq(a(n), n=1..20);  # Alois P. Heinz, Apr 15 2011
# uses expression as a resultant
seq(resultant(simplify(ChebyshevU(n-1, x/2)), simplify(ChebyshevU(n-1, (4-x)/2)), x), n = 1 .. 24); # Peter Bala, Apr 29 2014

Table[2^((n-1)^2) Product[(2 - Cos[Pi i/n] - Cos[Pi j/n]), {i, 1, n-1}, {j, 1, n-1}], {n, 12}] // Round
Table[Resultant[ChebyshevU[n-1, x/2], ChebyshevU[n-1, (4-x)/2], x], {n, 1, 12}] (* Vaclav Kotesovec, Apr 15 2020 *)

{a(n) = polresultant( polchebyshev(n-1, 2, x/2), polchebyshev(n-1, 2, (4-x)/2) )}; /* Michael Somos, Aug 12 2017 */

a(n) = 2^(n^2-1) / n^2 * product_{n1=0..n-1, n2=0..n-1, n1 and n2 not both 0} (2 - cos(Pi*n1/n) - cos(Pi*n2/n) ). - Sharon Sela (sharonsela(AT)hotmail.com), Jun 04 2002
Equivalently, a(n) = Resultant( U(n-1,x/2), U(n-1,(4-x)/2) ), where U(n,x) is a Chebyshev polynomial of the second kind. - Peter Bala, Apr 29 2014
From Vaclav Kotesovec, Dec 30 2020: (Start)
a(n) ~ 2^(1/4) * Gamma(1/4) * exp(4*G*n^2/Pi) / (Pi^(3/4)*sqrt(n)*(1+sqrt(2))^(2*n)), where G is Catalan's constant A006752.
a(n) = n * 2^(n-1) * A007726(n)^2. (End)

More terms and better description from Roberto E. Martinez II, Jan 07 2002

A007725 Number of spanning trees of Aztec diamonds of order n.

Original entry on oeis.org

1, 4, 768, 18170880, 48466759778304, 14179455913065873408000, 449549878218740179750040371200000, 1534679662450485063038349752542766158611218432, 561985025597966566291275288056092110323394467225010519932928

Offset: 0

Richard Stanley

nonn

Timothy Y. Chow, The Q-spectrum and spanning trees of tensor products of bipartite graphs, Proc. Amer. Math. Soc. 125 (1997), no. 11, 3155-3161.
D. E. Knuth, Aztec Diamonds, Checkerboard Graphs, and Spanning Trees, arXiv:math/9501234 [math.CO], 1995; J. Alg. Combinatorics 6 (1997), 253-257.
R. P. Stanley, Spanning trees of Aztec diamonds, Discrete Math. 157 (1996), 375-388 (Problem 251).
Index entries for sequences related to trees

Cf. A007726, A340166, A340176, A340185, A340352.

Table[4^n * Product[Product[4 - 4*Cos[j*Pi/(2*n)]*Cos[k*Pi/(2*n)], {k, 1, n-1}], {j, 1, 2*n-1}], {n, 0, 10}] // Round (* Vaclav Kotesovec, Jan 05 2021 *)

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

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

a(n) = 4^(2*n-1) * Product_{1<=j,k<=n-1} (4 - 4*cos(j*Pi/(2*n))*cos(k*Pi/(2*n)))*(4 + 4*cos(j*Pi/(2*n))*cos(k*Pi/(2*n))); [Knuth Eq. (8) p. 3]. - Seiichi Manyama, Jan 05 2021

More terms from Alois P. Heinz, Jan 20 2011

Offset changed (a(0)=1) by Seiichi Manyama, Jan 05 2021

A340052 a(n) = Product_{1<=i

Original entry on oeis.org

1, 1, 5, 91, 5661, 1173821, 801125065, 1786768287095, 12964564030176889, 305121026002697122873, 23243604301636717923421133, 5722586073277932639539150258131, 4548248834078776410469611991220703125

Offset: 0

Seiichi Manyama, Dec 29 2020

nonn

Seiichi Manyama, Table of n, a(n) for n = 0..50

Cf. A007726, A065072, A127605.

Table[2^(n*(n-1)) * Product[Product[Sin[i*Pi/(2*n + 1)]^2 + Sin[j*Pi/(2*n + 1)]^2, {i, 1, j-1}], {j, 2, n}], {n, 0, 15}] // Round (* Vaclav Kotesovec, Dec 30 2020 *)

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

a(n)^2 = A127605(n)/(2^n * (2*n+1)).

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

A340185 Number of spanning trees in the halved Aztec diamond HOD_n.

Original entry on oeis.org

1, 1, 15, 2639, 5100561, 105518291153, 23067254643457375, 52901008815129395889375, 1266973371422697144030728637409, 315937379766837559600972497421046382689, 818563964325891485548944567913851815851212484079

Offset: 0

Seiichi Manyama, Dec 31 2020

nonn

                                              *
                                              |
                      *                   *---*---*
                      |                   |   |   |
      *           *---*---*           *---*---*---*---*
      |           |   |   |           |   |   |   |   |
  *---*---*   *---*---*---*---*   *---*---*---*---*---*---*
    HOD_1           HOD_2                   HOD_3
-------------------------------------------------------------
                  *
                  |
              *---*---*
              |   |   |
          *---*---*---*---*
          |   |   |   |   |
      *---*---*---*---*---*---*
      |   |   |   |   |   |   |
  *---*---*---*---*---*---*---*---*
                HOD_4

Seiichi Manyama, Table of n, a(n) for n = 0..40
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.7.

Cf. A004003, A007725, A007726, A065072, A127605, A340052, A340176 (halved Aztec diamond HMD_n).

Table[4^((n-1)*n) * Product[Product[(1 - Cos[j*Pi/(2*n + 1)]^2*Cos[k*Pi/(2*n + 1)]^2), {k, j+1, n}], {j, 1, n}], {n, 0, 12}] // Round (* Vaclav Kotesovec, Jan 03 2021 *)

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

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

# Using graphillion
from graphillion import GraphSet
def make_HOD(n):
    s = 1
    grids = []
    for i in range(2 * n + 1, 1, -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 A340185(n):
    if n == 0: return 1
    universe = make_HOD(n)
    GraphSet.set_universe(universe)
    spanning_trees = GraphSet.trees(is_spanning=True)
    return spanning_trees.len()
print([A340185(n) for n in range(7)])

a(n) = Product_{1<=j

From Seiichi Manyama, Jan 02 2021: (Start)

a(n) = 4^((n-1)*n) * Product_{1<=j

a(n) = A340052(n) * A065072(n) = (1/2^n) * sqrt(A127605(n) * A004003(n) / (2*n+1)). (End)

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

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

Original entry on oeis.org

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

A340396 a(n) = 2^(n^2 - 1) * Product_{j=1..n, k=1..n} (1 + sin(Pij/n)^2 + sin(Pik/n)^2).

Original entry on oeis.org

0, 1, 96, 93789, 1244160000, 241885578271872, 700566272328037500000, 30323548995402141685610526683, 19627362048402730985830806120284160000, 189995156103157091521654945902925881881155376920, 27506190205802587152768139358989866456457087869970721213256

Offset: 0

Vaclav Kotesovec, Jan 06 2021

nonn

Cf. A004003, A007726, A065072, A067518, A127605, A340052, A340165, A340182, A340183, A340293.

Table[2^(n^2 - 1) * Product[1 + Sin[Pi*j/n]^2 + Sin[Pi*k/n]^2, {j, 1, n}, {k, 1, n}], {n, 0, 10}] // Round

a(n) = 2^(n^2-1) * Product_{j=1..n, k=1..n} (3 - cos(Pi*j/n)^2 - cos(Pi*k/n)^2).
a(n) = 2^(n^2-1) * Product_{j=1..n, k=1..n} (2-cos(2*Pi*j/n)/2-cos(2*Pi*k/n)/2).
a(n) ~ 2^(n^2-1) * exp(4*c*n^2/Pi^2), where c = Integral_{x=0..Pi/2, y=0..Pi/2} log(1 + sin(x)^2 + sin(y)^2) dy dx = -Pi^2*(log(2) + log(sqrt(2)-1)/2) + Pi * Integral_{x=0..Pi/2} log(1 + sqrt(1 + 1/(1 + sin(x)^2))) dx = A340421 = 1.627008991085721315763766677017604437985734719035793082916212355323520649...

A340168 Decimal expansion of a constant related to the asymptotics of A004003.

Original entry on oeis.org

1, 1, 0, 8, 8, 6, 2, 2, 5, 8, 7, 8, 0, 7, 6, 7, 5, 1, 3, 2, 7, 6, 9, 5, 1, 1, 6, 2, 1, 3, 0, 8, 1, 9, 2, 9, 2, 6, 4, 5, 2, 6, 6, 1, 2, 6, 9, 6, 3, 5, 6, 9, 2, 2, 4, 3, 6, 2, 9, 4, 3, 1, 4, 1, 8, 4, 4, 7, 3, 5, 5, 6, 5, 3, 0, 9, 3, 4, 8, 6, 6, 3, 2, 1, 3, 4, 3, 9, 7, 1, 4, 6, 7, 5, 0, 7, 9, 0, 1, 5, 5, 7, 4, 0, 5

Offset: 1

Vaclav Kotesovec, Dec 30 2020

			1.1088622587807675132769511621308192926452661269635692243629431418447355653...

Cf. A004003, A007341, A007726, A065072, A127605, A340052.

RealDigits[2*E^(Catalan/Pi)/(1 + Sqrt[2]), 10, 110][[1]]

Equals lim_{n->infinity} A004003(n) / ((sqrt(2)-1)^(2*n) * exp(4*G*n*(n+1)/Pi)), where G is the Catalan's constant A006752.

Equals 2*exp(G/Pi) / (1 + sqrt(2)), where G is Catalan's constant A006752.

Showing 1-7 of 7 results.

cp's OEIS Frontend

A007341 Number of spanning trees in n X n grid.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A007725 Number of spanning trees of Aztec diamonds of order n.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A340052 a(n) = Product_{1<=i

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A340185 Number of spanning trees in the halved Aztec diamond HOD_n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Python

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

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

Views

Author

Keywords

Crossrefs

Programs

Mathematica

Formula

A340168 Decimal expansion of a constant related to the asymptotics of A004003.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

A340396 a(n) = 2^(n^2 - 1) * Product_{j=1..n, k=1..n} (1 + sin(Pij/n)^2 + sin(Pik/n)^2).