A182099 Total area of the largest inscribed rectangles of all integer partitions of n.

0, 1, 4, 8, 18, 29, 54, 82, 136, 202, 309, 441, 658, 915, 1303, 1790, 2479, 3337, 4541, 6022, 8045, 10554, 13876, 17996, 23409, 30055, 38634, 49208, 62650, 79116, 99898, 125213, 156848, 195339, 242964, 300707, 371770, 457493, 562292, 688451, 841707, 1025484

Offset

0,3

Comments

a(n) >= A000041(n)*A061017(n) for n>0 because the least largest inscribed rectangle of any integer partition of n is A061017(n) and A000041(n) is the number of partitions of n.

a(n) >= A116503(n), the sum of the areas of the Durfee squares of all partitions of n.

Links

Alois P. Heinz, Table of n, a(n) for n = 0..175

Formula

a(n) = Sum_{k=1..n} k * A115723(n,k) for n>0, a(0) = 0.

a(n) = Sum_{k=1..n} k * (A182114(n,k) - A182114(n,k-1)).

Example

a(4) = 18 = 4+3+4+3+4 because the partitions of 4 are [1,1,1,1], [1,1,2], [2,2], [1,3], [4] and the largest inscribed rectangles have areas 4*1, 3*1, 2*2, 1*3, 1*4.
a(5) = 29 = 5+4+4+3+4+4+5 because the partitions of 5 are [1,1,1,1,1], [1,1,1,2], [1,2,2], [1,1,3], [2,3], [1,4], [5].

Maple

b:= proc(n, i, t, k) option remember; `if`(n=0, 1,
      `if`(i=1, `if`(t+n>k, 0, 1), `if`(i<1, 0, b(n, i-1, t, k)
      +add(`if`(t+j>k/i, 0, b(n-i*j, i-1, t+j, k)), j=1..n/i))))
    end:
a:= n-> add(k*(b(n, n, 0, k) -b(n, n, 0, k-1)), k=1..n):
seq(a(n), n=0..50);

Mathematica

b[n_, i_, t_, k_] := b[n, i, t, k] = If[n == 0, 1, If[i == 1, If[t + n > k, 0, 1], If[i < 1, 0, b[n, i - 1, t, k] + Sum[If[t + j > k/i, 0, b[n - i j, i - 1, t + j, k]], {j, 1, n/i}]]]];
a[n_] := Sum[k(b[n, n, 0, k] - b[n, n, 0, k - 1]), {k, 1, n}];
a /@ Range[0, 50] (* Jean-François Alcover, Dec 06 2020, after Alois P. Heinz *)

Crossrefs

Cf. A000041, A061017, A115723, A116503.

Sequence in context: A077474 A307817 A210433 * A318756 A365675 A195334

Adjacent sequences: A182096 A182097 A182098 * A182100 A182101 A182102

Keyword

nonn

Author

Alois P. Heinz, Apr 11 2012

Status

approved