A242861 -id:A242861 - cp's OEIS frontend

A028420 Number of monomer-dimer tilings of n X n chessboard.

1, 1, 7, 131, 10012, 2810694, 2989126727, 11945257052321, 179788343101980135, 10185111919160666118608, 2172138783673094193937750015, 1743829823240164494694386437970640, 5270137993816086266962874395450234534887, 59956919824257750508655631107474672284499736089

Offset: 0

Jennifer Henry, Shalosh B. Ekhad, and Steven Finch

Also the total number of matchings (not necessarily perfect ones; i.e., Hosoya index) in the n X n grid. - Andre Poenitz (poenitz(AT)htwm.de), Nov 20 2003

Steven R. Finch, Mathematical Constants, Cambridge, 2003, pp. 406-412.

Jennifer Henry, Table of n, a(n) for n = 0..21 [From S. R. Finch, Jan 30 2009]
J. H. Ahrens, 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
Steven R. Finch, Two Dimensional Monomer-Dimer Constant [Broken link]
Steven R. Finch, Two Dimensional Monomer-Dimer Constant [From the Wayback machine] H P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 362.
Svenja Huntemann and Neil A. McKay, Counting Domineering Positions, arXiv:1909.12419 [math.CO], 2019.
David Friedhelm Kind, The Gunport Problem: An Evolutionary Approach, De Montfort University (Leicester, UK, 2020).
Eric Weisstein's World of Mathematics, Grid Graph
Eric Weisstein's World of Mathematics, Hosoya Index
Eric Weisstein's World of Mathematics, Independent Edge Set
Eric Weisstein's World of Mathematics, Matching
D. Zeilberger, Source; Local copy
Index entries for sequences related to dominoes

Cf. A004003. A diagonal of A210662.

Row sums of A242861.

