A304789 -id:A304789 - cp's OEIS frontend

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

1, 2, 6, 16, 42, 106, 268, 650, 1580, 3750, 8862, 20598, 47776, 109248, 248966, 562630, 1264780, 2823958, 6282198, 13884820, 30590124, 67051982, 146463790, 318588916, 690882926, 1492592450, 3215372064, 6904561416, 14786529836, 31574656096, 67261524262

Offset: 0

Alois P. Heinz, May 16 2018

nonn

			a(2) = 6:
._.  .___.  ._._.  .___.  ._.___.  .___.___.
| |  |___|  | | |  |___|  | |___|  |___|___|
|_|  | |    |_|_|  |___|  |_|
| |  |_|
|_|

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
Gus Wiseman, All 42 domino tilings of integer partitions of 8.
Gus Wiseman, All 106 domino tilings of integer partitions of 10.
Index entries for sequences related to dominoes

Row sums of A304718.
Bisection (even part) of A304680.
Cf. A004003, A296625, A300060, A300789, A304677, A304710, A304790.

h:= proc(l, f) option remember; local k; if min(l[])>0 then
     `if`(nops(f)=0, 1, h(map(x-> x-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]), 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..12);

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]]];
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]]];
a[n_] := b[2n, 2n, {}];
Table[a[n], {n, 0, 12}] (* Jean-François Alcover, Aug 29 2021, after Alois P. Heinz *)

a(n) = Sum_{k=0..A304790(n)} k * A304789(n,k).
a(n) = Sum_{k=0..n} A304718(n,k).
a(n) = A296625(n) for n < 7.

A304710 Number of partitions of 2n whose Ferrers-Young diagram cannot be tiled with dominoes.

Original entry on oeis.org

0, 0, 0, 1, 2, 6, 12, 25, 46, 85, 146, 250, 410, 666, 1053, 1648, 2527, 3840, 5747, 8525, 12496, 18172, 26165, 37408, 53038, 74714, 104502, 145315, 200808, 276030, 377339, 513342, 694925, 936590, 1256670, 1679310, 2234994, 2963430, 3914701, 5153434, 6760937

Offset: 0

Alois P. Heinz, May 17 2018

nonn

Also the number of partitions of 2n where the number of odd parts in even positions differs from the number of odd parts in odd positions.

			a(3) = 1: the Ferrers-Young diagram of 321 cannot be tiled with dominoes because the numbers of white and black squares (when colored like a chessboard) are different but each domino covers exactly one white and one black square:
   ._____.
   |_|X|_|
   |X|_|
   |_|
.
a(4) = 2: 32111, 521.
a(5) = 6: 3211111, 32221, 4321, 52111, 541, 721.
a(6) = 12: 321111111, 3222111, 33321, 432111, 5211111, 52221, 54111, 543, 6321, 72111, 741, 921.

Alois P. Heinz, Table of n, a(n) for n = 0..10000
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

Column k=0 of A304789.

Cf. A000041, A000712, A058696, A144064, A182616, A304662.

b:= proc(n, i, p, c) option remember; `if`(n=0, `if`(c=0, 0, 1),
      `if`(i<1, 0, b(n, i-1, p, c)+b(n-i, min(n-i, i), -p, c+
      `if`(i::odd, p, 0))))
    end:
a:= n-> b(2*n$2, 1, 0):
seq(a(n), n=0..50);
# second Maple program:
a:= n-> (p-> p(2*n)-add(p(j)*p(n-j), j=0..n))(combinat[numbpart]):
seq(a(n), n=0..50);
# third Maple program:
b:= proc(n, k) option remember; `if`(n=0, 1, add(
      numtheory[sigma](j)*b(n-j, k), j=1..n)*k/n)
    end:
a:= n-> b(2*n, 1)-b(n, 2):
seq(a(n), n=0..50);

b[n_, i_, p_, c_] := b[n, i, p, c] = If[n == 0, If[c == 0, 0, 1], If[i < 1, 0, b[n, i - 1, p, c] + b[n - i, Min[n - i, i], -p, c + If[OddQ[i], p, 0]]]];
a[n_] := b[2n, 2n, 1, 0];
Table[a[n], {n, 0, 50}]
(* second program: *)
a[n_] := PartitionsP[2n] - Sum[PartitionsP[j]* PartitionsP[n - j], {j, 0, n}];
Table[a[n], {n, 0, 50}] (* Jean-François Alcover, Feb 13 2023, after Alois P. Heinz *)

a(n) = A058696(n) - A000712(n) = A000041(2*n) - A000712(n).
a(n) = A144064(2*n,1) - A144064(n,2).
a(n) ~ exp(2*Pi*sqrt(n/3)) / (8*sqrt(3)*n) * (1 - 2/(3^(1/4)*n^(1/4)) - (sqrt(3)/(2*Pi) + Pi/(48*sqrt(3))) / sqrt(n) + (Pi/(6*3^(3/4)) + 15*3^(1/4)/(8*Pi)) / n^(3/4)). - Vaclav Kotesovec, May 25 2018

A052837 Number of partitions of 2n whose Ferrers-Young diagram allows more than one different domino tiling.

Original entry on oeis.org

0, 0, 1, 4, 10, 22, 43, 80, 141, 240, 397, 640, 1011, 1568, 2395, 3604, 5360, 7876, 11460, 16510, 23588, 33418, 47006, 65640, 91085, 125596, 172215, 234820, 318579, 430060, 577920, 773130, 1030007, 1366644, 1806445, 2378892, 3121835, 4082796, 5322360, 6916360

Offset: 0

encyclopedia(AT)pommard.inria.fr, Jan 25 2000

The original name was: A simple grammar.

Alois P. Heinz, Table of n, a(n) for n = 0..10000
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 804

Essentially the same as A048574.

Cf. A000712, A304789.

spec := [S,{C=Sequence(Z,1 <= card),B=Set(C,1 <= card),S=Prod(B,B)},unlabeled]: seq(combstruct[count](spec,size=n), n=0..20);
# second Maple program:
a:= n-> (p-> add(p(j)*p(n-j), j=1..n-1))(combinat[numbpart]):
seq(a(n), n=0..40);  # Alois P. Heinz, May 26 2018

a[n_] := If[n <= 1, 0, With[{pp = Array[PartitionsP, n-1]},
   First[ListConvolve[pp, pp]]]];
Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Jan 30 2025 *)

G.f.: (exp(Sum_{j>=1} -x^j/((x^j-1)*j) )-1)^2.

a(n) = Sum_{k>=2} A304789(n,k). - Alois P. Heinz, May 26 2018

More terms from Franklin T. Adams-Watters, Feb 08 2006

New name from Alois P. Heinz, May 26 2018

A304790 The maximal number of different domino tilings allowed by the Ferrers-Young diagram of a single partition of 2n.

Original entry on oeis.org

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

Alois P. Heinz, May 18 2018

nonn

			a(11) = 149 different domino tilings are possible for 444442 and 6655.
a(18) = 6728 different domino tilings are possible for 666666.

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

Cf. A000045, A001105, A004003, A304789.

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

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

a(n) = max { k : A304789(n,k) > 0 }.
a(A001105(n)) = A004003(n).
a(n) = A000045(n+1) for n < 8.

cp's OEIS Frontend

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A304710 Number of partitions of 2n whose Ferrers-Young diagram cannot be tiled with dominoes.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A052837 Number of partitions of 2n whose Ferrers-Young diagram allows more than one different domino tiling.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A304790 The maximal number of different domino tilings allowed by the Ferrers-Young diagram of a single partition of 2n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula