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

Author

Jennifer Henry, Shalosh B. Ekhad, and Steven Finch

Keywords

• nonn
• nice

Comments

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

References

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

Links

• 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

Crossrefs

Cf. A004003. A diagonal of A210662.

Row sums of A242861.

Programs

Maple

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

Mathematica

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

Extensions

Broken links corrected by Steven Finch, Jan 27 2009

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