A300006 -id:A300006 - cp's OEIS frontend

A300007 Index of the inverse/opposite of the n-th 2 X 2 sandpile A300006(n). An involution (self-inverse permutation) of the integers [1..192].

95, 82, 92, 38, 37, 47, 35, 34, 83, 68, 67, 81, 30, 29, 28, 36, 26, 25, 24, 69, 53, 52, 66, 19, 18, 17, 27, 15, 14, 13, 54, 40, 51, 8, 7, 16, 5, 4, 43, 32, 191, 190, 39, 188, 187, 186, 6, 184, 183, 182, 33, 22, 21, 31, 177, 176, 175, 189, 173, 172, 171, 185, 169, 168

Offset: 1

M. F. Hasler, Mar 07 2018

See A300006 for the definition of the sandpile addition of 2 X 2 matrices.
A300006(116) = 2222 represents the neutral element e = [2,2;2,2], so a(116) = 116.
A300006 forms a group for the sandpile addition, so for each A300006(n) there exists a unique m, given here as a(n), such that A300006(n) (+) A300006(m) = 2222 (where (+) means the sandpile addition). A300006(m) is also listed as A300008(n).

			a(1) = 95 because A300006(1) + A300006(95) = 0112 + 2110 = 2222 represents the unit element of the 2 X 2 sandpile group.
a(2) = 82 because A300006(2) + A300006(82) = 0113 + 2003 = 2116 "topples" to 2222.

M. F. Hasler, Table of n, a(n) for n = 1..192

Cf. A300006, A300008, A300009.

