A007341 -id:A007341 - cp's OEIS frontend

A299999 Duplicate of A007341.

1, 4, 192, 100352

Offset: 0

dead

A116469 Square array read by antidiagonals: T(m,n) = number of spanning trees in an m X n grid.

1, 1, 1, 1, 4, 1, 1, 15, 15, 1, 1, 56, 192, 56, 1, 1, 209, 2415, 2415, 209, 1, 1, 780, 30305, 100352, 30305, 780, 1, 1, 2911, 380160, 4140081, 4140081, 380160, 2911, 1, 1, 10864, 4768673, 170537640, 557568000, 170537640, 4768673, 10864, 1

Offset: 1

Calculated by Hugo van der Sanden after a suggestion from Leroy Quet, Mar 20 2006

This is the number of ways the points in an m X n grid can be connected to their orthogonal neighbors such that for any pair of points there is precisely one path connecting them.
a(n,n) = A007341(n).
a(m,n) = number of perfect mazes made from a grid of m X n cells. - Leroy Quet, Sep 08 2007
Also number of domino tilings of the (2m-1) X (2n-1) rectangle with upper left corner removed.  For m=2, n=3 the 15 domino tilings of the 3 X 5 rectangle with upper left corner removed are:
. ._.___. . ._.___. . ._.___. . ._.___. . ._.___.
.|__|___| .|__|___| .| | |__| .|__|___| .| |__| |
| |_|___| | | | |_| | |||___| |_| |_| | ||__|_|
||__|___| |||_|_| ||__|___| |_|_|_| ||__|___|
. ._.___. . ._.___. . ._.___. . ._.___. . ._.___.
.|__|___| .|__|___| .| | |__| .|__|___| .|__|___|
| |_| | | | | | | | | | ||| | | |_| | | | | | |_| |
||__|_|| ||_|||_| ||__|_|| |__|_||| |||___|_|
. ._.___. . ._.___. . ._.___. . ._.___. . ._.___.
.|__| | | .|__| | | .| | | | | .|___| | | .|__|___|
| |_|_|| | | | ||_| | |||_|| |__| ||| |_|___| |
||__|___| |||_|_| ||__|___| |_|_|_| |_|___|_|
   - Alois P. Heinz, Apr 15 2011
Each row (and column) of the square array is a divisibility sequence, i.e., if n divides m then a(n) divides a(m). It follows that the main diagonal, A007341, is also a divisibility sequence. Row k satisfies a linear recurrence of order 2^k. - Peter Bala, Apr 29 2014

			a(2,2) = 4, since we must have exactly 3 of the 4 possible connections: if we have all 4 there are multiple paths between points; if we have fewer some points will be isolated from others.
Array begins:
  1,   1,      1,         1,           1,              1, ...
  1,   4,     15,        56,         209,            780, ...
  1,  15,    192,      2415,       30305,         380160, ...
  1,  56,   2415,    100352,     4140081,      170537640, ...
  1, 209,  30305,   4140081,   557568000,    74795194705, ...
  1, 780, 380160, 170537640, 74795194705, 32565539635200, ...

Seiichi Manyama, Antidiagonals n = 1..50, flattened
Germain Kreweras, Complexité et circuits Eulériens dans les sommes tensorielles de graphes, J. Combin. Theory, B 24 (1978), 202-212. - From _N. J. A. Sloane_, May 27 2012

Diagonal gives A007341. Rows and columns 1..10 give A000012, A001353, A006238, A003696, A003779, A139400, A334002, A334003, A334004, A334005.

Digits:=200;
T:=(m,n)->round(Re(evalf(simplify(expand(
mul(mul( 4*sin(h*Pi/(2*m))^2+4*sin(k*Pi/(2*n))^2, h=1..m-1), k=1..n-1)))))); # crude Maple program from N. J. A. Sloane, May 27 2012

T[m_, n_] := Product[4 Sin[h Pi/(2 m)]^2 + 4 Sin[k Pi/(2 n)]^2, {h, m - 1}, {k, n - 1}]; Flatten[Table[FullSimplify[T[k, r - k]], {r, 2, 10}, {k, 1, r - 1}]] (* Ben Branman, Mar 10 2013 *)

T(n,m) = polresultant(polchebyshev(n-1, 2, x/2), polchebyshev(m-1, 2, (4-x)/2)); \\ Michel Marcus, Apr 13 2020

# Using graphillion
from graphillion import GraphSet
import graphillion.tutorial as tl
def A116469(n, k):
    if n == 1 or k == 1: return 1
    universe = tl.grid(n - 1, k - 1)
    GraphSet.set_universe(universe)
    spanning_trees = GraphSet.trees(is_spanning=True)
    return spanning_trees.len()
