A033506 -id:A033506 - cp's OEIS frontend

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

N. J. A. Sloane, Mar 28 2012

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

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

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.

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

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

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

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

Reviewed by Ralf Stephan, May 22 2014

A100245 Triangle read by rows: T(n,k) is the number of k-matchings in the P_3 X P_n lattice graph.

Original entry on oeis.org

1, 1, 2, 1, 7, 11, 3, 1, 12, 44, 56, 18, 1, 17, 102, 267, 302, 123, 11, 1, 22, 185, 758, 1597, 1670, 757, 106, 1, 27, 293, 1654, 5256, 9503, 9401, 4603, 908, 41, 1, 32, 426, 3080, 13254, 35004, 56456, 53588, 27688, 6716, 540, 1, 37, 584, 5161, 28191, 99183

Offset: 0

Emeric Deutsch, Dec 28 2004

Row n contains 1+floor(3n/2) terms. Row sums yield A033506.

			T(2,2)=11 because in the P_3 X P_ 2 lattice graph with vertex set {O(0,0),A(1,0),B(1,1),C(1,2),D(0,2),E(0,1)} and edge set {OA,EB,DC,OE,ED,AB,BC} we have the following eleven 2-matchings: {OA,EB},{OA,DC},{EB,DC},{OA,ED},{OA,BC},{DC,OE},{DC,AB},{OE,AB},{OE,BC},{ED,AB} and {ED,BC}.
Triangle starts:
1;
1,2;
1,7,11,3;
1,12,44,56,18;
1,17,102,267,302,123,11;

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

Cf. A033506, A001835 (bisection diagonal).

G:=(1+t*z-t^3*z^2)*(1-2*t*z-t^3*z^2)/(1-(1+3*t)*z-t*(1+t)*(2+5*t)*z^2-t^2*(1+2*t)*(1-t)*z^3+t^4*(2+3*t+5*t^2)*z^4-t^6*(1-t)*z^5-t^9*z^6): Gser:=simplify(series(G,z=0,11)): P[0]:=1: for n from 1 to 8 do P[n]:=coeff(Gser,z^n) od:for n from 0 to 8 do seq(coeff(t*P[n],t^k),k=1..floor(3*n/2)+1) od; # yields sequence in triangular form

G.f.=(1+tz-t^3*z^2)(1-2tz-t^3*z^2)/[1-(1+3t)z-t(1+t)(2+5t)z^2-t^2*(1+2t)(1-t)z^3+t^4*(2+3t+5t^2)z^4-t^6*(1-t)z^5-t^9*z^6]. The row generating polynomials A[n] satisfy A[n]=(1+3t)A[n-1]+t(2+7t+5t^2)A[n-2]+t^2*(1+t-2t^2)A[n-3]-t^4*(2+3t+5t^2)A[n-4]+t^6*(1-t)A[n-5]+t^9*A[n-6].

Keyword tabl changed to tabf by Michel Marcus, Apr 09 2013

A335747 Number of ways to tile vertically-fault-free 3 X n strip with squares and dominoes.

Original entry on oeis.org

1, 3, 13, 26, 66, 154, 380, 904, 2204, 5286, 12818, 30854, 74636, 179948, 434820, 1049122, 2533818, 6115538, 14766868, 35646080, 86064196, 207766110, 501609946, 1210964110, 2923573588, 7058053972, 17039774268

Offset: 0

Greg Dresden and Oluwatobi Jemima Alabi, Jun 20 2020

nonn

By "vertically-fault-free" we mean that the tilings of the 3 X n strip do not split along any interior vertical line. Here are two of the 66 possible vertically-fault-free tilings of a 3 X 4 strip with squares and dominoes:
.  _       _  
| |_ |   | _|_| |
|| _| |   | | |_|
|| _||   ||_| |

			a(2) = 13 thanks to these thirteen vertically-fault-free tilings of a 3 X 2 strip:
._ _     _ _     _ _     _ _     _ _     _ _     _ _
|_ _|   |_|_|   |_|_|   |_ _|   |_|_|   |_ _|   |_ _|
|_|_|   |_ _|   |_|_|   |_ _|   |_ _|   |_|_|   |_ _|
|_|_|   |_|_|   |_ _|   |_|_|   |_ _|   |_ _|   |_ _|
._ _     _ _     _ _     _ _     _ _     _ _
|_ _|   |_ _|   |_ _|   | |_|   |_| |   | | |
| |_|   |_| |   | | |   |_|_|   |_|_|   |_|_|
|_|_|   |_|_|   |_|_|   |_ _|   |_ _|   |_ _|

