|
%I M3721 #106 Nov 30 2023 12:26:01
%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).
%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
|