b:= proc(n, l) option remember; local k;
      if n=0 then 1
    elif min(l)>0 then (t-> b(n-t, map(h->h-t, l)))(min(l))
    else for k while l[k]>0 do od; `if`(k b(n, [0$n]):
seq(a(n), n=0..13);  # Alois P. Heinz, Dec 04 2020

Table[With[{g = GridGraph[{n, n}]}, Count[Subsets[EdgeList[g], Length @ Flatten @ FindIndependentEdgeSet[g]], ?(IndependentEdgeSetQ[g, #] &)]], {n, 4}] (* _Eric W. Weisstein, May 28 2017 *)
b[n_, l_] := b[n, l] = Module[{k}, Which[
     n == 0, 1,
     Min[l] > 0, Function[t, b[n-t, Map[#-t&, l]]][Min[l]],
     True, For[k = 1, l[[k]] > 0, k++]; If[k < Length[l] &&
          l[[k+1]] == 0, b[n, ReplacePart[l, {k -> 1, k+1 -> 1}]], 0] +
          Sum[If[n j]]], {j, 1, 2}]]];
a[n_] := b[n, Table[0, {n}]];
Table[a[n], {n, 0, 13}] (* Jean-François Alcover, Dec 30 2021, after Alois P. Heinz *)

Broken links corrected by Steven Finch, Jan 27 2009

a(0)=1 prepended by Alois P. Heinz, Dec 04 2020

A243424 Triangle T(n,k) read by rows of number of ways k domicules can be placed on an n X n square (n >= 0, 0 <= k <= floor(n^2/2)).

Original entry on oeis.org

1, 1, 1, 6, 3, 1, 20, 110, 180, 58, 1, 42, 657, 4890, 18343, 33792, 27380, 7416, 280, 1, 72, 2172, 36028, 362643, 2307376, 9382388, 24121696, 37965171, 34431880, 16172160, 3219364, 170985, 1, 110, 5375, 154434, 2911226, 38049764, 355340561, 2408715568

Offset: 0

Alois P. Heinz, Jun 04 2014

A domicule is either a domino or it is formed by the union of two neighboring unit squares connected via their corners. In a tiling the connections of two domicules are allowed to cross each other.

The n-th row gives the coefficients of the matching-generating polynomial of the n X n king graph. - Eric W. Weisstein, Jun 20 2017

			T(2,1) = 6:
  +---+  +---+  +---+  +---+  +---+  +---+
  |o-o|  |   |  |o  |  |  o|  |o  |  |  o|
  |   |  |   |  ||  |  |  ||  | \ |  | / |
  |   |  |o-o|  |o  |  |  o|  |  o|  |o  |
  +---+  +---+  +---+  +---+  +---+  +---+
T(2,2) = 3:
  +---+  +---+  +---+
  |o-o|  |o o|  |o o|
  |   |  || ||  | X |
  |o-o|  |o o|  |o o|
  +---+  +---+  +---+
Triangle T(n,k) begins:
  1;
  1;
  1,  6,    3;
  1, 20,  110,   180,     58;
  1, 42,  657,  4890,  18343,   33792,   27380,     7416,      280;
  1, 72, 2172, 36028, 362643, 2307376, 9382388, 24121696, 37965171, ...
  ...

Alois P. Heinz, Rows n = 0..13, flattened
Eric Weisstein's World of Mathematics, King Graph
Eric Weisstein's World of Mathematics, Matching-Generating Polynomial

Columns k=0-5 give: A000012, A002943(n-1) for n>0, A243464, A243465, A243466, A243467.
Row sums give A220638.
T(n,floor(n^2/2)) gives A243510.
T(n,floor(n^2/4)) gives A243511.
Cf. A242861 (the same for dominoes), A239264.

b:= proc(n, l) option remember; local d, f, k;
      d:= nops(l)/2; f:=false;
      if n=0 then 1
    elif l[1..d]=[f$d] then b(n-1, [l[d+1..2*d][], true$d])
    else for k to d while not l[k] do od;
         expand(b(n, subsop(k=f, l))+
         `if`(k1 and l[k+d+1],
                            x*b(n, subsop(k=f, k+d+1=f, l)), 0)+
         `if`(k>1 and n>1 and l[k+d-1],
                            x*b(n, subsop(k=f, k+d-1=f, l)), 0)+
         `if`(n>1 and l[k+d], x*b(n, subsop(k=f, k+d=f, l)), 0)+
         `if`(k (p-> seq(coeff(p,x,i), i=0..degree(p)))(b(n, [true$(n*2)])):
seq(T(n), n=0..7);

b[n_, l_] := b[n, l] = Module[{d, f, k}, d = Length[l]/2; f = False; Which[ n == 0, 1, l[[1 ;; d]] == Table[f, d], b[n-1, Join[l[[d+1 ;; 2d]], Table[ True, d]]], True, For[k = 1, !l[[k]], k++]; Expand[b[n, ReplacePart[l, k -> f]] + If[k1 && l[[k+d+1]], x*b[n, ReplacePart[l, {k -> f, k + d + 1 -> f}]], 0] + If[k>1 && n>1 && l[[k + d - 1]], x*b[n, ReplacePart[ l, {k -> f, k + d - 1 -> f}]], 0] + If[n>1 && l[[k + d]], x*b[n, ReplacePart[l, {k -> f, k+d -> f}]], 0] + If[k f, k+1 -> f}]], 0]]]];
T[n_] := Function[p, Table[Coefficient[p, x, i], {i, 0, Exponent[p, x]}]][
  b[n, Table[True, 2n]]];
Table[T[n], {n, 0, 7}] // Flatten (* Jean-François Alcover, Jun 09 2018, after Alois P. Heinz *)

A242856 Number of 2-matchings of the n X n grid graph.

Original entry on oeis.org

2, 44, 224, 686, 1622, 3272, 5924, 9914, 15626, 23492, 33992, 47654, 65054, 86816, 113612, 146162, 185234, 231644, 286256, 349982, 423782, 508664, 605684, 715946, 840602, 980852, 1137944, 1313174, 1507886, 1723472, 1961372, 2223074, 2510114, 2824076, 3166592

Offset: 2

Ralf Stephan, May 24 2014

Number of ways two dominoes can be placed on an n X n chessboard.

Alois P. Heinz, Table of n, a(n) for n = 2..1000
Ralf Stephan, In how many ways can we place two dominoes on the n x n chessboard? Proof of formula.
Ralf Stephan, Two dominoes on the 3x3 chessboard, illustration of a(3)=44.
Index entries for sequences related to dominoes.
Index entries for sequences related to matchings.
Index entries for linear recurrences with constant coefficients, signature (5,-10,10,-5,1).

Second column of A242861. Cf. A016742, A046092, A054000, A210662.

LinearRecurrence[{5, -10, 10, -5, 1}, {2, 44, 224, 686, 1622}, 50] (* Paolo Xausa, May 20 2024 *)

Vec(-2*x^2*(x^4-7*x^3+12*x^2+17*x+1)/(x-1)^5 + O(x^100)) \\ Colin Barker, Jun 26 2014

def a(n):
    G = Graph(graphs.Grid2dGraph(n,n))
    G.relabel()
    return G.matching_polynomial()[n^2-4]

a(n) = 2*n^4 - 4*n^3 - 5*n^2 + 13*n - 4.
G.f.: -2*x^2*(x^4-7*x^3+12*x^2+17*x+1) / (x-1)^5. - Colin Barker, Jun 26 2014
a(n + 1) = (1/2)*A046092(n)*(A046092(n) - 1) - A016742(n) - A054000(n). - Nicolas Bělohoubek, May 15 2024
E.g.f.: 4 - 2*x + exp(x)*(2*x^4 + 8*x^3 - 3*x^2 + 6*x - 4). - Stefano Spezia, Jun 04 2024

a(7)-a(36) from Alois P. Heinz, Jun 01 2014

A287595 Number of maximal matchings in the n X n grid graph.

Original entry on oeis.org

1, 1, 2, 22, 400, 22228, 3136370, 1158560776, 1147204164108, 2980178704765860, 20513821200001569410, 373243563814532182524614, 17941038966060235808302667164

Offset: 0

Eric W. Weisstein, May 27 2017

Svenja Huntemann and Neil A. McKay, Counting Domineering Positions, arXiv:1909.12419 [math.CO], 2019.
Eric Weisstein's World of Mathematics, Grid Graph
Eric Weisstein's World of Mathematics, Independent Edge Set
Eric Weisstein's World of Mathematics, Matching
Eric Weisstein's World of Mathematics, Maximal Independent Edge Set

Main diagonal of A288026.

Cf. A286945, A288028, A099390, A242861, A284703.

Join[{1}, Table[Length@FindIndependentVertexSet[LineGraph@GridGraph[{n, n}], Infinity, All], {n, 2, 6}]] (* Eric W. Weisstein, Jul 13 2024 *)

a(7)-a(10) from Andrey Zabolotskiy, May 31 2017
a(1) changed and a(0) prepended by Alois P. Heinz, May 31 2017
a(11)-a(12) from Andrew Howroyd, Jun 04 2017

A137308 Number of dimer coverings on n X n square if n is even; number of dimer arrangements with exactly one monomer if n is odd.

Original entry on oeis.org

1, 1, 2, 18, 36, 2180, 6728, 2200776, 12988816, 20355006224, 258584046368, 1801272981919008, 53060477521960000, 1560858753560238398528, 112202208776036178000000, 13428038397958481723104394368

Offset: 0

Steven Finch, Apr 03 2008

nonn

Subsequence of even-subscripted terms is A004003.
Rightmost diagonal of A242861.
Also the number of maximum matchings in the n X n grid graph. - Eric W. Weisstein, May 28 2017

Y. Kong, Packing dimers on (2p+1) X (2q+1) lattices, Phys. Rev. E 73 (2006) 016106

Steven Finch, Table of n, a(n) for n = 0..19
Eric Weisstein's World of Mathematics, Grid Graph
Eric Weisstein's World of Mathematics, Matching
Eric Weisstein's World of Mathematics, Maximum Independent Edge Set

Cf. A004003, A242861.

a(0)=1 prepended by Alois P. Heinz, Aug 15 2021

A243206 Number of 3-matchings of the n X n grid graph.

Original entry on oeis.org

0, 0, 0, 56, 1044, 6632, 26172, 78536, 196916, 434584, 871612, 1622552, 2845076, 4749576, 7609724, 11773992, 17678132, 25858616, 36967036, 51785464, 71242772, 96431912, 128628156, 169308296, 220170804, 283156952, 360472892, 454612696, 568382356, 704924744

Offset: 0

Alois P. Heinz, Jun 01 2014

nonn

Number of ways 3 dominoes can be placed on an n X n chessboard.

Alois P. Heinz, Table of n, a(n) for n = 0..1000

Column k=3 of A242861.

a:= n-> `if`(n<3, 0, ((((((4*n-12)*n-30)*n+116)*n+14)*n-272)*n+156)/3):
seq(a(n), n=0..40);

G.f.: 4*x^3*(-14-163*x-125*x^2-5*x^5-6*x^4+72*x^3+x^6)/(x-1)^7.

a(n) = (4*n^6-12*n^5-30*n^4+116*n^3+14*n^2-272*n+156)/3 for n>=3, a(n) = 0 for n<3.

A243215 Number of 4-matchings of the n X n grid graph.

Original entry on oeis.org

0, 0, 0, 18, 2593, 39979, 281514, 1301950, 4618099, 13628193, 35115244, 81502564, 174076485, 347418199, 655313518, 1178436234, 2034127639, 3388621645, 5472091824, 8596923568, 13179641449, 19766948739, 29066362930, 41981957974, 59655750843, 83515296889

Offset: 0

Alois P. Heinz, Jun 01 2014

nonn

Number of ways 4 dominoes can be placed on an n X n chessboard.

Alois P. Heinz, Table of n, a(n) for n = 0..1000

Column k=4 of A242861.

a:= n-> `if`(n<4, [0$3, 18][n+1], ((((((((4*n-16)*n-60)
       *n+308)*n+171)*n-1942)*n+872)*n+3963)*n-3366)/6):
seq(a(n), n=0..40);

G.f.: -(6*x^9 -14*x^8 -155*x^7 +474*x^6 +1267*x^5 -7976*x^4 +13539*x^3 +17290*x^2 +2431*x +18)*x^3 / (x-1)^9.

a(n) = (4*n^8 -16*n^7 -60*n^6 +308*n^5 +171*n^4 -1942*n^3 +872*n^2 +3963*n -3366)/6 for n>=4, a(3) = 18, a(n) = 0 for n<=2.

A243217 Number of 5-matchings of the n X n grid graph.

Original entry on oeis.org

0, 0, 0, 0, 3388, 157000, 2135356, 15836664, 81324796, 325679904, 1088989348, 3174085648, 8301786980, 19888285976, 44304931948, 92833927816, 184597383660, 350812701616, 640815379476, 1130391980512, 1933082192404, 3215240556392, 5215796556572, 8271817286296

Offset: 0

Alois P. Heinz, Jun 01 2014

nonn

Number of ways 5 dominoes can be placed on an n X n chessboard.

Alois P. Heinz, Table of n, a(n) for n = 0..1000

Column k=5 of A242861.

a:= n-> `if`(n<5, [0$4, 3388][n+1], ((((((((((4*n-20)*n-100)*n+640)
    *n+635)*n-7589)*n+2370)*n+39275)*n-35789)*n-74246)*n+86580)/15):
seq(a(n), n=0..40);

G.f.: 4*(2*x^11 -6*x^10 +17*x^9 -559*x^8 +3298*x^7 -5840*x^6 -8668*x^5 +55222*x^4 -105932*x^3 -148674*x^2 -29933*x -847)*x^4 / (x-1)^11.

a(n) = (4*n^10 -20*n^9 -100*n^8 +640*n^7 +635*n^6 -7589*n^5 +2370*n^4 +39275*n^3 -35789*n^2 -74246*n +86580)/15 for n>=5, a(4) = 3388, a(n) = 0 for n<=3.

A243221 Number of quarter-square matchings of the n X n grid graph.

Original entry on oeis.org

1, 1, 4, 44, 2593, 407620, 333518324, 696849783788, 7561681603209033, 204785162442300693673, 28874426647917459828127044, 10023323177854055068860282476760, 18172145684566998309243670369029131178, 80387219406473992671391703779030095453926416

Offset: 0

Alois P. Heinz, Jun 01 2014

nonn

Number of ways floor(n^2/4) dominoes can be placed on an n X n chessboard. a(n) is the central term in the n-th row of A242861.

Alois P. Heinz, Table of n, a(n) for n = 0..14

Cf. A002620, A242861.

a(n) = A242861(n,floor(n^2/4)) = A242861(n,A002620(n)).

A242983 n/2 * (n^3 - 2n^2 - 2n + 5).

Original entry on oeis.org

0, 1, 1, 12, 58, 175, 411, 826, 1492, 2493, 3925, 5896, 8526, 11947, 16303, 21750, 28456, 36601, 46377, 57988, 71650, 87591, 106051, 127282, 151548, 179125, 210301, 245376, 284662, 328483, 377175, 431086, 490576, 556017

Offset: 0

Ralf Stephan, Jun 09 2014

For n>1, number of ways to place two dominoes horizontally on an n X n chessboard.

Index entries for sequences related to dominoes
Index entries for linear recurrences with constant coefficients, signature (5,-10,10,-5,1).

Cf. A242856, A242861.

Table[n/2 (n^3-2n^2-2n+5),{n,0,40}] (* or *) LinearRecurrence[{5,-10,10,-5,1},{0,1,1,12,58},40] (* Harvey P. Dale, Jul 19 2018 *)

a(n) = A019582(n) + A077414(n-2), n>1.

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

cp's OEIS Frontend

A028420 Number of monomer-dimer tilings of n X n chessboard.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A243424 Triangle T(n,k) read by rows of number of ways k domicules can be placed on an n X n square (n >= 0, 0 <= k <= floor(n^2/2)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A242856 Number of 2-matchings of the n X n grid graph.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Sage

Formula

Extensions

A287595 Number of maximal matchings in the n X n grid graph.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Extensions

A137308 Number of dimer coverings on n X n square if n is even; number of dimer arrangements with exactly one monomer if n is odd.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Extensions

A243206 Number of 3-matchings of the n X n grid graph.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Formula

A243215 Number of 4-matchings of the n X n grid graph.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Formula

A243217 Number of 5-matchings of the n X n grid graph.

Views

Author

Keywords

Comments

A242983 n/2 * (n^3 - 2n^2 - 2n + 5).