cp's OEIS Frontend

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

%I A028420 #61 Feb 16 2025 08:32:35
%S A028420 1,1,7,131,10012,2810694,2989126727,11945257052321,179788343101980135,
%T A028420 10185111919160666118608,2172138783673094193937750015,
%U A028420 1743829823240164494694386437970640,5270137993816086266962874395450234534887,59956919824257750508655631107474672284499736089
%N A028420 Number of monomer-dimer tilings of n X n chessboard.
%C A028420 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
%D A028420 Steven R. Finch, Mathematical Constants, Cambridge, 2003, pp. 406-412.
%H A028420 Jennifer Henry, <a href="/A028420/b028420.txt">Table of n, a(n) for n = 0..21</a> [From S. R. Finch, Jan 30 2009]
%H A028420 J. H. Ahrens, <a href="http://dx.doi.org/10.1016/0097-3165(81)90061-3">Paving the chessboard</a>. J. Combin. Theory Ser. A 31(1981), no. 3, 277--288. MR0635371 (84d:05009). See Table I. - _N. J. A. Sloane_, Mar 27 2012
%H A028420 Steven R. Finch, <a href="http://www.people.fas.harvard.edu/~sfinch/constant/md/md.html">Two Dimensional Monomer-Dimer Constant</a> [Broken link]
%H A028420 Steven R. Finch, <a href="http://web.archive.org/web/20010608043455/http://www.mathsoft.com/asolve/constant/md/md.html">Two Dimensional Monomer-Dimer Constant</a> [From the Wayback machine] H P. Flajolet and R. Sedgewick, <a href="http://algo.inria.fr/flajolet/Publications/books.html">Analytic Combinatorics</a>, 2009; see page 362.
%H A028420 Svenja Huntemann and Neil A. McKay, <a href="https://arxiv.org/abs/1909.12419">Counting Domineering Positions</a>, arXiv:1909.12419 [math.CO], 2019.
%H A028420 David Friedhelm Kind, <a href="https://doi.org/10.13140/RG.2.2.11182.54086">The Gunport Problem: An Evolutionary Approach</a>, De Montfort University (Leicester, UK, 2020).
%H A028420 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/GridGraph.html">Grid Graph</a>
%H A028420 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/HosoyaIndex.html">Hosoya Index</a>
%H A028420 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/IndependentEdgeSet.html">Independent Edge Set</a>
%H A028420 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Matching.html">Matching</a>
%H A028420 D. Zeilberger, <a href="http://www.math.rutgers.edu/~zeilberg/tokhniot/DOMINO">Source</a>; <a href="/A028420/a028420.txt">Local copy</a>
%H A028420 <a href="/index/Do#domino">Index entries for sequences related to dominoes</a>
%p A028420 b:= proc(n, l) option remember; local k;
%p A028420       if n=0 then 1
%p A028420     elif min(l)>0 then (t-> b(n-t, map(h->h-t, l)))(min(l))
%p A028420     else for k while l[k]>0 do od; `if`(k<nops(l) and
%p A028420          l[k+1]=0, b(n, subsop(k=1, k+1=1, l)), 0)+add(
%p A028420          `if`(n<j, 0, b(n, subsop(k=j, l))), j=1..2)
%p A028420       fi
%p A028420     end:
%p A028420 a:= n-> b(n, [0$n]):
%p A028420 seq(a(n), n=0..13);  # _Alois P. Heinz_, Dec 04 2020
%t A028420 Table[With[{g = GridGraph[{n, n}]}, Count[Subsets[EdgeList[g], Length @ Flatten @ FindIndependentEdgeSet[g]], _?(IndependentEdgeSetQ[g, #] &)]], {n, 4}] (* _Eric W. Weisstein_, May 28 2017 *)
%t A028420 b[n_, l_] := b[n, l] = Module[{k}, Which[
%t A028420      n == 0, 1,
%t A028420      Min[l] > 0, Function[t, b[n-t, Map[#-t&, l]]][Min[l]],
%t A028420      True, For[k = 1, l[[k]] > 0, k++]; If[k < Length[l] &&
%t A028420           l[[k+1]] == 0, b[n, ReplacePart[l, {k -> 1, k+1 -> 1}]], 0] +
%t A028420           Sum[If[n<j, 0, b[n, ReplacePart[l, k -> j]]], {j, 1, 2}]]];
%t A028420 a[n_] := b[n, Table[0, {n}]];
%t A028420 Table[a[n], {n, 0, 13}] (* _Jean-François Alcover_, Dec 30 2021, after _Alois P. Heinz_ *)
%Y A028420 Cf. A004003. A diagonal of A210662.
%Y A028420 Row sums of A242861.
%K A028420 nonn,nice
%O A028420 0,3
%A A028420 Jennifer Henry, _Shalosh B. Ekhad_, and _Steven Finch_
%E A028420 Broken links corrected by _Steven Finch_, Jan 27 2009
%E A028420 a(0)=1 prepended by _Alois P. Heinz_, Dec 04 2020