A028420 -id:A028420 - cp's OEIS frontend

A004003 Number of domino tilings (or dimer coverings) of a 2n X 2n square.

1, 2, 36, 6728, 12988816, 258584046368, 53060477521960000, 112202208776036178000000, 2444888770250892795802079170816, 548943583215388338077567813208427340288, 1269984011256235834242602753102293934298576249856

Offset: 0

N. J. A. Sloane, Greg Huber

A099390 is the main entry for domino tilings (or dimer tilings) of a rectangle.
The numbers of domino tilings in A006253, A004003, A006125 give the number of perfect matchings in the relevant graphs. There are results of Jockusch and Ciucu that if a planar graph has a rotational symmetry then the number of perfect matchings is a square or twice a square - this applies to these 3 sequences. - Dan Fux (dan.fux(AT)OpenGaia.com or danfux(AT)OpenGaia.com), Apr 12 2001
Christine Bessenrodt points out that Pachter (1997) shows that a(n) is divisible by 2^n (cf. A065072).
a(n) is the number of different ways to cover a 2n X 2n lattice with 2n^2 dominoes. John and Sachs show that a(n) = 2^n*B(n)^2, where B(n) == n+1 (mod 32) when n is even and B(n) == (-1)^((n-1)/2)*n (mod 32) when n is odd. - Yong Kong (ykong(AT)curagen.com), May 07 2000

			The 36 solutions for the 4 X 4 board, from Neven Juric, May 14 2008:
