cp's OEIS Frontend

A304662 Total number of domino tilings of Ferrers-Young diagrams summed over all partitions of 2n.

%I A304662 #38 Feb 16 2025 08:33:54
%S A304662 1,2,6,16,42,106,268,650,1580,3750,8862,20598,47776,109248,248966,
%T A304662 562630,1264780,2823958,6282198,13884820,30590124,67051982,146463790,
%U A304662 318588916,690882926,1492592450,3215372064,6904561416,14786529836,31574656096,67261524262
%N A304662 Total number of domino tilings of Ferrers-Young diagrams summed over all partitions of 2n.
%H A304662 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/FerrersDiagram.html">Ferrers Diagram</a>
%H A304662 Wikipedia, <a href="https://en.wikipedia.org/wiki/Domino_(mathematics)">Domino</a>
%H A304662 Wikipedia, <a href="https://en.wikipedia.org/wiki/Domino_tiling">Domino tiling</a>
%H A304662 Wikipedia, <a href="https://en.wikipedia.org/wiki/Ferrers_diagram">Ferrers diagram</a>
%H A304662 Wikipedia, <a href="https://en.wikipedia.org/wiki/Mutilated_chessboard_problem">Mutilated chessboard problem</a>
%H A304662 Wikipedia, <a href="https://en.wikipedia.org/wiki/Partition_(number_theory)">Partition (number theory)</a>
%H A304662 Wikipedia, <a href="https://en.wikipedia.org/wiki/Young_tableau#Diagrams">Young tableau, Diagrams</a>
%H A304662 Gus Wiseman, <a href="/A304662/a304662.png">All 42 domino tilings of integer partitions of 8.</a>
%H A304662 Gus Wiseman, <a href="/A304662/a304662_1.png">All 106 domino tilings of integer partitions of 10.</a>
%H A304662 <a href="/index/Do#domino">Index entries for sequences related to dominoes</a>
%F A304662 a(n) = Sum_{k=0..A304790(n)} k * A304789(n,k).
%F A304662 a(n) = Sum_{k=0..n} A304718(n,k).
%F A304662 a(n) = A296625(n) for n < 7.
%e A304662 a(2) = 6:
%e A304662 ._.  .___.  ._._.  .___.  ._.___.  .___.___.
%e A304662 | |  |___|  | | |  |___|  | |___|  |___|___|
%e A304662 |_|  | |    |_|_|  |___|  |_|
%e A304662 | |  |_|
%e A304662 |_|
%p A304662 h:= proc(l, f) option remember; local k; if min(l[])>0 then
%p A304662      `if`(nops(f)=0, 1, h(map(x-> x-1, l[1..f[1]]), subsop(1=[][], f)))
%p A304662     else for k from nops(l) while l[k]>0 by -1 do od;
%p A304662         `if`(nops(f)>0 and f[1]>=k, h(subsop(k=2, l), f), 0)+
%p A304662         `if`(k>1 and l[k-1]=0, h(subsop(k=1, k-1=1, l), f), 0)
%p A304662       fi
%p A304662     end:
%p A304662 g:= l-> `if`(add(`if`(l[i]::odd, (-1)^i, 0), i=1..nops(l))=0,
%p A304662         `if`(l=[], 1, h([0$l[1]], subsop(1=[][], l))), 0):
%p A304662 b:= (n, i, l)-> `if`(n=0 or i=1, g([l[], 1$n]), b(n, i-1, l)
%p A304662                   +b(n-i, min(n-i, i), [l[], i])):
%p A304662 a:= n-> b(2*n$2, []):
%p A304662 seq(a(n), n=0..12);
%t A304662 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, 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 A304662 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 A304662 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 A304662 a[n_] := b[2n, 2n, {}];
%t A304662 Table[a[n], {n, 0, 12}] (* _Jean-François Alcover_, Aug 29 2021, after _Alois P. Heinz_ *)
%Y A304662 Row sums of A304718.
%Y A304662 Bisection (even part) of A304680.
%Y A304662 Cf. A004003, A296625, A300060, A300789, A304677, A304710, A304790.
%K A304662 nonn
%O A304662 0,2
%A A304662 _Alois P. Heinz_, May 16 2018