print([A116469(j + 1, i - j + 1) for i in range(9) for j in range(i + 1)])  # Seiichi Manyama, Apr 12 2020

T(m,n) = Product_{k=1..n-1} Product_{h=1..m-1} (4*sin(h*Pi/(2*m))^2 + 4*sin(k*Pi/(2*n))^2); [Kreweras] - N. J. A. Sloane, May 27 2012

Equivalently, T(n,m) = resultant( U(n-1,x/2), U(m-1,(4-x)/2) ) = Product_{k = 1..n-1} Product_{h = 1..m-1} (4 - 2*cos(h*Pi/m) - 2*cos(k*Pi/n)), where U(n,x) denotes the Chebyshev polynomial of the second kind. The divisibility properties of the array mentioned in the Comments follow from this representation. - Peter Bala, Apr 29 2014

A007726 Number of spanning trees of quarter Aztec diamonds of order n.

Original entry on oeis.org

1, 1, 4, 56, 2640, 411840, 210613312, 351102230528, 1901049105201408, 33349238079515381760, 1892086487183556298556416, 346728396311328694807284940800, 205021218459835103075295973360128000, 390870571052378289975757743555515137130496

Offset: 1

Richard Stanley

nonn

Mihai Ciucu (ciucu(AT)math.gatech.edu), in preparation, 2001.

Seiichi Manyama, Table of n, a(n) for n = 1..50
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.
R. Kenyon, J. Propp and D. Wilson, Trees and matchings, Electronic Journal of Combinatorics, 7(1):R25, 2000.
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. A007725, A007341, A065072, A340052.

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

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

