A304790 The maximal number of different domino tilings allowed by the Ferrers-Young diagram of a single partition of 2n.

1, 1, 2, 3, 5, 8, 13, 21, 36, 55, 95, 149, 281, 430, 781, 1211, 2245, 3456, 6728, 10092, 18061, 31529, 51378, 85659, 167089, 252748, 431819, 817991, 1292697

Offset: 0

Author

Alois P. Heinz, May 18 2018

Keywords

• nonn

Examples

			a(11) = 149 different domino tilings are possible for 444442 and 6655.
a(18) = 6728 different domino tilings are possible for 666666.
		

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
• Index entries for sequences related to dominoes

Crossrefs

Cf. A000045, A001105, A004003, A304789.

Programs

Maple

h:= proc(l, f) option remember; local k; if min(l[])>0 then
     `if`(nops(f)=0, 1, h(map(u-> u-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]), max(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..15);

Mathematica

h[l_, f_] := h[l, f] = Module[{k}, If[Min[l] > 0, If[Length[f] == 0, 1, h[Map[# - 1&, l[[1 ;; f[[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}]]], Max[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, 15}] (* Jean-François Alcover, Aug 24 2021, after Alois P. Heinz *)

Formula

a(n) = max { k : A304789(n,k) > 0 }.

a(A001105(n)) = A004003(n).

a(n) = A000045(n+1) for n < 8.