A210662 - OEIS

%I #50 Dec 04 2020 21:09:20

%S 1,2,7,3,22,131,5,71,823,10012,8,228,5096,120465,2810694,13,733,31687,

%T 1453535,65805403,2989126727,21,2356,196785,17525619,1539222016,

%U 135658637925,11945257052321,34,7573,1222550,211351945,36012826776,6158217253688,1052091957273408,179788343101980135

%N Triangle read by rows: T(n,k) (1 <= k <= n) = number of monomer-dimer tilings of an n X k board.

%C The triangle is half of a symmetric square array, since T(n,k) = T(k,n).

%C Equivalently, ways of paving n X k grid cells using only singletons and dominoes. Also, the number of tilings of an n X k chessboard with the two polyominoes (0,0) and (0,0)+(0,1).

%C Also, matchings of the n X k grid graph. The n X k grid graph is also denoted P_m X P_n. For k=2, this is called the ladder graph L_n.

%C In statistical mechanics, this is a special case of the Monomer-Dimer Problem, which deals with monomer-dimer coverings of a finite patch of a lattice.

%C Right hand diagonal is A028420. Left hand diagonal is A000045.

%C Taken as a full square array, columns (and rows) 1-7 respectively match A000045(n+1), A030186, A033506(n-1), A033507(n-1), A033508(n-1), A033509(n-1), A033510(n-1), and have recurrences of order 2 3 6 9 20 36 72. - _R. H. Hardin_, Dec 11 2012

%D Steven R. Finch, Mathematical Constants, Cambridge, 2003, pp. 406-412.

%D Per Hakan Lundow, "Computation of matching polynomials and the number of 1-factors in polygraphs", Research reports, No 12, 1996, Department of Mathematics, Umea University.

%H Alois P. Heinz, <a href="/A210662/b210662.txt">Rows n = 1..18, flattened</a>

%H Ahrens, J. H. <a href="http://dx.doi.org/10.1016/0097-3165(81)90061-3">Paving the chessboard</a>. J. Combin. Theory Ser. A 31(1981), no. 3, 277--288. MR0635371 (84d:05009). See Table I. - _N. J. A. Sloane_, Mar 27 2012

%H Anzalone, Nick, et al. <a href="http://arxiv.org/abs/math/0304359">A Reciprocity Theorem for Monomer-Dimer Coverings.</a> DMCS. 2003. arXiv:math/0304359 [math.CO]

%H F. Cazals, <a href="http://algo.inria.fr/libraries/autocomb/MonoDiMer-html/MonoDiMer.html">Monomer-Dimer Tilings</a>, 1997.

%H Steven R. Finch, <a href="http://www.people.fas.harvard.edu/~sfinch/constant/md/md.html">Two Dimensional Monomer-Dimer Constant</a> [Broken link]

%H Steven R. Finch, <a href="http://web.archive.org/web/20010608043455/http://www.mathsoft.com/asolve/constant/md/md.html">Two Dimensional Monomer-Dimer Constant</a> [From the Wayback machine]

%H P. Flajolet and R. Sedgewick, <a href="http://algo.inria.fr/flajolet/Publications/books.html">Analytic Combinatorics</a>, 2009; see page 362

%H Friedland, Shmuel, and Uri N. Peled, <a href="http://arxiv.org/abs/math/0402009">Theory of Computation of Multidimensional Entropy with an Application to the Monomer-Dimer Problem.</a> arXiv:math/0402009 [math.CO]

%H H. Hosoya and A. Motoyama, <a href="http://scitation.aip.org/content/aip/journal/jmp/26/1/10.1063/1.526778">An effective algorithm for obtaining polynomials for dimer statistics. Application of operator technique on the topological index to two- and three-dimensional rectangular and torus lattices</a>, J. Math. Physics 26 (1985) 157-167 (eq. (26) and Table V).

%H C. Kenyon, D. Randall, and A. Sinclair, <a href="http://link.springer.com/article/10.1007/BF02183743">Approximating the number of monomer-dimer coverings of a lattice</a>, Journal of Statistical Physics 83 (1996), 637-659.

%H David Friedhelm Kind, <a href="https://doi.org/10.13140/RG.2.2.11182.54086">The Gunport Problem: An Evolutionary Approach</a>, De Montfort University (Leicester, UK, 2020).

%H Per Hakan Lundow, <a href="http://www.theophys.kth.se/~phl/Text/1factors.pdf">Enumeration of matchings in polygraphs</a>, 1998.

%H R. C. Read, <a href="http://link.springer.com/article/10.1007/BF02193034">The dimer problem for narrow rectangular arrays: A unified method of solution, and some extensions</a>, Aequationes Mathematicae, 24 (1982), 47-65.

%H Ralf Stephan, <a href="/A210662/a210662.gif">Animation of all 71 matchings of the P(2) X P(4) graph</a>

%H D. Zeilberger, <a href="http://www.math.rutgers.edu/~zeilberg/tokhniot/DOMINO">Source</a>

%H <a href="/index/Do#domino">Index entries for sequences related to dominoes</a>

%H <a href="/index/Mat#matchings">Index entries for sequences related to matchings</a>

%H <a href="/index/Pol#polyominoes">Index entries for sequences related to polyominoes</a>

%F T(1,n) = A000045(n+1), T(2,n) = A030186(n), T(3,n) = A033506(n), T(4,n) = A033507(n), T(5,n) = A033508(n), T(6,n) = A033509(n), T(7,n) = A033510(n), T(8,n) = A033511(n), T(9,n) = A033512(n), T(10,n) = A033513(n), T(11,n) = A033514(n), T(n,n) = A028420(n).

%e Triangle begins:

%e 1

%e 2 7

%e 3 22 131

%e 5 71 823 10012

%e 8 228 5096 120465 2810694

%e 13 733 31687 1453535 65805403 2989126727

%e 21 2356 196785 17525619 1539222016 135658637925 11945257052321

%e 34 7573 1222550 211351945 36012826776 6158217253688 1052091957273408 179788343101980135...

%e The 7 matchings of the P(2) X P(2)-graph are:

%e   . .   .-.   . .   . .   . .   . .   .-.

%e               |       |         | |

%e   . .   . .   . .   . .   .-.   . .   .-.

%o (Sage)

%o from sage.combinat.tiling import TilingSolver, Polyomino

%o def T(n, k):

%o     p = Polyomino([(0, 0)])

%o     q = Polyomino([(0, 0), (0, 1)])

%o     T = TilingSolver([p, q], box=[n, k], reusable=True)

%o     return T.number_of_solutions()

%o # _Ralf Stephan_, May 22 2014

%K nonn,tabl

%O 1,2

%A _N. J. A. Sloane_, Mar 28 2012

%E Typo in term 27 corrected by _Alois P. Heinz_, Dec 03 2012

%E Reviewed by _Ralf Stephan_, May 22 2014