OFFSET
0,3
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
FORMULA
EXAMPLE
a(11) = 149 different domino tilings are possible for 444442 and 6655.
a(18) = 6728 different domino tilings are possible for 666666.
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 *)
CROSSREFS
KEYWORD
nonn
AUTHOR
Alois P. Heinz, May 18 2018
STATUS
approved