A028471 -id:A028471 - cp's OEIS frontend

A099390 Array T(m,n) read by antidiagonals: number of domino tilings (or dimer tilings) of the m X n grid (or m X n rectangle), for m>=1, n>=1.

0, 1, 1, 0, 2, 0, 1, 3, 3, 1, 0, 5, 0, 5, 0, 1, 8, 11, 11, 8, 1, 0, 13, 0, 36, 0, 13, 0, 1, 21, 41, 95, 95, 41, 21, 1, 0, 34, 0, 281, 0, 281, 0, 34, 0, 1, 55, 153, 781, 1183, 1183, 781, 153, 55, 1, 0, 89, 0, 2245, 0, 6728, 0, 2245, 0, 89, 0, 1, 144, 571, 6336, 14824, 31529, 31529, 14824, 6336, 571, 144, 1

Offset: 1

Ralf Stephan, Oct 16 2004

There are many versions of this array (or triangle) in the OEIS. This is the main entry, which ideally collects together all the references to the literature and to other versions in the OEIS. But see A004003 for further information. - N. J. A. Sloane, Mar 14 2015

			0,  1,  0,   1,    0,    1, ...
1,  2,  3,   5,    8,   13, ...
0,  3,  0,  11,    0,   41, ...
1,  5, 11,  36,   95,  281, ...
0,  8,  0,  95,    0, 1183, ...
1, 13, 41, 281, 1183, 6728, ...

S. R. Finch, Mathematical Constants, Cambridge, 2003, pp. 406-412.
P. E. John, H. Sachs, and H. Zernitz, Problem 5. Domino covers in square chessboards, Zastosowania Matematyki (Applicationes Mathematicae) XIX 3-4 (1987), 635-641.
R. P. Stanley, Enumerative Combinatorics, Vol. 1, Cambridge University Press, 2nd ed., pp. 547 and 570.
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.

Alois P. Heinz, Table of n, a(n) for n = 1..1035
M. Aanjaneya and S. P. Pal, Faultfree tromino tilings of rectangles, arXiv:math/0610925 [math.CO], 2006.
Mudit Aggarwal and Samrith Ram, Generating Functions for Straight Polyomino Tilings of Narrow Rectangles, J. Int. Seq., Vol. 26 (2023), Article 23.1.4.
F. Ardila and R. P. Stanley, Tilings, arXiv:math/0501170 [math.CO], 2005.
M. Ciucu, Enumeration of perfect matchings in graphs with reflective symmetry, Journal of Combinatorial Theory, Series A, Volume 77, Issue 1, January 1997, Pages 67-97.
Henry Cohn, 2-adic behavior of numbers of domino tilings, arXiv:math/0008222 [math.CO], 2000.
Henry Cohn, 2-adic behavior of numbers of domino tilings, Electronic Journal of Combinatorics, 6 (1999), #R14.
F. Faase, Counting Hamiltonian cycles in product graphs
F. Faase, Results from the counting program
Steven R. Finch, The Dimer Problem [From Steven Finch, Apr 20 2019]
Steven R. Finch, Two Dimensional Monomer Dimer Constant [Broken link]
M. E. Fisher, Statistical mechanics of dimers on a plane lattice, Physical Review, 124 (1961), 1664-1672.
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 363.
Laura Florescu, Daniela Morar, David Perkinson, Nicholas Salter, and Tianyuan Xu, Sandpiles and Dominos, Electronic Journal of Combinatorics, Volume 22(1), 2015.
W. Jockusch, Perfect matchings and perfect squares J. Combin. Theory Ser. A 67 (1994), no. 1, 100-115.
Peter E. John and Horst Sachs, On a strange observation in the theory of the dimer problem, arXiv:math/9801094 [math.CO], 1998.
Peter E. John and Horst Sachs, On a strange observation in the theory of the dimer problem, Discrete Math. 216 (2000), no. 1-3, 211-219.
Yuhi Kamio, Junnosuke Koizumi, and Toshihiko Nakazawa, Quadratic residues and domino tilings, arXiv:2311.13597 [math.NT], 2023.
David Klarner and Jordan Pollack, Domino tilings of rectangles with fixed width, Disc. Math. 32 (1980) 45-52, Table 1.
Per Hakan Lundow, Enumeration of matchings in polygraphs, 1998.
P. W. Kasteleyn, The statistics of dimers on a lattice, I. the number of dimer arrangements on a quadratic lattice, Physica 27 (1961), 1209-1225.
Douglas M. McKenna, The Art of Space-Filling Domino Curves, Bridges Conference Proceedings, 2024, pp. 319-326.
L. Pachter, Combinatorial approaches and conjectures for 2-divisibility problems concerning domino tilings of polyominoes, Electronic Journal of Combinatorics 4 (1997), #R29.
J. Propp, Dimers and Dominoes
J. Propp, Enumeration of Matchings: Problems and Progress, arXiv:math/9904150v2 [math.CO], 1999.
Jaime Rangel-Mondragon, Polyominoes and Related Families, The Mathematica Journal, 9:3 (2005), 609-640.
R. C. Read, A Note on Tiling Rectangles with Dominoes, The Fibonacci Quarterly, 18.1 (1980), 24-27.
R. P. Stanley, A combinatorial miscellany
H. N. V. Temperley and Michael E. Fisher, Dimer problem in statistical mechanics -- an exact result, Philos. Mag. (8) 6 (1961), 1061-1063.
Herman Tulleken, Polyominoes 2.2: How they fit together, (2019).
Eric Weisstein's World of Mathematics, Domino Tiling
Eric Weisstein, Illustration for T(4,4) = 36, from Domino Tilings web page (see previous link) [Included with permission]
Index entries for sequences related to dominoes

