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,3

Links

Table of n, a(n) for n=0..28.

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

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

Cf. A000045, A001105, A004003, A304789.

Sequence in context: A226999 A218032 A229194 * A306486 A236212 A293865

Adjacent sequences: A304787 A304788 A304789 * A304791 A304792 A304793

Keyword

nonn

Author

Alois P. Heinz, May 18 2018

Status

approved