A01 = {(1,2), (3,4), (5,6), (7,8), (9,10), (11,12), (13,14), (15,16)}
A02 = {(1,2), (3,4), (5,6), (7,11), (9,10), (8,12), (13,14), (15,16)}
A03 = {(1,2), (3,4), (5,9), (6,7), (10,11), (8,12), (13,14), (15,16)}
A04 = {(1,2), (3,4), (5,9), (6,10), (7,8), (11,12), (13,14), (15,16)}
A05 = {(1,2), (3,4), (5,9), (6,10), (7,11), (8,12), (13,14), (15,16)}
A06 = {(1,2), (3,4), (5,6), (7,8), (9,10), (13,14), (11,15), (12,16)}
A07 = {(1,2), (3,4), (5,9), (6,10), (7,8), (11,15), (13,14), (12,16)}
A08 = {(1,2), (3,4), (5,6), (7,8), (9,13), (10,14), (11,12), (15,16)}
A09 = {(1,2), (3,4), (5,6), (7,11), (8,12), (9,13), (10,14), (15,16)}
A10 = {(1,2), (3,4), (5,6), (7,8), (9,13), (10,11), (14,15), (12,16)}
A11 = {(1,2), (3,4), (5,6), (7,8), (9,13), (10,14), (11,15), (12,16)}
A12 = {(1,2), (5,6), (3,7), (4,8), (9,10), (11,12), (13,14), (15,16)}
A13 = {(1,2), (3,7), (4,8), (5,9), (6,10), (11,12), (13,14), (15,16)}
A14 = {(1,2), (5,6), (3,7), (4,8), (9,10), (13,14), (11,15), (12,16)}
A15 = {(1,2), (3,7), (4,8), (6,10), (5,9), (11,15), (12,16), (13,14)}
A16 = {(1,2), (3,7), (4,8), (5,6), (9,13), (10,14), (11,12), (15,16)}
A17 = {(1,2), (3,7), (4,8), (5,6), (9,13), (10,11), (14,15), (12,16)}
A18 = {(1,2), (5,6), (3,7), (4,8), (9,13), (10,14), (11,15), (12,16)}
A19 = {(1,5), (2,6), (3,4), (7,8), (9,10), (11,12), (13,14), (15,16)}
A20 = {(1,5), (2,6), (3,4), (7,11), (8,12), (9,10), (13,14), (15,16)}
A21 = {(1,5), (3,4), (2,6), (9,10), (7,8), (11,15), (13,14), (12,16)}
A22 = {(1,5), (2,6), (3,4), (7,8), (9,13), (10,14), (11,12), (15,16)}
A23 = {(1,5), (2,6), (3,4), (7,11), (8,12), (9,13), (10,14), (15,16)}
A24 = {(1,5), (2,6), (3,4), (7,8), (9,13), (10,11), (14,15), (12,16)}
A25 = {(1,5), (2,6), (3,4), (7,8), (9,13), (10,14), (11,15), (12,16)}
A26 = {(1,5), (2,3), (6,7), (4,8), (9,10), (11,12), (13,14), (15,16)}
A27 = {(1,5), (2,6), (3,7), (4,8), (9,10), (11,12), (13,14), (15,16)}
A28 = {(1,5), (2,3), (6,7), (4,8), (9,10), (11,15), (13,14), (12,16)}
A29 = {(1,5), (2,6), (3,7), (4,8), (9,10), (13,14), (11,15), (12,16)}
A30 = {(1,5), (2,3), (6,7), (4,8), (9,13), (10,14), (11,12), (15,16)}
A31 = {(1,5), (2,6), (3,7), (4,8), (9,13), (10,14), (11,12), (15,16)}
A32 = {(1,5), (2,6), (3,7), (4,8), (9,13), (10,14), (11,15), (12,16)}
A33 = {(1,5), (2,6), (3,7), (4,8), (9,13), (10,11), (14,15), (12,16)}
A34 = {(1,5), (2,3), (4,8), (6,10), (7,11), (9,13), (14,15), (12,16)}
A35 = {(1,5), (2,3), (6,7), (4,8), (9,13), (10,14), (11,15), (12,16)}
A36 = {(1,5), (2,3), (6,7), (4,8), (9,13), (10,11), (14,15), (12,16)}

Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 569.
S. R. Finch, Mathematical Constants, Cambridge, 2003, pp. 406-412.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
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 = 0..44 (first 26 terms from T. D. Noe)
M. Aanjaneya and S. P. Pal, Faultfree tromino tilings of rectangles, arXiv:math/0610925 [math.CO], 2006.
N. Allegra, Exact solution of the 2d dimer model: Corner free energy, correlation functions and combinatorics, arXiv:1410.4131 [cond-mat.stat-mech], 2014.
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.
H. Cohn, 2-adic behavior of numbers of domino tilings, arXiv:math/0008222 [math.CO], 2000.
Steven R. Finch, The Dimer Problem [From Steven Finch, Apr 20 2019]
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.
Laura Florescu, Daniela Morar, David Perkinson, Nicholas Salter, and Tianyuan Xu, Illustration for a(2) = 36 [Fig. 9 from "Sandpiles and Dominos"]
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, Discrete Math. 216 (2000), no. 1-3, 211-219.
Adrien Kassel, Le modèle de dimères, Images des Mathématiques, CNRS, 2016. [In French]
P. W. Kasteleyn, The Statistics of Dimers on a Lattice, Physica, 27 (1961), 1209-1225.
P. W. Kasteleyn, Dimer statistics and phase transitions, J. Mathematical Phys. 4 1963 287-293. MR0153427 (27 #3394).
Viet-Ha Nguyen, Kévin Perrot, and Mathieu Vallet, NP-completeness of the game Kingdomino(TM), Theoretical Computer Science (2020) Vol. 822, 23-35. See also arXiv:1909.02849, [cs.CC], 2019.
Lior Pachter, Combinatorial approaches and conjectures ..., Elec. J. Comb. 4 (1997) #R29.
James Propp, Some 2-Adic Conjectures Concerning Polyomino Tilings of Aztec Diamonds, Integers (2023) Vol. 23, Art. A30.
Jaime Rangel-Mondragon, Polyominoes and Related Families, The Mathematica Journal, 9:3 (2005), 609-640.
N. J. A. Sloane, Illustration for a(2) = 36 [Slide from an old talk I gave]
R. P. Stanley, A combinatorial miscellany
Eric Weisstein's World of Mathematics, Domino Tiling
Eric Weisstein, Illustration for a(2) = 36, from Domino Tilings web page (see previous link) [Included with permission]
Index entries for sequences related to dominoes

Cf. A028420, A006253, A006125, A065072, A124997, A239273, A256043.

Main diagonal of array A099390 or A187596.

f := n->2^(2*n^2)*product(product(cos(i*Pi/(2*n+1))^2+cos(j*Pi/(2*n+1))^2,j=1..n),i=1..n); for k from 0 to 12 do round(evalf(f(k),300)) od;

a[n_] := Round[ N[ Product[ 2*Cos[(2i*Pi)/(2n+1)] + 2*Cos[(2j*Pi)/(2n+1)] + 4,  {i, 1, n}, {j, 1, n}], 300] ]; Table[a[n], {n, 0, 12}] (* Jean-François Alcover, Jan 04 2012, after Maple *)
Table[Sqrt[Resultant[ChebyshevU[2*n, x/2], ChebyshevU[2*n, I*x/2], x]], {n, 0, 12}] (* Vaclav Kotesovec, Dec 30 2020 *)

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

from math import isqrt
from sympy.abc import x
from sympy import I, resultant, chebyshevu
def A004003(n): return isqrt(resultant(chebyshevu(n<<1,x/2),chebyshevu(n<<1,I*x/2))) if n else 1 # Chai Wah Wu, Nov 07 2023

a(n) = A099390(2n,2n).
a(n) = Product_{j=1..n} Product_{k=1..n} (4*cos(j*Pi/(2*n+1))^2 + 4*cos(k*Pi/(2*n+1))^2). - N. J. A. Sloane, Mar 16 2015
a(n) = 2^n * A065072(n)^2. - Alois P. Heinz, Nov 22 2018
a(n)^2 = Resultant(U(2*n,x/2), U(2*n,i*x/2)), where U(n,x) is a Chebyshev polynomial of the second kind and i = sqrt(-1). - Seiichi Manyama, Apr 13 2020
a(n) ~ 2 * (sqrt(2)-1)^(2*n+1) * exp(G*(2*n+1)^2/Pi), where G is Catalan's constant A006752. - Vaclav Kotesovec, Dec 30 2020

Corrected and extended by David Radcliffe

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

Original entry on oeis.org

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

A287428 Array read by antidiagonals: T(m,n) is the number of matchings in the stacked prism graph C_m X P_n.

Original entry on oeis.org

1, 2, 3, 3, 12, 4, 5, 47, 32, 7, 8, 185, 228, 108, 11, 13, 728, 1655, 1511, 342, 18, 21, 2865, 11978, 21497, 9213, 1104, 29, 34, 11275, 86731, 305184, 253880, 57536, 3544, 47, 55, 44372, 627960, 4334009, 6974078, 3079253, 356863, 11396, 76

Offset: 1

Andrew Howroyd, May 25 2017

Row 1 is the number of matchings in P_n and row 2 is the number of matchings in G X P_n where G is a double edge. These choices give the best fit with the column linear recurrences.

			Table starts:
======================================================================
m\n|  1    2      3        4          5            6              7
---|------------------------------------------------------------------
1  |  1    2      3        5          8           13             21 ...
2  |  3   12     47      185        728         2865          11275 ...
3  |  4   32    228     1655      11978        86731         627960 ...
4  |  7  108   1511    21497     305184      4334009       61545775 ...
5  | 11  342   9213   253880    6974078    191668283     5267252351 ...
6  | 18 1104  57536  3079253  164206124   8761336545   467431319920 ...
7  | 29 3544 356863 37071837 3834744194 396924243197 41080815923665 ...
...

Andrew Howroyd, Table of n, a(n) for n = 1..435
Eric Weisstein's World of Mathematics, Stacked Prism Graph

Rows 2..13 are A088132, A033515, A033516, A033517, A033518, A033519-A033525.
Columns 2..3 are A102080, A102090.
Cf. A028420 (P_m X P_n), A270246 (C_m X C_n), A270227 (K_m X K_n).

A242861 Triangle T(n,k) by rows: number of ways k dominoes can be placed on an n X n chessboard, k>=0.

Original entry on oeis.org

1, 1, 1, 4, 2, 1, 12, 44, 56, 18, 1, 24, 224, 1044, 2593, 3388, 2150, 552, 36, 1, 40, 686, 6632, 39979, 157000, 407620, 695848, 762180, 510752, 192672, 35104, 2180, 1, 60, 1622, 26172, 281514, 2135356, 11785382, 48145820, 146702793, 333518324, 562203148

Offset: 0

Ralf Stephan, May 24 2014

Also, coefficients of the matching-generating polynomial of the n X n grid graph.

In the n-th row there are floor(n^2/2)+1 values.

			Triangle starts:
  1
  1
  1  4   2
  1 12  44   56    18
  1 24 224 1044  2593   3388   2150    552     36
  1 40 686 6632 39979 157000 407620 695848 762180 510752 192672 35104 2180
  ...

Alois P. Heinz, Rows n = 0..14, flattened
Ralf Stephan, Two dominoes on the 3x3 chessboard, illustration of T(3,2)=44.
Eric Weisstein's World of Mathematics, Grid Graph
Eric Weisstein's World of Mathematics, Matching-Generating Polynomial
Wikipedia, Matching polynomial
Index entries for sequences related to dominoes
Index entries for sequences related to matchings

Cf. A046741, A096713.

b:= proc(n, l) option remember; local k;
      if n=0 then 1
    elif min(l[])>0 then b(n-1, map(h->h-1, l))
    else for k while l[k]>0 do od; expand(`if`(n>1,
         x*b(n, subsop(k=2, l)), 0) +`if`(k (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, [0$n])):
seq(T(n), n=0..8); # Alois P. Heinz, Jun 01 2014

b[n_, l_List] := b[n, l] =  Module[{k}, Which[n == 0, 1, Min[l]>0, b[n-1, l-1], True, For[k=1, l[[k]]>0, k++]; Expand[If[n>1, x*b[n, ReplacePart[l, k -> 2]], 0] + If[k 1, k + 1 -> 1}]], 0] + b[n, ReplacePart[l, k -> 1]]]]]; T[n_] := Function[{p}, Table[Coefficient[p, x, i], {i, 0, Exponent[p, x]}]][b[n, Array[0&, n]]]; Table[T[n], {n, 0, 8}] // Flatten (* Jean-François Alcover, Jun 16 2015, after Alois P. Heinz *)