G. C. Greubel, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (1,4,-1,-1).

Cf. A033506 (which gives all tilings of 3 X n strip), A112577, A134438, A291227.

Cf. A000045, A000129.

I:=[26, 66, 154, 380]; [1,3,13] cat [n le 4 select I[n] else Self(n-1) +4*Self(n-2) -Self(n-3) -Self(n-4): n in [1..40]]; // G. C. Greubel, Jan 15 2022

CoefficientList[Series[(1+2x+6x^2+2x^3-8x^4+x^6)/((1+x-x^2)(1-2x-x^2)), {x, 0, 26}], x] (* Michael De Vlieger, Jul 03 2020 *)
LinearRecurrence[{1,4,-1,-1}, {1,3,13,26,66,154,380}, 40] (* G. C. Greubel, Jan 15 2022 *)

def P(n): return lucas_number1(n,2,-1)
def A335747(n): return (1/3)*(-9*bool(n==0) - 3*bool(n==1) + 3*bool(n==2) + 2*(3*P(n+1) + 2*P(n-1)) + 2*(-1)^n*fibonacci(n-1))
[A335747(n) for n in (0..40)] # G. C. Greubel, Jan 15 2022

a(n) = a(n-1) + 4*a(n-2) - a(n-3) - a(n-4) for n >= 7.
a(n) = 2*A291227(n) - 8*A112577(n-2) + 2*A112577(n-4) for n >= 4.
a(n) = (2/3)*(A221174(n+1) + (-1)^n*A000045(n-1)) for n >= 3. - Greg Dresden, Jul 03 2020
G.f.: (1 + 2*x + 6*x^2 + 2*x^3 - 8*x^4 + x^6) / ((1 + x - x^2)*(1 - 2*x - x^2)). - Colin Barker, Jun 21 2020
a(n) = (1/3)*(-9*[n=0] - 3*[n=1] + 3*[n=2] + 2*(3*A000129(n+1) + 2*A000129(n-1)) + 2*(-1)^n*Fibonacci(n-1)). - G. C. Greubel, Jan 15 2022

A376031 Number of ways to tile a 3 x (2*n) rectangle with dominoes and T's.

Original entry on oeis.org

1, 3, 18, 112, 692, 4294, 26624, 165086, 1023662, 6347440, 39358774, 244053158, 1513307844, 9383614226, 58185263358, 360791140032, 2237168644134, 13872079956206, 86017029971684, 533368425534858, 3307273890427894, 20507514248408832, 127161570097317790

Offset: 0

Greg Dresden and Lucas MingQu Xia, Sep 06 2024

a(n) is the number of ways to tile a 3 X (2*n) rectangle with two kinds of tiles: dominoes (made up of 2 cells) and T's (made up of 4 cells), each of which can be rotated as needed.

			For n=3, here is one of the a(3) = 112 ways to tile a 3 x 6 rectangle using our dominoes and T's:
 ___________
| |___| | | |
|  _|_  |_|_|
|_|___|_|___|.

Paolo Xausa, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (5,7,4,-8,2).

Cf. A033506, A219968, A337492, A346054.

LinearRecurrence[{5, 7, 4, -8, 2}, {1, 3, 18, 112, 692}, 30] (* Paolo Xausa, Sep 23 2024 *)

a(n) = 5*a(n-1) + 7*a(n-2) + 4*a(n-3) - 8*a(n-4) + 2*a(n-5).

G.f.: -(2*x^4-3*x^3-4*x^2-2*x+1)/(2*x^5-8*x^4+4*x^3+7*x^2+5*x-1).

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

References

Links

Programs

Sage

Formula

Extensions

A100245 Triangle read by rows: T(n,k) is the number of k-matchings in the P_3 X P_n lattice graph.

Views

Author

Keywords

Comments

Examples

References

Crossrefs

Programs

Maple

Formula

Extensions

A335747 Number of ways to tile vertically-fault-free 3 X n strip with squares and dominoes.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

Sage

Formula

A376031 Number of ways to tile a 3 x (2*n) rectangle with dominoes and T's.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula