A304662 Total number of domino tilings of Ferrers-Young diagrams summed over all partitions of 2n.

1, 2, 6, 16, 42, 106, 268, 650, 1580, 3750, 8862, 20598, 47776, 109248, 248966, 562630, 1264780, 2823958, 6282198, 13884820, 30590124, 67051982, 146463790, 318588916, 690882926, 1492592450, 3215372064, 6904561416, 14786529836, 31574656096, 67261524262

Offset: 0

Author

Alois P. Heinz, May 16 2018

Keywords

• nonn

Examples

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

Links

• Eric Weisstein's World of Mathematics, Ferrers Diagram
• Wikipedia, Domino
• Wikipedia, Domino tiling
• Wikipedia, Ferrers diagram
• Wikipedia, Mutilated chessboard problem
• Wikipedia, Partition (number theory)
• Wikipedia, Young tableau, Diagrams
• Gus Wiseman, All 42 domino tilings of integer partitions of 8.
• Gus Wiseman, All 106 domino tilings of integer partitions of 10.
• Index entries for sequences related to dominoes

Crossrefs

Row sums of A304718.

Bisection (even part) of A304680.

Cf. A004003, A296625, A300060, A300789, A304677, A304710, A304790.

Programs

Maple

h:= proc(l, f) option remember; local k; if min(l[])>0 then
     `if`(nops(f)=0, 1, h(map(x-> x-1, l[1..f[1]]), subsop(1=[][], f)))
    else for k from nops(l) while l[k]>0 by -1 do od;
        `if`(nops(f)>0 and f[1]>=k, h(subsop(k=2, l), f), 0)+
        `if`(k>1 and l[k-1]=0, h(subsop(k=1, k-1=1, l), f), 0)
      fi
    end:
g:= l-> `if`(add(`if`(l[i]::odd, (-1)^i, 0), i=1..nops(l))=0,
        `if`(l=[], 1, h([0$l[1]], subsop(1=[][], l))), 0):
b:= (n, i, l)-> `if`(n=0 or i=1, g([l[], 1$n]), b(n, i-1, l)
                  +b(n-i, min(n-i, i), [l[], i])):
a:= n-> b(2*n$2, []):
seq(a(n), n=0..12);

Mathematica

h[l_, f_] := h[l, f] = Module[{k}, If[Min[l]>0, If[Length[f] == 0, 1, h[l[[1 ;; f[[1]]]]-1, ReplacePart[f, 1 -> Nothing]]], For[k = Length[l], l[[k]]>0, k--]; If[Length[f]>0 && f[[1]] >= k, h[ReplacePart[l, k -> 2], f], 0] + If[k>1 && l[[k-1]] == 0, h[ReplacePart[l, {k -> 1, k-1 -> 1}], f], 0]]];
g[l_] := If[Sum[If[OddQ[l[[i]]], (-1)^i, 0], {i, 1, Length[l]}] == 0, If[l == {}, 1, h[Table[0, {l[[1]]}], ReplacePart[l, 1 -> Nothing]]], 0];
b[n_, i_, l_] := If[n == 0 || i == 1, g[Join[l, Table[1, {n}]]], b[n, i-1, l] + b[n-i, Min[n-i, i], Append[l, i]]];
a[n_] := b[2n, 2n, {}];
Table[a[n], {n, 0, 12}] (* Jean-François Alcover, Aug 29 2021, after Alois P. Heinz *)

Formula

a(n) = Sum_{k=0..A304790(n)} k * A304789(n,k).

a(n) = Sum_{k=0..n} A304718(n,k).

a(n) = A296625(n) for n < 7.