def T(n,k):
   G = Graph(graphs.Grid2dGraph(n,n))
   G.relabel()
   mu = G.matching_polynomial()
   return abs(mu[n^2-2*k])

T(n,1) = A046092(n-1), T(n,2) = A242856(n).
T(n,floor(n^2/2)) = A137308(n), T(2n,2n^2) = A004003(n).
sum(k>=0, T(n,k)) = A210662(n,n) = A028420(n).
T(n,3) = A243206(n), T(n,4) = A243215(n), T(n,5) = A243217(n), T(n,floor(n^2/4)) = A243221(n). - Alois P. Heinz, Jun 01 2014

A270228 Number of matchings in the n X n rook graph K_n X K_n.

Original entry on oeis.org

1, 7, 370, 270529, 3337807996, 855404716021831, 5352265402523357926168, 940288991338542314571521981185, 5236753179470435264288904589157765055760, 1029720447530443779943631183186535523331685533812231

Offset: 1

Andrew Howroyd, Mar 13 2016

nonn

K_n X K_n is also called the rook graph or lattice graph.

Andrew Howroyd, Table of n, a(n) for n = 1..16
Andrew Howroyd, C# software related to this sequence
Eric Weisstein's World of Mathematics, Independent Edge Set
Eric Weisstein's World of Mathematics, Matching
Eric Weisstein's World of Mathematics, Rook Graph
Wikipedia, Rook's graph, Hosoya index