A300007(n)=for(m=1,#S2,spa(S2[n],S2[m])==[2,2;2,2]&&return(m)) \\ S2 and spa() being defined as in A300006.

A300008 Inverse of the n-th 2 X 2 sandpile A300006(n).

Original entry on oeis.org

2110, 2003, 2101, 1033, 1032, 1130, 1023, 1022, 2011, 1303, 1302, 2002, 333, 332, 331, 1031, 323, 322, 321, 1310, 1203, 1202, 1301, 233, 232, 231, 330, 223, 222, 221, 1210, 1103, 1201, 133, 132, 230, 123, 122, 1120, 1013, 3332, 3331, 1102, 3323, 3322, 3321, 131, 3313

Offset: 1

M. F. Hasler, Mar 07 2018

As in A300006, a 2 X 2 sandpile [a,b;c,d] is encoded as 4-digit number concat(a,b,c,d), and a leading a = 0 is not displayed.
By definition, a(n) (+) A300006(n) = 2222, the neutral element, where the sandpile addition (+) is the regular addition followed by "toppling" of digits (i.e., matrix elements) larger than 3, as described in A300006.
Sequence A300007(n) gives the index of a(n) in A300006.

M. F. Hasler, Table of n, a(n) for n = 1..192

For links, references etc. see the main entry A300006.

PARI
```
a(n)=A300006[A300007(n)]
```

a(n,e=[2,2;2,2])=for(i=1,#S2,spa(S2[i],S2[n])==e&&return(A300006[i])) \\ spa() and S2 are defined in A300006; A300006[i] is the decimal encoding of S2[i].

a(n) = A300006(A300007(n)).

A300009 Addition table for the 2 X 2 sandpile group: T(m,n) = A300006(m) (+) A300006(n), for 1 <= m <= n <= 192. (Upper right part of the symmetric matrix.)

Original entry on oeis.org

330, 331, 332, 233, 1301, 1203, 1301, 1302, 1310, 1311, 1302, 1303, 1311, 1312, 1313, 1310, 1311, 1213, 1320, 1321, 1223, 1311, 1312, 1320, 1321, 1322, 1330, 1331, 1312, 1313, 1321, 1322, 1323, 1331, 1332, 1333, 323, 1031, 332, 333, 2002, 1303, 2011, 2012, 1023, 1031, 1032, 333, 2002, 2003, 2011, 2012, 2013, 1130

Offset: 1

M. F. Hasler, Mar 07 2018

The sandpile-addition of 2 X 2 matrices is the standard addition, followed by repeated "toppling" of matrix elements > 3, which are decreased by 4 and increase each of their von-Neumann neighbors. A300006 lists all 192 elements of the 2 X 2 sandpile group, the largest subset of the 2 X 2 matrices which forms a group under the sandpile addition, with neutral element e = [2,2;2,2] encoded as A300006(116) = 2222. The symbol (+) denotes sandpile addition indifferently for 2 X 2 matrices and for their decimal encoding.

This is the (addition) table of this group, which is abelian, so we list only 1 <= m <= n <= 192, where m, n are the indices of the elements of A300006.

			T(1,1) = 0330 represents [0,1;1,2] (+) [0,1;1,2] = [0,3;3,0] (result after "toppling" the plain addition of the first element of A300006 to itself, 0112 + 0112 = 0224).
Given that the operation is abelian, the sequence lists only the upper-right (or equivalently, lower left) part of the table: (For reference we mark \abcd\ the diagonal element which is the last one listed of the respective row / column.)
A \ B: 0112  0113  0121  0122  0123  0131  0132  0133  0211  ...
0112 :\0330\ 0331  0233  1301  1302  1310  1311  1312  0323  ...
0113 : 0331 \0332\ 1301  1302  1310  1311  1312  1313  1031  ...
0121 : 0233  1301 \1203\ 1310  1311  1213  1320  1321  0332  ...
0122 : 1301  1302  1310 \1311\ 1312  1320  1321  1322  0333  ...
0123 : 1302  1303  1311  1312 \1313\ 1321  1322  1323  2002  ...
0131 : 1310  1311  1213  1320  1321 \1223\ 1330  1331  2011  ...
0132 : 1311  1312  1320  1321  1322  1330 \1331\ 1332  2012  ...
0133 : 1312  1313  1321  1322  1323  1331  1332 \1333\ 2012  ...
0211 : 0323  1031  0332  0333  2002  1303  2011  2012 \1023\ ...
...

M. F. Hasler, Table of n, a(n) for n = 1..18528. (Complete sequence: row / column 1..192, flattened.)

For links, references etc. see the main entry A300006.

A300009(m,n)=m2d(spa(S2[m],S2[n])) \\ with m2d(), spa() and S2 defined in A300006.

A007341 Number of spanning trees in n X n grid.

Original entry on oeis.org

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

A307652 The number of grains of sand in the identity element for the sandpile group on an (n+1) X (n+1) square grid.

Original entry on oeis.org

8, 12, 40, 52, 72, 88, 136, 160, 216, 244, 320, 356, 408, 448, 544, 592, 704, 756, 888, 948, 1088, 1156, 1304, 1376, 1504, 1584, 1736, 1820, 1984, 2076, 2288, 2384, 2536, 2640, 2912, 3024, 3200, 3316, 3624, 3748, 3976, 4104, 4392, 4528, 4824, 4968, 5216, 5364, 5664, 5820, 6088, 6248, 6616

Offset: 1

Scott R. Shannon, Apr 20 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. Squares on the edge of the board lose sand from the grid when toppling thus a stable configuration for the grid will always occur after a finite number of topples. Starting with the maximal stable grid consisting of 3 grains of sand in all squares, adding sand to one or more squares, and then performing topple stabilization results in a set of recurrent configurations which form the elements of the sandpile group for the given grid size. This group includes one configuration which acts as the identity element for the group, i.e., adding the identity configuration to any chosen group element and then performing topple stabilization results in the chosen group element.

This sequence {a(n)} is the number of sand grains in the identity element of the sandpile group on a square grid of size (n+1) X (n+1).

			a(1) = 2 X 2 grid.
       Identity: | 2 2 |
                 | 2 2 | = 8 grains.
a(2) = 3 X 3 grid.
       Identity: | 2 1 2 |
                 | 1 0 1 |
                 | 2 1 2 | = 12 grains.
a(3) = 4 X 4 grid.
       Identity: | 2 3 3 2 |
                 | 3 2 2 3 |
                 | 3 2 2 3 |
                 | 2 3 3 2 | = 40 grains.
a(4) = 5 X 5 grid.
       Identity: | 2 3 2 3 2 |
                 | 3 2 1 2 3 |
                 | 2 1 0 1 2 |
                 | 3 2 1 2 3 |
                 | 2 3 2 3 2 | = 52 grains.

Scott R. Shannon, Table of n, a(n) for n = 1..500
Yvan Le Borgne, Dominique Rossin, On the identity of the sandpile group. Discrete Mathematics, 256 (2002) 775-790.
Luis David Garcia-Puente and Brady Haran, Sandpiles, Numberphile video, YouTube.com, Jan. 13, 2017.
Alexander E. Holroyd et al., Chip-firing and Rotor-Routing on Directed Graphs. arXiv:0801.3306v4 [math.CO], 2013.
Scott R. Shannon, Identity for the 50x50 grid. For this, and other images, black=0, yellow=1, blue=2, red=3 grains.
Scott R. Shannon, Identity for the 51x51 grid. This shows the crossed line pattern through the center of the grid which is typical of grids with odd numbered side lengths.
Scott R. Shannon, Identity for the 1000x1000 grid.
Scott R. Shannon, Identity for the 4000x4000 grid. This contains 37246680 grains.
Scott R. Shannon, Simplified Java code for finding the identity element and the sequence a(n).
Wikipedia, Abelian Sandpile Model.

Cf. A259013, A180230, A300006.

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

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

The sequence is closely fitted by the quadratic a(n) ~ 2.32*n^2, where 2.32 corresponds to the approximate grains per square density of the identity element configurations.

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.

cp's OEIS Frontend

A300007 Index of the inverse/opposite of the n-th 2 X 2 sandpile A300006(n). An involution (self-inverse permutation) of the integers [1..192].

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A300008 Inverse of the n-th 2 X 2 sandpile A300006(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

PARI

Formula

A300009 Addition table for the 2 X 2 sandpile group: T(m,n) = A300006(m) (+) A300006(n), for 1 <= m <= n <= 192. (Upper right part of the symmetric matrix.)

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A007341 Number of spanning trees in n X n grid.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A307652 The number of grains of sand in the identity element for the sandpile group on an (n+1) X (n+1) square grid.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

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