See A187596 for another version (with m >= 0, n >= 0). See A187616 for a triangular version. See also A187617, A187618.
See also A004003 for more literature on the dimer problem.
Rows 2-13, 16 (without zeros) are A000045, A001835, A005178, A003775, A028468, A028469, A028470, A028471, A028472, A028473, A028474, A241908, A340532.
Main diagonal is A004003.
Cf. A103997, A103999, A233320, A230031, A233427.

(Maple code for the even-numbered rows from N. J. A. Sloane, Mar 15 2015. This is not totally satisfactory since it uses floating point. However, it is useful for getting the initial values quickly.)
Digits:=100;
p:=evalf(Pi);
z:=proc(h,d) global p; evalf(cos( h*p/(2*d+1) )); end;
T:=proc(m,n) global z; round(mul( mul( 4*z(h,m)^2+4*z(k,n)^2, k=1..n), h=1..m)); end;
[seq(T(1,n),n=0..10)]; # A001519
[seq(T(2,n),n=0..10)]; # A188899
[seq(T(3,n),n=0..10)]; # A256044
[seq(T(n,n),n=0..10)]; # A004003

T[?OddQ, ?OddQ] = 0;
T[m_, n_] := Product[2*(2+Cos[2j*Pi/(m+1)]+Cos[2k*Pi/(n+1)]), {k, 1, n/2}, {j, 1, m/2}];
Flatten[Table[Round[T[m-n+1, n]], {m, 1, 12}, {n, 1, m}]] (* Jean-François Alcover, Nov 25 2011, updated May 28 2022 *)

{T(n, k) = sqrtint(abs(polresultant(polchebyshev(n, 2, x/2), polchebyshev(k, 2, I*x/2))))} \\ Seiichi Manyama, Apr 13 2020

T(m, n) = Product_{j=1..ceiling(m/2)} Product_{k=1..ceiling(n/2)} (4*cos(j*Pi/(m+1))^2 + 4*cos(k*Pi/(n+1))^2).

Old link fixed and new link added by Frans J. Faase, Feb 04 2009

Entry edited by N. J. A. Sloane, Mar 15 2015

A189005 Number of domino tilings of the 9 X n grid with upper left corner removed iff n is odd.

Original entry on oeis.org

1, 1, 55, 209, 6336, 30305, 817991, 4140081, 108435745, 557568000, 14479521761, 74795194705, 1937528668711, 10021992194369, 259423766712000, 1342421467113969, 34741645659770711, 179796299139278305, 4652799879944138561

Offset: 0

Alois P. Heinz, Apr 15 2011

Alois P. Heinz, Table of n, a(n) for n = 0..300
Index entries for sequences related to dominoes

9th row of array A189006.

Bisection gives: A028471 (even part), A003779 (odd part).

