A367955 Number T(n,k) of partitions of [n] whose block maxima sum to k, triangle T(n,k), n>=0, n<=k<=n*(n+1)/2, read by rows.

1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 5, 2, 3, 1, 1, 1, 2, 5, 10, 7, 7, 11, 3, 4, 1, 1, 1, 2, 5, 10, 23, 15, 23, 25, 37, 18, 14, 19, 4, 5, 1, 1, 1, 2, 5, 10, 23, 47, 39, 49, 81, 84, 129, 74, 78, 70, 87, 33, 23, 29, 5, 6, 1, 1, 1, 2, 5, 10, 23, 47, 103, 81, 129, 172, 261, 304, 431, 299, 325, 376, 317, 424, 196, 183, 144, 165, 52, 34, 41, 6, 7, 1

Offset

0,7

Comments

Rows and also columns reversed converge to A365441.

T(n,k) is defined for all n,k >= 0. The triangle contains only the positive terms. T(n,k) = 0 if k < n or k > n*(n+1)/2.

Links

Alois P. Heinz, Rows n = 0..50, flattened

Wikipedia, Partition of a set

Formula

Sum_{k=n..n*(n+1)/2} k * T(n,k) = A278677(n+1) for n>=1.

Sum_{k=n..n*(n+1)/2} (k-n) * T(n,k) = A200660(n) for n>=1.

T(n,n) = T(n,n*(n+1)/2) = 1.

Example

T(4,7) = 5: 123|4, 124|3, 13|24, 14|23, 1|2|34.
T(5,9) = 10: 1234|5, 1235|4, 124|35, 125|34, 134|25, 135|24, 14|235, 15|234, 1|23|45, 1|245|3.
T(5,13) = 3: 1|23|4|5, 1|24|3|5, 1|25|3|4.
T(5,14) = 4: 12|3|4|5, 13|2|4|5, 14|2|3|5, 15|2|3|4.
T(5,15) = 1: 1|2|3|4|5.
Triangle T(n,k) begins:
  1;
  .  1;
  .  .  1, 1;
  .  .  .  1, 1, 2, 1;
  .  .  .  .  1, 1, 2, 5, 2,  3,  1;
  .  .  .  .  .  1, 1, 2, 5, 10,  7,  7, 11,  3,  4,  1;
  .  .  .  .  .  .  1, 1, 2,  5, 10, 23, 15, 23, 25, 37, 18, 14, 19, 4, 5, 1;
  ...

Maple

b:= proc(n, m) option remember; `if`(n=0, 1,
      b(n-1, m)*m + expand(x^n*b(n-1, m+1)))
    end:
T:= (n, k)-> coeff(b(n, 0), x, k):
seq(seq(T(n, k), k=n..n*(n+1)/2), n=0..10);
# second Maple program:
b:= proc(n, i, t) option remember; `if`(i*(i+1)/2<n, 0,
      `if`(n=0, t^i, `if`(t=0, 0, t*b(n, i-1, t))+
       (t+1)^max(0, 2*i-n-1)*b(n-i, min(n-i, i-1), t+1)))
    end:
T:= (n, k)-> b(k, n, 0):
seq(seq(T(n, k), k=n..n*(n+1)/2), n=0..10);

Mathematica

b[n_, i_, t_] := b[n, i, t] = If[i*(i + 1)/2 < n, 0, If[n == 0, t^i, If[t == 0, 0, t*b[n, i - 1, t]] + (t + 1)^Max[0, 2*i - n - 1]*b[n - i, Min[n - i, i - 1], t + 1]]];
T[0, 0] = 1; T[n_, k_] := b[k, n, 0];
Table[Table[T[n, k], {k, n, n*(n + 1)/2}], {n, 0, 10}] // Flatten (* Jean-François Alcover, Oct 03 2024, after Alois P. Heinz's second Maple program *)

Crossrefs

Row sums give A000110.

Column sums give A204856.

Antidiagonal sums give A368102.

T(2n,3n) gives A365441.

T(n,2n) gives A368675.

Row maxima give A367969.

Row n has A000124(n-1) terms (for n>=1).

Cf. A000217, A124327 (the same for block minima), A200660, A278677.

Sequence in context: A265312 A241531 A362277 * A273894 A308035 A336479

Adjacent sequences: A367952 A367953 A367954 * A367956 A367957 A367958

Keyword

nonn,tabf

Author

Alois P. Heinz, Dec 05 2023

Status

approved