|
| |
|
|
A007341
|
|
Number of spanning trees in n X n grid.
(Formerly M3721)
|
|
22
|
|
|
|
1, 4, 192, 100352, 557568000, 32565539635200, 19872369301840986112, 126231322912498539682594816, 8326627661691818545121844900397056, 5694319004079097795957215725765328371712000, 40325021721404118513276859513497679249183623593590784, 2954540993952788006228764987084443226815814190099484786032640000
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
COMMENTS
|
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:
. .___. . .___. . .___. . .___.
._|___| ._|___| ._| | | ._|___|
| |___| | | | | | |_|_| |___| |
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
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)
|
|
|
REFERENCES
|
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
|
LINKS
|
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
Lionel Levine and James Propp, What is... a sandpile?, Notices of the AMS, Volume 57 (2010), Number 8, 976-979.
|
|
|
FORMULA
|
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
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)
|
|
|
EXAMPLE
|
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)
|
|
|
MAPLE
|
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
|
|
|
MATHEMATICA
|
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 *)
|
|
|
PROG
|
(PARI) {a(n) = polresultant( polchebyshev(n-1, 2, x/2), polchebyshev(n-1, 2, (4-x)/2) )}; /* Michael Somos, Aug 12 2017 */
|
|
|
CROSSREFS
|
Cf. A080690 (number of acyclic orientations), A080691 (number of spanning forests).
|
|
|
KEYWORD
|
nonn,easy
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