a(n) = Product_{0Sean A. Irvine, Jan 20 2018
From Vaclav Kotesovec, Dec 30 2020: (Start)
a(n) ~ sqrt(Gamma(1/4)) * 2^(5/8) * exp(2*G*n^2/Pi) / (Pi^(3/8) * n^(3/4) * 2^(n/2) * (1 + sqrt(2))^n), where G is Catalan's constant A006752.
a(n) = sqrt(A007341(n) / (n * 2^(n-1))). (End)

More terms from Sean A. Irvine, Jan 20 2018

A127605 a(n) = 2^(2nn) * Product_{i=1..n} Product_{j=1..n} (sin(iPi/(2n+1))^2 + sin(jPi/(2n+1))^2).

Original entry on oeis.org

1, 6, 500, 463736, 4614756624, 485005220494432, 533978739649683515200, 6129678550595328659594928000, 731483813983605533022316212534132992, 905665520470954445892575061753881157482726912

Offset: 0

Miklos Kristof, Apr 03 2007

nonn

Cf. A004003, A007341, A340052.

for n from 0 to 12 do a[n]:=2^(2*n*n)*product(product(sin(i*Pi/(2*n+1))^2+ sin(j*Pi/(2*n+1))^2,j=1..n),i=1..n) od: seq(round(evalf(a[n],300)),n=0..12);

Table[(2*n+1) * 2^(n*(2*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}]^2, {n, 0, 15}] // Round (* Vaclav Kotesovec, Dec 30 2020 *)

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

A300006 Matrices of the 2 X 2 sandpile group, with matrix [a,b;c,d] encoded as concat(a,b,c,d), leading 0 omitted.

Original entry on oeis.org

112, 113, 121, 122, 123, 131, 132, 133, 211, 212, 213, 220, 221, 222, 223, 230, 231, 232, 233, 311, 312, 313, 320, 321, 322, 323, 330, 331, 332, 333, 1012, 1013, 1021, 1022, 1023, 1031, 1032, 1033, 1102, 1103, 1112, 1113, 1120, 1121, 1122, 1123, 1130, 1131

Offset: 1

M. F. Hasler, Mar 07 2018

The 2 X 2 sandpile group S2 has 192 elements (called sandpiles), which are obtained as sandpile-addition of any arbitrary 2 X 2 matrix to the neutral element E2 = [2,2;2,2]. Equivalently, these are exactly the matrices which are invariant under sandpile-addition of E2.
Sandpile-addition is standard matrix 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, iterated until no element is > 3. The addition table for the group S2 is given in A300009.
The 2 X 2 matrices A = [a,b;c,d] are represented here as concat(a,b,c,d) (or Sum_{i,j=1..2} 10^(6-2i-j)*A[i,j]), and listed in lexicographic order. The first 30 elements (corresponding to the 3-digit terms < 1000) have a = 0 which is not displayed.
The opposite of the i-th element A300006(i) (in the above lexicographic order) is the A300007(i)-th element, A300008(i) = A300006(A300007(i)).

			a(1) = 0112 represents the matrix A = [0,1;1,2]. As illustration, add this to E2 = [2,2;2,2]: A + E2 = [2,3;3,4], and the 4 "topples": it gets 4 subtracted and both neighbors (the two 3's) get incremented by 1, thus: [2,4;4;0]. Now the two 4's topple, each one incrementing the 2 and the 0 by one: [4,0;0,2]. Once again the 4 topples: [0,1;1,2]. This is the result: A (+) E2 = A.
a(116) = 2222 represents E2 = [2,2;2,2], which is the only nonzero 2 X 2 matrix such that M (+) M = M. (Indeed, 2222 + 2222 = 4444 -> 2222, as each 4 topples to 0 and gets +1 from each of its 2 neighbors.) It is (by definition) the neutral element in S2 := { A in M_2(Z) | A (+) E2 = A }, and it turns out that there is an opposite or inverse A' for each A in S(2), such that A (+) A' = E2. (This would not be the case for the zero matrix.)

M. F. Hasler, Table of n, a(n) for n = 1..192
L. David Garcia-Puente, in Sandpiles, Numberphile video, on YouTube.com, Jan 13 2017

Cf. A007341 (order of the sandpile group for (n-1) X (n-1) grid), A300008 (inverse of a(n)), A300007 (indices of the inverses), A300009 (addition table of this group).

spa(A,B=0,C=0*A[,1],R=0*A[1,])={A+=B; while(B=A\4,A+=concat(B[,^1], C)+concat(C,B[,^-1])+concat(B[^1,],R)+concat(R,B[^-1,])-4*B); A} \\ sandpile addition; without 2nd arg only "topple"
S2=List(); forvec(v=vector(4,i,[2,5]), listput(S2,spa(Mat([v[1..2],v[3..4]]~)))); S2=Set(S2) \\ The 2 X 2 sandpile group as subset of 2 X 2 matrices with coefficients in [0..3], here determined by adding an arbitrary matrix 2 X 2 to the matrix E2 = [2,2;2,2]; equivalently one could select the 2 X 2 matrices invariant under sandpile-addition of E2: see also A007341.
A300006=apply( m2d=M->fromdigits(concat(Col(M~)~)), S2) \\ matrix-to-decimal encoding. Use transpose because PARI sorts matrices [a,b;c,d] as (a,c,b,d).

A080691 Number of spanning forests of the n X n grid graph.

Original entry on oeis.org

1, 15, 3102, 8790016, 341008617408, 181075508242067552, 1315927389374152034113856, 130877523274817580209987036404864, 178135975585132088643635627145305047963624, 3318089946193080260596185780557019330240985991363200, 845810281460839114896541390288164525407725177643901666416522016

Offset: 1

Andre Poenitz [André Pönitz], Peter Tittmann, Mar 03 2003

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..15
N. Calkin, C. Merino, S. Noble and M. Noy, Improved Bounds for the Number of Forests and Acyclic Orientations in the Square Lattice, The Electronic Journal of Combinatorics, Volume 10(1), 2003, #R4.
A. Pönitz, Über eine Methode zur Konstruktion von Algorithmen für die Berechnung von Invarianten in endlichen ungerichteten Hypergraphen, PhD Thesis (2004) C.3.
Peter Tittmann, More Results [Gives a(1)-a(14)]
Eric Weisstein's World of Mathematics, Grid Graph

Main diagonal of A360194.

Cf. A007341, A080690.

Terms a(10) and beyond from Andrew Howroyd, Feb 22 2023

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.

A375817 In an n X n grid draw straight walls between cells, starting at a border, such that the resulting figure is connected and has only one-cell wide paths; a(n) is the number of solutions not reduced for symmetries.

Original entry on oeis.org

1, 4, 56, 1112, 25000, 607712, 15918280, 451371888, 13908978792, 466254401360, 16972978214456, 668532916285104, 28362769354991656, 1290007395847848160, 62619708755213093360, 3230982278203826268640, 176553522584025285715304, 10184062836771923067636528

Offset: 1

Lars Blomberg, Aug 30 2024

nonn

This sequence contains some, but not all of the spanning trees in A007341, a(n)<A007341(n), for n>2.

See A375770 for examples.

			a(3) = 56. The A375770(3) = 10 distinct solutions with their multiplicities are:
  ._._._.   ._._._.   ._._._.   ._._._.   ._._._.
  |     |   |   | |   |   | |   | | | |   |   ._|
  | | | |   | |   |   | | | |   |     |   | |   |
  |_|_|_|   |_|_|_|   |_|_._|   |_|_|_|   |_|_|_|
    (4)       (8)       (4)       (2)       (8)
  ._._._.   ._._._.   ._._._.   ._._._.   ._._._.
  | | ._|   |   | |   |   ._|   |_. ._|   |_. | |
  |     |   | | ._|   | | ._|   |     |   |   ._|
  |_|_|_|   |_|_._|   |_|_._|   |_|_|_|   |_|_._|
    (8)       (8)       (8)       (4)       (2)

Andrew Howroyd, Table of n, a(n) for n = 1..100

Main diagonal of A375858.

Cf. A007341, A375770 (up to rotations and reflections), A375859 (up to rotations), A375860 (up to symmetries of the rectangle).

\\ See PARI link in A375770 for program code.
vector(20, n, A375817(n)) \\ Andrew Howroyd, Sep 03 2024

Terms corrected and extended by Andrew Howroyd, Sep 03 2024

A071763 Number of spanning trees in n X n X n grid.

Original entry on oeis.org

1, 384, 8193540096000, 172685928902844729688524604506636288, 77746347057132811936046563068332100246216273086593103906734080000000000000

Offset: 1

Sharon Sela (sharonsela(AT)hotmail.com), Jun 04 2002

nonn

W.-J. Tzeng and F. Y. Wu, Spanning Trees on Hypercubic Lattices and Non-orientable Surfaces, arXiv:cond-mat/0001408 [cond-mat.stat-mech], 2000.
Eric Weisstein's World of Mathematics, Grid Graph
Eric Weisstein's World of Mathematics, Spanning Tree

Cf. A007341, A340182.

Table[2^(n^3 - 1)/n^3 Product[Piecewise[{{1, i == j == k == 0}}, 3 - Cos[Pi i/n] - Cos[Pi j/n] - Cos[Pi k/n]], {i, 0, n - 1}, {j, 0, n - 1}, {k, 0, n - 1}], {n, 12}] // Round

a(n) = 2^(n^3-1) / n^3 * Product_{n1=0..n-1 n2=0..n-1 n3=0..n-1} (3- cos(Pi*n1/n) - cos(Pi*n2/n) - cos(Pi*n3/n) ) where n1, n2, n3 are not all 0.

Limit_{n->infinity} a(n)^(1/n^3) = exp(8 * A340322 / Pi^3) = 5.330202889205167421134597996649659520108446730592285502966091902480522584119... - Vaclav Kotesovec, Jan 05 2021

A080690 Number of acyclic orientations of n X n grid graph.

Original entry on oeis.org

1, 14, 2398, 5015972, 128091434266, 39931856138212664, 151966368274993474937668, 7059965159455454640307807067492, 4003910412343921295679925280332950062686, 27719972687144020161876951888422165049044889741764

Offset: 1

Andre Poenitz [André Pönitz], Peter Tittmann (poenitz(AT)htwm.de), Mar 03 2003

nonn

N. Calkin, C. Merino, S. Noble and M. Noy, Improved Bounds for the Number of Forests and Acyclic Orientations in the Square Lattice, The Electronic Journal of Combinatorics, Volume 10(1), 2003, #R4.
A. Pönitz, Über eine Methode zur Konstruktion von Algorithmen für die Berechnung von Invarianten in endlichen ungerichteten Hypergraphen, PhD Thesis (2004) C.3.
Peter Tittmann, More Results [Gives a(1)-a(14)]

Cf. A007341, A080691.

a(10) from Alois P. Heinz, Dec 21 2013

cp's OEIS Frontend

A299999 Duplicate of A007341.

Views

Author

Keywords

A116469 Square array read by antidiagonals: T(m,n) = number of spanning trees in an m X n grid.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

A007726 Number of spanning trees of quarter Aztec diamonds of order n.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A127605 a(n) = 2^(2*n*n) * Product_{i=1..n} Product_{j=1..n} (sin(i*Pi/(2*n+1))^2 + sin(j*Pi/(2*n+1))^2).

Views

Author

Keywords

Crossrefs

Programs

Maple

Mathematica

Formula

A300006 Matrices of the 2 X 2 sandpile group, with matrix [a,b;c,d] encoded as concat(a,b,c,d), leading 0 omitted.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A080691 Number of spanning forests of the n X n grid graph.

Views

Author

Keywords

Links

Crossrefs

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

A375817 In an n X n grid draw straight walls between cells, starting at a border, such that the resulting figure is connected and has only one-cell wide paths; a(n) is the number of solutions not reduced for symmetries.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Extensions

A071763 Number of spanning trees in n X n X n grid.

Views

Author

A127605 a(n) = 2^(2nn) * Product_{i=1..n} Product_{j=1..n} (sin(iPi/(2n+1))^2 + sin(jPi/(2n+1))^2).