A[1, 1] = 1;
A[m_, n_] := A[m, n] = Module[{i, j, s, t, M}, Which[m == 0 || n == 0, 1, m < n, A[n, m], True, s = Mod[n*m, 2]; M[i_, j_] /; j < i := -M[j, i]; M[, ] = 0; For[i = 1, i <= n, i++, For[j = 1, j <= m, j++, t = (i - 1)*m + j - s; If[i > 1 || j > 1 || s == 0, If[j < m, M[t, t + 1] = 1]; If[i < n, M[t, t + m] = 1 - 2*Mod[j, 2]]]]]; Sqrt[Det[Array[M, {n*m - s, n*m - s}]] ]]];
a[n_] := A[9, n];
a /@ Range[0, 18] (* Jean-François Alcover, Feb 27 2020, after Alois P. Heinz in A189006 *)

G.f.: -(x^30+x^29-154*x^28 +6777*x^26-1440*x^25-123961*x^24 +26752*x^23 +1132714*x^22-185889*x^21 -5684515*x^20+574750*x^19+16401668*x^18 -708928*x^17 -27757938*x^16+27757938*x^14+708928*x^13 -16401668*x^12 -574750*x^11+5684515*x^10 +185889*x^9-1132714*x^8-26752*x^7 +123961*x^6 +1440*x^5-6777*x^4+154*x^2-x-1) / (x^32-209*x^30+11936*x^28 -274208*x^26 +3112032*x^24-19456019*x^22 +70651107*x^20-152325888*x^18+196664896*x^16 -152325888*x^14+70651107*x^12 -19456019*x^10 +3112032*x^8-274208*x^6 +11936*x^4-209*x^2+1).

A241908 Number of perfect matchings in graph P_{13} X P_{2n}.

Original entry on oeis.org

1, 377, 413351, 536948224, 731164253833, 1012747193318519, 1412218550274852671, 1974622635952709613247, 2764079753958605286860951, 3870940598132705729413670953, 5422065916132126528319352874496, 7595338059193606161156363370300487, 10640045682768766172108553992086690201

Offset: 0

Sergey Perepechko, May 01 2014

In Karavaev and Perepechko generating functions G_m(x) for P_m X P_n graphs were found for all values of m up to 27.

A. M. Karavaev and S. N. Perepechko, Generating functions for dimer problem on rectangular lattices (in Russian), Information Processes, 13(2013), No4, 374-400.

Sergey Perepechko, Generating function for A241908

Row 13 of array A099390.

Cf. A028470, A028471, A028472, A028473, A028474, A187596.

{a(n) = sqrtint(polresultant(polchebyshev(2*n, 2, x/2), polchebyshev(13, 2, I*x/2)))} \\ Seiichi Manyama, Apr 13 2020

A360799 Numbers m with m mod 3 = q, q != 2, such that the number of ones in its base-2 representation is even if q=0 and odd if q=1.

Original entry on oeis.org

0, 1, 3, 4, 6, 7, 9, 12, 13, 15, 16, 18, 19, 22, 24, 25, 27, 28, 30, 31, 33, 36, 37, 39, 45, 48, 49, 51, 52, 54, 55, 57, 60, 61, 63, 64, 66, 67, 70, 72, 73, 75, 76, 78, 79, 82, 88, 90, 91, 94, 96, 97, 99, 100, 102, 103, 105, 108, 109, 111, 112, 114, 115, 118, 120, 121

Offset: 0

Gerhard Kirchner, Feb 24 2023

nonn

For q=0, the terms in A180963 are excluded.
The terms of the sequence occur, with some exceptions, while tiling a wall (odd width w) with 1 X 2 dominos. The current tiling status can be described by a number x with 0 <= x < 2^w. In the base-2 representation, 1 stands for an overstanding unit square, see example.
Statement:
The tiling always starts with q=1 and an odd number of ones (type 1) and is followed by a term with q=0 and an even number of ones (type 2) and so on, alternately.
Proof:
Start, provisionally, with w upright dominos. The corresponding term is x = (11..1) = 2^w-1 with x mod 3 = 1 (type 1). Another first profile can be generated by replacing a pair of adjacent upright dominos with one flat domino. In the base-2 representation, this is the subtraction (11..11..1) - (00..11..0) = (11..00..1). The subtrahend is 3*2^j with 0 <= j < w. Therefore, the modified term also is type 1. This way, any first profile can be found and it is type 1.
In the next provisional step, an upright domino is placed on each not overstanding unit square. If p1 is the first profile, then the second is p2 = 2^w - 1 - p1 with p2 mod 3 = 0. Moreover, the transition from p1 to p2 exchanges the ones and zeros such that p2 is type 2. Again, replacing adjacent upright dominos by one flat domino does not change the type of the profile. The next profile is type 1 and so on. QED. Condition to be satisfied by a tiling profile: The continued removal of 00 and 11 (reduction) leads to (0) or (1). Example: a(10)=18=(10010) -> (110) -> (0). The first exceptions are a(314) = 682 = (01010101010), a(611) = 1365 = (10101010101) and a(988) = 2218 = (0100010101010). Note that the reduction of 2218 is 682.

			 5 X 4 wall is tiled bottom-up with 1 X 2 dominos:
                                      _    ___ ___ _
                 _ _          _ _ ___| |  |_ _|___| |
        _       | | |_ ___   | | |_ _|_|  | | |_ _|_|
    ___| |___   |_|_| |___|  |_|_| |___|  |_|_| |___|
   |___|_|___|  |___|_|___|  |___|_|___|  |___|_|___|
    0 0 1 0 0    1 1 0 0 0    0 0 0 0 1    0 0 0 0 0
     4 = a(3)   24 = a(14)     1 = a(1)     0 = a(0)

