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

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

Formula

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

Example

:   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;
  ...

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 *)

Crossrefs

Row sums give A304662.

Main diagonal and column k=0 give A000041.

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

Sequence in context: A071867 A126337 A322261 * A036355 A228390 A309256

Adjacent sequences: A304715 A304716 A304717 * A304719 A304720 A304721

Keyword

nonn,tabl

Author

Alois P. Heinz, May 17 2018

Status

approved