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

1, 2, 7, 3, 22, 131, 5, 71, 823, 10012, 8, 228, 5096, 120465, 2810694, 13, 733, 31687, 1453535, 65805403, 2989126727, 21, 2356, 196785, 17525619, 1539222016, 135658637925, 11945257052321, 34, 7573, 1222550, 211351945, 36012826776, 6158217253688, 1052091957273408, 179788343101980135

Offset: 1

Author

N. J. A. Sloane, Mar 28 2012

Keywords

• nonn
• tabl

Comments

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

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).

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.

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.

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

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

Examples

			Triangle begins:
1
2 7
3 22 131
5 71 823 10012
8 228 5096 120465 2810694
13 733 31687 1453535 65805403 2989126727
21 2356 196785 17525619 1539222016 135658637925 11945257052321
34 7573 1222550 211351945 36012826776 6158217253688 1052091957273408 179788343101980135...
The 7 matchings of the P(2) X P(2)-graph are:
  . .   .-.   . .   . .   . .   . .   .-.
              |       |         | |
  . .   . .   . .   . .   .-.   . .   .-.
		

References

• Steven R. Finch, Mathematical Constants, Cambridge, 2003, pp. 406-412.
• 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.

Links

• Alois P. Heinz, Rows n = 1..18, flattened
• Ahrens, J. H. Paving the chessboard. J. Combin. Theory Ser. A 31(1981), no. 3, 277--288. MR0635371 (84d:05009). See Table I. - _N. J. A. Sloane_, Mar 27 2012
• Anzalone, Nick, et al. A Reciprocity Theorem for Monomer-Dimer Coverings. DMCS. 2003. arXiv:math/0304359 [math.CO]
• F. Cazals, Monomer-Dimer Tilings, 1997.
• Steven R. Finch, Two Dimensional Monomer-Dimer Constant [Broken link]
• Steven R. Finch, Two Dimensional Monomer-Dimer Constant [From the Wayback machine]
• P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 362
• Friedland, Shmuel, and Uri N. Peled, Theory of Computation of Multidimensional Entropy with an Application to the Monomer-Dimer Problem. arXiv:math/0402009 [math.CO]
• H. Hosoya and A. Motoyama, 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, J. Math. Physics 26 (1985) 157-167 (eq. (26) and Table V).
• C. Kenyon, D. Randall, and A. Sinclair, Approximating the number of monomer-dimer coverings of a lattice, Journal of Statistical Physics 83 (1996), 637-659.
• David Friedhelm Kind, The Gunport Problem: An Evolutionary Approach, De Montfort University (Leicester, UK, 2020).
• Per Hakan Lundow, Enumeration of matchings in polygraphs, 1998.
• R. C. Read, The dimer problem for narrow rectangular arrays: A unified method of solution, and some extensions, Aequationes Mathematicae, 24 (1982), 47-65.
• Ralf Stephan, Animation of all 71 matchings of the P(2) X P(4) graph
• D. Zeilberger, Source
• Index entries for sequences related to dominoes
• Index entries for sequences related to matchings
• Index entries for sequences related to polyominoes

Programs

Sage

from sage.combinat.tiling import TilingSolver, Polyomino
def T(n, k):
    p = Polyomino([(0, 0)])
    q = Polyomino([(0, 0), (0, 1)])
    T = TilingSolver([p, q], box=[n, k], reusable=True)
    return T.number_of_solutions()
# Ralf Stephan, May 22 2014

Formula

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).

Extensions

Typo in term 27 corrected by Alois P. Heinz, Dec 03 2012

Reviewed by Ralf Stephan, May 22 2014