Cf. A001835, A003775, A028469, A028471, A180963, A187616, A360800.

block(kmax: 100, a:[],
 even_ones(x):= block(su:0,
  while x>0 do(p: mod(x,2), x:(x-p)/2, su:su+p),
   return(mod(su,2))),
for k from 0 thru kmax do(r:mod(k,3),
 if r<2 and r=even_ones(k) then a:append(a,[k])),a);

isok(m) = my(k=m%3); if (hammingweight(m) % 2, k==1, k==0); \\ Michel Marcus, Feb 27 2023

A360800 Numbers Sum_{i=1..2r+1} 2^k(i) such that k(1) is even and, for r > 0 and i < 2r+1, the difference k(i+1)-k(i) is > 0 and odd.

Original entry on oeis.org

1, 4, 7, 16, 19, 25, 28, 31, 64, 67, 73, 76, 79, 97, 100, 103, 112, 115, 121, 124, 127, 256, 259, 265, 268, 271, 289, 292, 295, 304, 307, 313, 316, 319, 385, 388, 391, 400, 403, 409, 412, 415, 448, 451, 457, 460, 463, 481, 484, 487, 496, 499, 505, 508, 511, 1024

Offset: 1

Gerhard Kirchner, Feb 24 2023

nonn

This is a subsequence of A360799. Another description of the terms: in the base-2 representation, the number of ones is odd and all zeros are grouped in blocks of even length.

That is why the terms less than 2^(2j+1) describe start profiles for tiling a (2j+1) X m wall with 1 X 2 dominos, see examples and A360799.

			A 5 X m wall is tiled bottom-up with dominos, start profiles:
            _        _            _ _ _    _     _ _    _ _ _ _ _
    ___ ___| |   ___| |___    ___| | | |  | |___| | |  | | | | | |
   |___|___|_|  |___|_|___|  |___|_|_|_|  |_|___|_|_|  |_|_|_|_|_|
    0 0 0 0 1    0 0 1 0 0    0 0 1 1 1    1 0 0 1 1    1 1 1 1 1
    1 = a(1)     4 = a(2)     7 = a(3)     19 = a(5)    31 = a(7)
    also the mirror images of 1 (16), 19 (25) and 7 (28).

Cf. A001835, A003775, A028469, A028471, A180963, A187616, A360799.

block(kmax: 100, a:[],
 oddsum(y):= block(su1:0, su2:0, pold:0, ok: true,
  while y>0 and ok do(p:mod(y,2), y:(y-p)/2,
   if p=1 then(if pold=0 and su2=1 then ok:false, su1:1-su1, su2:0)
   elseif p=0 then su2:1-su2, pold:p), return(is(ok and su1=1))),
for k from 1 thru kmax do if oddsum(k) then a:append(a,[k]),a);

cp's OEIS Frontend

A099390 Array T(m,n) read by antidiagonals: number of domino tilings (or dimer tilings) of the m X n grid (or m X n rectangle), for m>=1, n>=1.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A189005 Number of domino tilings of the 9 X n grid with upper left corner removed iff n is odd.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A241908 Number of perfect matchings in graph P_{13} X P_{2n}.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

PARI

A360799 Numbers m with m mod 3 = q, q != 2, such that the number of ones in its base-2 representation is even if q=0 and odd if q=1.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maxima

PARI

A360800 Numbers Sum_{i=1..2r+1} 2^k(i) such that k(1) is even and, for r > 0 and i < 2r+1, the difference k(i+1)-k(i) is > 0 and odd.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maxima