A304718 Number T(n,k) of domino tilings of Ferrers-Young diagrams of partitions of 2n using exactly k horizontally oriented dominoes; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

1, 1, 1, 2, 2, 2, 3, 5, 5, 3, 5, 9, 14, 9, 5, 7, 18, 28, 28, 18, 7, 11, 29, 63, 62, 63, 29, 11, 15, 51, 109, 150, 150, 109, 51, 15, 22, 79, 206, 293, 380, 293, 206, 79, 22, 30, 126, 342, 590, 787, 787, 590, 342, 126, 30, 42, 189, 584, 1061, 1675, 1760, 1675, 1061, 584, 189, 42

Offset: 0

Author

Alois P. Heinz, May 17 2018

Keywords

• nonn
• tabl

Examples

			:   T(2,0) = 2   :   T(2,1) = 2       :   T(2,2) = 2         :
:   ._.  ._._.   :   .___.  ._.___.   :   .___.  .___.___.   :
:   | |  | | |   :   |___|  | |___|   :   |___|  |___|___|   :
:   |_|  |_|_|   :   | |    |_|       :   |___|              :
:   | |          :   |_|              :                      :
:   |_|          :                    :                      :
:                :                    :                      :
Triangle T(n,k) begins:
   1;
   1,   1;
   2,   2,   2;
   3,   5,   5,    3;
   5,   9,  14,    9,    5;
   7,  18,  28,   28,   18,    7;
  11,  29,  63,   62,   63,   29,   11;
  15,  51, 109,  150,  150,  109,   51,   15;
  22,  79, 206,  293,  380,  293,  206,   79,  22;
  30, 126, 342,  590,  787,  787,  590,  342, 126,  30;
  42, 189, 584, 1061, 1675, 1760, 1675, 1061, 584, 189, 42;
  ...
		

Links

• Alois P. Heinz, Rows n = 0..25, flattened
• 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

Row sums give A304662.

Main diagonal and column k=0 give A000041.

T(n,floor(n/2)) gives A304719.

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; expand(
        `if`(nops(f)>0 and f[1]>=k, x*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])):
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(2*n$2, [])):
seq(T(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, x*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]]];
T[n_] := CoefficientList[b[2n, 2n, {}], x];
Table[T[n], {n, 0, 12}] // Flatten (* Jean-François Alcover, Aug 29 2021, after Alois P. Heinz *)

Formula

T(n,k) = T(n,n-k).