Cf. A270227, A270229, A085537 (Wiener index), A002720 (independent vertex sets), A269561, A028420.

A269869 Number of matchings (not necessarily perfect) in the triangle graph of order n.

Original entry on oeis.org

1, 4, 27, 425, 14278, 1054396, 169858667, 59811185171, 46012925161519, 77344464552678876, 284066030784415134855, 2279568155737623235728996, 39969481180418160836567285156, 1531253921482570179838977438893104, 128176575381689893022287259560629125869

Offset: 1

Andrew Howroyd, Mar 06 2016

nonn

The triangle graph of order n has n rows with i vertices in row i. Each vertex is connected to the neighbors in the same row and up to two vertices in each of the neighboring rows. The graph has A000217(n) vertices and 3*A000217(n-1) edges altogether.

Samuel Dittmer, Hiram Golze, Grant Molnar, and Caleb Stanford, Puzzle and Proof: A Decade of Problems from the Utah Math Olympiad, CRC Press, 2025, p. 59.

Andrew Howroyd, Table of n, a(n) for n = 1..25
Eric Weisstein's World of Mathematics, Independent Edge Set.
Eric Weisstein's World of Mathematics, Matching.
Eric Weisstein's World of Mathematics, Triangular Grid Graph.

Cf. A000217, A028420, A039907, A112676, A178446.

