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,3

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

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<nops(l) and
         l[k+1]=0, b(n, subsop(k=1, k+1=1, l)), 0)+add(
         `if`(n<j, 0, b(n, subsop(k=j, l))), j=1..2)
      fi
    end:
a:= n-> 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, 0, b[n, ReplacePart[l, k -> 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 *)

Crossrefs

Cf. A004003. A diagonal of A210662.

Row sums of A242861.

Sequence in context: A367247 A170912 A099601 * A220257 A220321 A247597

Adjacent sequences: A028417 A028418 A028419 * A028421 A028422 A028423

Keyword

nonn,nice

Author

Jennifer Henry, Shalosh B. Ekhad, and Steven Finch

Extensions

Broken links corrected by Steven Finch, Jan 27 2009

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

Status

approved