|
| |
|
|
A007341
|
|
Number of spanning trees in n X n grid.
(Formerly M3721)
|
|
4
| |
|
|
1, 4, 192, 100352, 557568000, 32565539635200, 19872369301840986112, 126231322912498539682594816, 8326627661691818545121844900397056, 5694319004079097795957215725765328371712000, 40325021721404118513276859513497679249183623593590784, 2954540993952788006228764987084443226815814190099484786032640000
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 1,2
|
|
|
COMMENTS
| Kreweras calls this the complexity of the n X n grid.
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
a(n)= number of perfect mazes made from a grid of n-by-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
|
|
|
REFERENCES
| G. Kreweras, Complexite et circuits Euleriens dans la sommes tensorielles de graphes, J. Combin. Theory, B 24 (1978), 202-212.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
|
LINKS
| W.-J. Tzeng, F. Y. Wu, Spanning Trees on Hypercubic Lattices and Non-orientable Surfaces.
Eric Weisstein's World of Mathematics, Grid Graph
Eric Weisstein's World of Mathematics, Spanning Tree
|
|
|
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
|
|
|
MATHEMATICA
| Table[2^(n^2 - 1)/n^2 Product[Piecewise[{{2 - Cos[Pi i/n] - Cos[Pi j/n], i != 0 || j != 0}}, 1], {i, 0, n - 1}, {j, 0, n - 1}], {n, 12}] // Round
|
|
|
CROSSREFS
| Cf. A116469.
Sequence in context: A163839 A012015 A012102 * A203516 A159783 A028370
Adjacent sequences: A007338 A007339 A007340 * A007342 A007343 A007344
|
|
|
KEYWORD
| nonn
|
|
|
AUTHOR
| N. J. A. Sloane (njas(AT)research.att.com).
|
|
|
EXTENSIONS
| More terms and better description from Roberto E. Martinez II (remartin(AT)fas.harvard.edu), Jan 07 2002
|
| |
|
|