Row sums of A288852.

A353777 Number of tilings of an n X n square using dominoes, monominoes and 2 X 2 tiles.

Original entry on oeis.org

1, 1, 8, 163, 15623, 5684228, 8459468955, 50280716999785, 1202536689448371122, 115462301811597894998929, 44537596159273736617786474211, 69003082378039459280864860681919942, 429429579883061866326542598342441907826951, 10734684843612889640707750537898705644071715970757

Offset: 0

Alois P. Heinz, May 07 2022

nonn

			a(2) = 8:
  .___.  .___.  .___.  .___.  .___.  .___.  .___.  .___.
  |   |  |_|_|  |___|  | | |  |_|_|  |___|  |_| |  | |_|
  |___|  |_|_|  |___|  |_|_|  |___|  |_|_|  |_|_|  |_|_| .

Alois P. Heinz, Table of n, a(n) for n = 0..17
Wikipedia, Polyomino

Main diagonal of A352589.

Cf. A004003, A028420, A063443, A219874, A219952, A219994, A220061, A220778, A233807, A270071.

a(n) = A352589(n,n).

A270247 Number of matchings in the n X n torus grid graph C_n X C_n.

Original entry on oeis.org

1, 7, 370, 41025, 15637256, 23079663560, 127193770624285, 2645142169931308801, 206932904585998805434690, 60953421285412135689567940992, 67583556205239600880061198746186383, 282092296203355454009618109524478429807744

Offset: 1

Andrew Howroyd, Mar 13 2016

nonn

C_{n} X C_{n} is also known as the (n,n)-torus grid graph.

Eric Weisstein's World of Mathematics, Matching.
Eric Weisstein's World of Mathematics, Torus Grid Graph.

Cf. A270246, A102080, A028420, A270228, A027683, A228316, A222199.

A332714 The number of placements of zero or more dominoes on the n X n grid where the number of vertical dominoes differs from the number of horizontal dominoes by at most 1.

Original entry on oeis.org

1, 5, 75, 4632, 1076492, 963182263, 3317770165381, 43809083383524391, 2209112327971366587064, 424273291301040427702718109, 309707064465485300360403957730000, 857932019835933358500355409793382735115, 9007779604382069542348587670082074125962102375

