login
A304790
The maximal number of different domino tilings allowed by the Ferrers-Young diagram of a single partition of 2n.
2
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,3
FORMULA
a(n) = max { k : A304789(n,k) > 0 }.
a(A001105(n)) = A004003(n).
a(n) = A000045(n+1) for n < 8.
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