|
%I M2160 #138 Nov 07 2023 19:48:56
%S 1,2,36,6728,12988816,258584046368,53060477521960000,
%T 112202208776036178000000,2444888770250892795802079170816,
%U 548943583215388338077567813208427340288,1269984011256235834242602753102293934298576249856
%N Number of domino tilings (or dimer coverings) of a 2n X 2n square.
%C A099390 is the main entry for domino tilings (or dimer tilings) of a rectangle.
%C The numbers of domino tilings in A006253, A004003, A006125 give the number of perfect matchings in the relevant graphs. There are results of Jockusch and Ciucu that if a planar graph has a rotational symmetry then the number of perfect matchings is a square or twice a square - this applies to these 3 sequences. - Dan Fux (dan.fux(AT)OpenGaia.com or danfux(AT)OpenGaia.com), Apr 12 2001
%C _Christine Bessenrodt_ points out that Pachter (1997) shows that a(n) is divisible by 2^n (cf. A065072).
%C a(n) is the number of different ways to cover a 2n X 2n lattice with 2n^2 dominoes. John and Sachs show that a(n) = 2^n*B(n)^2, where B(n) == n+1 (mod 32) when n is even and B(n) == (-1)^((n-1)/2)*n (mod 32) when n is odd. - Yong Kong (ykong(AT)curagen.com), May 07 2000
%D Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 569.
%D S. R. Finch, Mathematical Constants, Cambridge, 2003, pp. 406-412.
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D Darko Veljan, Kombinatorika s teorijom grafova (Croatian) (Combinatorics with Graph Theory) mentions the value 12988816 = 2^4*901^2 for the 8 X 8 case on page 4.
%H Alois P. Heinz, <a href="/A004003/b004003.txt">Table of n, a(n) for n = 0..44</a> (first 26 terms from T. D. Noe)
%H M. Aanjaneya and S. P. Pal, <a href="http://arXiv.org/abs/math.CO/0610925">Faultfree tromino tilings of rectangles</a>, arXiv:math/0610925 [math.CO], 2006.
%H N. Allegra, <a href="http://arxiv.org/abs/1410.4131">Exact solution of the 2d dimer model: Corner free energy, correlation functions and combinatorics</a>, arXiv:1410.4131 [cond-mat.stat-mech], 2014.
%H M. Ciucu, <a href="http://dx.doi.org/10.1006/jcta.1996.2725">Enumeration of perfect matchings in graphs with reflective symmetry</a>, Journal of Combinatorial Theory, Series A, Volume 77, Issue 1, January 1997, Pages 67-97.
%H H. Cohn, <a href="http://arXiv.org/abs/math.CO/0008222">2-adic behavior of numbers of domino tilings</a>, arXiv:math/0008222 [math.CO], 2000.
%H Steven R. Finch, <a href="/FinchDimer.html">The Dimer Problem</a> [From Steven Finch, Apr 20 2019]
%H M. E. Fisher, <a href="http://dx.doi.org/10.1103/PhysRev.124.1664">Statistical mechanics of dimers on a plane lattice</a>, Physical Review, 124 (1961), 1664-1672.
%H P. Flajolet and R. Sedgewick, <a href="http://algo.inria.fr/flajolet/Publications/books.html">Analytic Combinatorics</a>, 2009; see page 363
%H Laura Florescu, Daniela Morar, David Perkinson, Nicholas Salter, Tianyuan Xu, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p66">Sandpiles and Dominos</a>, Electronic Journal of Combinatorics, Volume 22(1), 2015.
%H Laura Florescu, Daniela Morar, David Perkinson, Nicholas Salter, Tianyuan Xu, <a href="/A004003/a004003.pdf">Illustration for a(2) = 36</a> [Fig. 9 from "Sandpiles and Dominos"]
%H W. Jockusch, <a href="http://dx.doi.org/10.1016/0097-3165(94)90006-X">Perfect matchings and perfect squares</a> J. Combin. Theory Ser. A 67 (1994), no. 1, 100-115.
%H Peter E. John and Horst Sachs, <a href="http://dx.doi.org/10.1016/S0012-365X(99)00301-5">On a strange observation in the theory of the dimer problem</a>, Discrete Math. 216 (2000), no. 1-3, 211-219.
%H Adrien Kassel, <a href="http://images.math.cnrs.fr/Le-modele-de-dimeres.html">Le modèle de dimères</a>, Images des Mathématiques, CNRS, 2016. [In French]
%H P. W. Kasteleyn, <a href="http://dx.doi.org/10.1016/0031-8914(61)90063-5">The Statistics of Dimers on a Lattice</a>, Physica, 27 (1961), 1209-1225.
%H P. W. Kasteleyn, <a href="http://dx.doi.org/10.1063/1.1703953">Dimer statistics and phase transitions</a>, J. Mathematical Phys. 4 1963 287-293. MR0153427 (27 #3394).
%H Viet-Ha Nguyen, Kévin Perrot, Mathieu Vallet, <a href="https://doi.org/10.1016/j.tcs.2020.04.007">NP-completeness of the game Kingdomino(TM)</a>, Theoretical Computer Science (2020) Vol. 822, 23-35. See also <a href="https://arxiv.org/abs/1909.02849">arXiv:1909.02849</a>, [cs.CC], 2019.
%H Lior Pachter, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v4i1r29">Combinatorial approaches and conjectures ...</a>, Elec. J. Comb. 4 (1997) #R29.
%H James Propp, <a href="http://math.colgate.edu/~integers/x30/x30.pdf">Some 2-Adic Conjectures Concerning Polyomino Tilings of Aztec Diamonds</a>, Integers (2023) Vol. 23, Art. A30.
%H Jaime Rangel-Mondragon, <a href="https://web.archive.org/web/20190411024906/http://www.mathematica-journal.com/issue/v9i3/polyominoes.html">Polyominoes and Related Families</a>, The Mathematica Journal, 9:3 (2005), 609-640.
%H N. J. A. Sloane, <a href="/A004003/a004003_2.pdf">Illustration for a(2) = 36</a> [Slide from an old talk I gave]
%H R. P. Stanley, <a href="http://www-math.mit.edu/~rstan/papers/comb.pdf">A combinatorial miscellany</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/DominoTiling.html">Domino Tiling</a>
%H Eric Weisstein, <a href="/A004003/a004003.gif">Illustration for a(2) = 36</a>, from Domino Tilings web page (see previous link) [Included with permission]
%H <a href="/index/Do#domino">Index entries for sequences related to dominoes</a>
%F a(n) = A099390(2n,2n).
%F a(n) = Product_{j=1..n} Product_{k=1..n} (4*cos(j*Pi/(2*n+1))^2 + 4*cos(k*Pi/(2*n+1))^2). - _N. J. A. Sloane_, Mar 16 2015
%F a(n) = 2^n * A065072(n)^2. - _Alois P. Heinz_, Nov 22 2018
%F a(n)^2 = Resultant(U(2*n,x/2), U(2*n,i*x/2)), where U(n,x) is a Chebyshev polynomial of the second kind and i = sqrt(-1). - _Seiichi Manyama_, Apr 13 2020
%F a(n) ~ 2 * (sqrt(2)-1)^(2*n+1) * exp(G*(2*n+1)^2/Pi), where G is Catalan's constant A006752. - _Vaclav Kotesovec_, Dec 30 2020
%e The 36 solutions for the 4 X 4 board, from Neven Juric, May 14 2008:
%e A01 = {(1,2), (3,4), (5,6), (7,8), (9,10), (11,12), (13,14), (15,16)}
%e A02 = {(1,2), (3,4), (5,6), (7,11), (9,10), (8,12), (13,14), (15,16)}
%e A03 = {(1,2), (3,4), (5,9), (6,7), (10,11), (8,12), (13,14), (15,16)}
%e A04 = {(1,2), (3,4), (5,9), (6,10), (7,8), (11,12), (13,14), (15,16)}
%e A05 = {(1,2), (3,4), (5,9), (6,10), (7,11), (8,12), (13,14), (15,16)}
%e A06 = {(1,2), (3,4), (5,6), (7,8), (9,10), (13,14), (11,15), (12,16)}
%e A07 = {(1,2), (3,4), (5,9), (6,10), (7,8), (11,15), (13,14), (12,16)}
%e A08 = {(1,2), (3,4), (5,6), (7,8), (9,13), (10,14), (11,12), (15,16)}
%e A09 = {(1,2), (3,4), (5,6), (7,11), (8,12), (9,13), (10,14), (15,16)}
%e A10 = {(1,2), (3,4), (5,6), (7,8), (9,13), (10,11), (14,15), (12,16)}
%e A11 = {(1,2), (3,4), (5,6), (7,8), (9,13), (10,14), (11,15), (12,16)}
%e A12 = {(1,2), (5,6), (3,7), (4,8), (9,10), (11,12), (13,14), (15,16)}
%e A13 = {(1,2), (3,7), (4,8), (5,9), (6,10), (11,12), (13,14), (15,16)}
%e A14 = {(1,2), (5,6), (3,7), (4,8), (9,10), (13,14), (11,15), (12,16)}
%e A15 = {(1,2), (3,7), (4,8), (6,10), (5,9), (11,15), (12,16), (13,14)}
%e A16 = {(1,2), (3,7), (4,8), (5,6), (9,13), (10,14), (11,12), (15,16)}
%e A17 = {(1,2), (3,7), (4,8), (5,6), (9,13), (10,11), (14,15), (12,16)}
%e A18 = {(1,2), (5,6), (3,7), (4,8), (9,13), (10,14), (11,15), (12,16)}
%e A19 = {(1,5), (2,6), (3,4), (7,8), (9,10), (11,12), (13,14), (15,16)}
%e A20 = {(1,5), (2,6), (3,4), (7,11), (8,12), (9,10), (13,14), (15,16)}
%e A21 = {(1,5), (3,4), (2,6), (9,10), (7,8), (11,15), (13,14), (12,16)}
%e A22 = {(1,5), (2,6), (3,4), (7,8), (9,13), (10,14), (11,12), (15,16)}
%e A23 = {(1,5), (2,6), (3,4), (7,11), (8,12), (9,13), (10,14), (15,16)}
%e A24 = {(1,5), (2,6), (3,4), (7,8), (9,13), (10,11), (14,15), (12,16)}
%e A25 = {(1,5), (2,6), (3,4), (7,8), (9,13), (10,14), (11,15), (12,16)}
%e A26 = {(1,5), (2,3), (6,7), (4,8), (9,10), (11,12), (13,14), (15,16)}
%e A27 = {(1,5), (2,6), (3,7), (4,8), (9,10), (11,12), (13,14), (15,16)}
%e A28 = {(1,5), (2,3), (6,7), (4,8), (9,10), (11,15), (13,14), (12,16)}
%e A29 = {(1,5), (2,6), (3,7), (4,8), (9,10), (13,14), (11,15), (12,16)}
%e A30 = {(1,5), (2,3), (6,7), (4,8), (9,13), (10,14), (11,12), (15,16)}
%e A31 = {(1,5), (2,6), (3,7), (4,8), (9,13), (10,14), (11,12), (15,16)}
%e A32 = {(1,5), (2,6), (3,7), (4,8), (9,13), (10,14), (11,15), (12,16)}
%e A33 = {(1,5), (2,6), (3,7), (4,8), (9,13), (10,11), (14,15), (12,16)}
%e A34 = {(1,5), (2,3), (4,8), (6,10), (7,11), (9,13), (14,15), (12,16)}
%e A35 = {(1,5), (2,3), (6,7), (4,8), (9,13), (10,14), (11,15), (12,16)}
%e A36 = {(1,5), (2,3), (6,7), (4,8), (9,13), (10,11), (14,15), (12,16)}
%p f := n->2^(2*n^2)*product(product(cos(i*Pi/(2*n+1))^2+cos(j*Pi/(2*n+1))^2,j=1..n),i=1..n); for k from 0 to 12 do round(evalf(f(k),300)) od;
%t a[n_] := Round[ N[ Product[ 2*Cos[(2i*Pi)/(2n+1)] + 2*Cos[(2j*Pi)/(2n+1)] + 4, {i, 1, n}, {j, 1, n}], 300] ]; Table[a[n], {n, 0, 12}] (* _Jean-François Alcover_, Jan 04 2012, after Maple *)
%t Table[Sqrt[Resultant[ChebyshevU[2*n, x/2], ChebyshevU[2*n, I*x/2], x]], {n, 0, 12}] (* _Vaclav Kotesovec_, Dec 30 2020 *)
%o (PARI) {a(n) = sqrtint(polresultant(polchebyshev(2*n, 2, x/2), polchebyshev(2*n, 2, I*x/2)))} \\ _Seiichi Manyama_, Apr 13 2020
%o (Python)
%o from math import isqrt
%o from sympy.abc import x
%o from sympy import I, resultant, chebyshevu
%o def A004003(n): return isqrt(resultant(chebyshevu(n<<1,x/2),chebyshevu(n<<1,I*x/2))) if n else 1 # _Chai Wah Wu_, Nov 07 2023
%Y Cf. A028420, A006253, A006125, A065072, A124997, A239273, A256043.
%Y Main diagonal of array A099390 or A187596.
%K nonn,easy,nice
%O 0,2
%A _N. J. A. Sloane_, _Greg Huber_
%E Corrected and extended by _David Radcliffe_
|