Offset: 1

Neil A. McKay, Feb 20 2020

nonn

The number of play positions of n X n Domineering. Domineering is a game in which players take turns placing dominoes on a grid, one player placing vertically and the other horizontally until the player to place cannot place a domino.

Bjorn Huntemann, Svenja Huntemann, and Neil A. McKay, SageMath code for Counting Domineering Positions
Svenja Huntemann and Neil A. McKay, Counting Domineering Positions, arXiv:1909.12419 [math.CO], 2019.

Cf. A028420 (the number of placements of dominoes on an n X n grid).

Cf. A330658, A332865.

# See Bjorn Huntemann, Svenja Huntemann, Neil A. McKay link.

a(11)-a(13) from Andrew Howroyd, Feb 20 2020

A335560 Number of ways to tile an n X n square with 1 X 1 squares and (n-1) X 1 vertical or horizontal strips.

Original entry on oeis.org

1, 16, 131, 335, 851, 2207, 5891, 16175, 45491, 130367, 378851, 1112015, 3286931, 9762527, 29091011, 86879855, 259853171, 777986687, 2330814371, 6986151695, 20945872211, 62812450847, 188387020931, 565060399535, 1694979872051, 5084536963007, 15252805582691

Offset: 1

Oluwatobi Jemima Alabi, Jun 14 2020

It is assumed that 1 X 1 squares and 1 X 1 strips can be distinguished. - Alois P. Heinz, Feb 23 2022

			Here is one of the 131 ways to tile a 3 X 3 square, in this case using two horizontal and two vertical strips:
   _ _ _
  |_ _| |
  | |_|_|
  |_|_ _|

Colin Barker, Table of n, a(n) for n = 1..1000
Index entries for linear recurrences with constant coefficients, signature (6,-11,6).

Cf. A063443 and A211348 (tiling an n X n square with smaller squares).

Cf. A028420 (tiling an n X n square with monomers and dimers).

Join[{1, 16}, LinearRecurrence[{6, -11, 6}, {131, 335, 851}, 25]] (* Amiram Eldar, Jun 16 2020 *)

Vec(x*(1 + 10*x + 46*x^2 - 281*x^3 + 186*x^4) / ((1 - x)*(1 - 2*x)*(1 - 3*x)) + O(x^30)) \\ Colin Barker, Jun 14 2020

a(n) = 2*3^n + 12*2^n - 19, for n >= 3.
From Colin Barker, Jun 14 2020: (Start)
G.f.: x*(1 + 10*x + 46*x^2 - 281*x^3 + 186*x^4) / ((1 - x)*(1 - 2*x)*(1 - 3*x)).
a(n) = 6*a(n-1) - 11*a(n-2) + 6*a(n-3) for n>5. (End)
E.g.f.: 5 - 19*exp(x) +12 *exp(2*x) + 2*exp(3*x) - 10*x - 31*x^2/2. - Stefano Spezia, Aug 25 2025

cp's OEIS Frontend

A004003 Number of domino tilings (or dimer coverings) of a 2n X 2n square.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

Extensions

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

A287428 Array read by antidiagonals: T(m,n) is the number of matchings in the stacked prism graph C_m X P_n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A242861 Triangle T(n,k) by rows: number of ways k dominoes can be placed on an n X n chessboard, k>=0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Sage

Formula

A270228 Number of matchings in the n X n rook graph K_n X K_n.

Views

Author

Keywords

Comments

Links

Crossrefs

A269869 Number of matchings (not necessarily perfect) in the triangle graph of order n.

Views

Author

Keywords

Comments

References

Links

Crossrefs

A353777 Number of tilings of an n X n square using dominoes, monominoes and 2 X 2 tiles.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A270247 Number of matchings in the n X n torus grid graph C_n X C_n.

Views

Author

Keywords

Comments

Links

Crossrefs