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,2

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

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

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

Example

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

Prog

(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

Crossrefs

Sequence in context: A336854 A209666 A089124 * A229610 A117809 A052091

Adjacent sequences: A210659 A210660 A210661 * A210663 A210664 A210665

Keyword

nonn,tabl

Author

N. J. A. Sloane, Mar 28 2012

Extensions

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

Reviewed by Ralf Stephan, May 22 2014

Status

approved