Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).
%I M3721 #109 Sep 03 2024 00:44:49
%S 1,4,192,100352,557568000,32565539635200,19872369301840986112,
%T 126231322912498539682594816,8326627661691818545121844900397056,
%U 5694319004079097795957215725765328371712000,40325021721404118513276859513497679249183623593590784,2954540993952788006228764987084443226815814190099484786032640000
%N Number of spanning trees in n X n grid.
%C Kreweras calls this the complexity of the n X n grid.
%C a(n) is the number of perfect mazes made from a grid of n X n cells. - _Leroy Quet_, Sep 08 2007
%C 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:
%C . .___. . .___. . .___. . .___.
%C ._|___| ._|___| ._| | | ._|___|
%C | |___| | | | | | |_|_| |___| |
%C |_|___| |_|_|_| |_|___| |___|_| - _Alois P. Heinz_, Apr 15 2011
%C 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
%C 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
%C From _M. F. Hasler_, Mar 07 2018: (Start)
%C 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.
%C 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.)
%C 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)
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H Alois P. Heinz, <a href="/A007341/b007341.txt">Table of n, a(n) for n = 1..45</a>
%H Anakin Dey, Sam Ruggerio, and Melkior Ornik, <a href="https://arxiv.org/abs/2311.15093">Optimizing a Model-Agnostic Measure of Graph Counterdeceptiveness via Reattachment</a>, arXiv:2311.15093 [math.OC], 2023. See p. 10.
%H Noah Doman, <a href="http://fse.studenttheses.ub.rug.nl/id/eprint/21391">The Identity of the Abelian Sandpile Group</a>, Bachelor Thesis, University of Groningen (Netherlands 2020).
%H Laura Florescu, Daniela Morar, David Perkinson, Nick Salter and Tianyuan Xu, <a href="https://doi.org/10.37236/4472">Sandpiles and Dominos</a>, Electronic Journal of Combinatorics, Volume 22, Issue 1 (2015), Paper #P1.66
%H Luis David Garcia-Puente and Brady Haran, <a href="https://youtu.be/1MtEUErz7Gg">Sandpiles</a>, Numberphile video, on YouTube.com, Jan. 13, 2017
%H Antal A. Járai, <a href="https://arxiv.org/abs/1401.0354">Sandpile models</a>, arXiv:1401.0354 [math.PR], 2014.
%H Germain Kreweras, <a href="http://dx.doi.org/10.1016/0095-8956(78)90021-7">Complexite et circuits Euleriens dans les sommes tensorielles de graphes</a>, J. Combin. Theory, B 24 (1978), 202-212.
%H Lionel Levine and James Propp, <a href="https://www.ams.org/notices/201008/rtx100800976p.pdf">What is... a sandpile?</a>, Notices of the AMS, Volume 57 (2010), Number 8, 976-979.
%H F. Redig, <a href="http://www.pdmi.ras.ru/~lowdimma/sandpile/sandpilelectures.pdf">Mathematical aspects of the abelian sandpile model</a> (2005)
%H W.-J. Tzeng, F. Y. Wu, <a href="http://arxiv.org/abs/cond-mat/0001408">Spanning Trees on Hypercubic Lattices and Non-orientable Surfaces.</a> arXiv:cond-mat/0001408v1 [cond-mat.stat-mech], Jan 2000.
%H W.-J. Tzeng and F. Y. Wu, <a href="http://arxiv.org/abs/cond-mat/0203149">Dimers on a simple-quartic net with a vacancy</a>, arXiv:cond-mat/0203149v2 [cond-mat.stat-mech], Mar 2002.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/GridGraph.html">Grid Graph</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/SpanningTree.html">Spanning Tree</a>
%H David B. Wilson, <a href="http://online.kitp.ucsb.edu/online/nonequil14/wilson/pdf/Wilson_Nonequil14_KITP.pdf">Local statistics of the abelian sandpile model</a> (2014)
%H F. Y. Wu, <a href="https://iopscience.iop.org/article/10.1088/0305-4470/10/6/004">Number of spanning trees on a lattice</a>, J. Phys. A: Math. Gen., 10 (1977) no. 6, L113-L115.
%H <a href="/index/Di#divseq">Index to divisibility sequences</a>
%F 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
%F 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
%F From _Vaclav Kotesovec_, Dec 30 2020: (Start)
%F 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.
%F a(n) = n * 2^(n-1) * A007726(n)^2. (End)
%e From _M. F. Hasler_, Mar 07 2018: (Start)
%e For n = 1, there exists only one 0 X 0 matrix, e_0 = []; it is the neutral element of the singleton group S(0) = {[]}.
%e 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, +).
%e 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.
%e 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.
%e 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)
%p 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
%p # uses expression as a resultant
%p seq(resultant(simplify(ChebyshevU(n-1, x/2)), simplify(ChebyshevU(n-1, (4-x)/2)), x), n = 1 .. 24); # _Peter Bala_, Apr 29 2014
%t 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
%t Table[Resultant[ChebyshevU[n-1, x/2], ChebyshevU[n-1, (4-x)/2], x], {n, 1, 12}] (* _Vaclav Kotesovec_, Apr 15 2020 *)
%o (PARI) {a(n) = polresultant( polchebyshev(n-1, 2, x/2), polchebyshev(n-1, 2, (4-x)/2) )}; /* _Michael Somos_, Aug 12 2017 */
%Y Main diagonal of A116469.
%Y Cf. A300006, A300007, A300008, A300009; A256043, A256045.
%Y Cf. A080690 (number of acyclic orientations), A080691 (number of spanning forests), A349718 (number of spanning trees, reduced for symmetry).
%K nonn,easy
%O 1,2
%A _N. J. A. Sloane_
%E More terms and better description from _Roberto E. Martinez II_, Jan 07 2002