login
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.
3

%I #23 Aug 29 2021 12:01:53

%S 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,

%T 15,51,109,150,150,109,51,15,22,79,206,293,380,293,206,79,22,30,126,

%U 342,590,787,787,590,342,126,30,42,189,584,1061,1675,1760,1675,1061,584,189,42

%N 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.

%H Alois P. Heinz, <a href="/A304718/b304718.txt">Rows n = 0..25, flattened</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/FerrersDiagram.html">Ferrers Diagram</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Domino_(mathematics)">Domino</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Domino_tiling">Domino tiling</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Ferrers_diagram">Ferrers diagram</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Mutilated_chessboard_problem">Mutilated chessboard problem</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Partition_(number_theory)">Partition (number theory)</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Young_tableau#Diagrams">Young tableau, Diagrams</a>

%H <a href="/index/Do#domino">Index entries for sequences related to dominoes</a>

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

%e : T(2,0) = 2 : T(2,1) = 2 : T(2,2) = 2 :

%e : ._. ._._. : .___. ._.___. : .___. .___.___. :

%e : | | | | | : |___| | |___| : |___| |___|___| :

%e : |_| |_|_| : | | |_| : |___| :

%e : | | : |_| : :

%e : |_| : : :

%e : : : :

%e Triangle T(n,k) begins:

%e 1;

%e 1, 1;

%e 2, 2, 2;

%e 3, 5, 5, 3;

%e 5, 9, 14, 9, 5;

%e 7, 18, 28, 28, 18, 7;

%e 11, 29, 63, 62, 63, 29, 11;

%e 15, 51, 109, 150, 150, 109, 51, 15;

%e 22, 79, 206, 293, 380, 293, 206, 79, 22;

%e 30, 126, 342, 590, 787, 787, 590, 342, 126, 30;

%e 42, 189, 584, 1061, 1675, 1760, 1675, 1061, 584, 189, 42;

%e ...

%p h:= proc(l, f) option remember; local k; if min(l[])>0 then

%p `if`(nops(f)=0, 1, h(map(u-> u-1, l[1..f[1]]), subsop(1=[][], f)))

%p else for k from nops(l) while l[k]>0 by -1 do od; expand(

%p `if`(nops(f)>0 and f[1]>=k, x*h(subsop(k=2, l), f), 0)+

%p `if`(k>1 and l[k-1]=0, h(subsop(k=1, k-1=1, l), f), 0))

%p fi

%p end:

%p g:= l-> `if`(add(`if`(l[i]::odd, (-1)^i, 0), i=1..nops(l))=0,

%p `if`(l=[], 1, h([0$l[1]], subsop(1=[][], l))), 0):

%p b:= (n, i, l)-> `if`(n=0 or i=1, g([l[], 1$n]), b(n, i-1, l)

%p +b(n-i, min(n-i, i), [l[], i])):

%p T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(2*n$2, [])):

%p seq(T(n), n=0..12);

%t 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]]];

%t 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];

%t 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 T[n_] := CoefficientList[b[2n, 2n, {}], x];

%t Table[T[n], {n, 0, 12}] // Flatten (* _Jean-François Alcover_, Aug 29 2021, after _Alois P. Heinz_ *)

%Y Row sums give A304662.

%Y Main diagonal and column k=0 give A000041.

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

%K nonn,tabl

%O 0,4

%A _Alois P. Heinz_, May 17 2018