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

%I #41 Oct 03 2024 07:59:50

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

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

%U 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

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

%C Rows and also columns reversed converge to A365441.

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

%H Alois P. Heinz, <a href="/A367955/b367955.txt">Rows n = 0..50, flattened</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Partition_of_a_set">Partition of a set</a>

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

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

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

%e T(4,7) = 5: 123|4, 124|3, 13|24, 14|23, 1|2|34.

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

%e T(5,13) = 3: 1|23|4|5, 1|24|3|5, 1|25|3|4.

%e T(5,14) = 4: 12|3|4|5, 13|2|4|5, 14|2|3|5, 15|2|3|4.

%e T(5,15) = 1: 1|2|3|4|5.

%e Triangle T(n,k) begins:

%e 1;

%e . 1;

%e . . 1, 1;

%e . . . 1, 1, 2, 1;

%e . . . . 1, 1, 2, 5, 2, 3, 1;

%e . . . . . 1, 1, 2, 5, 10, 7, 7, 11, 3, 4, 1;

%e . . . . . . 1, 1, 2, 5, 10, 23, 15, 23, 25, 37, 18, 14, 19, 4, 5, 1;

%e ...

%p b:= proc(n, m) option remember; `if`(n=0, 1,

%p b(n-1, m)*m + expand(x^n*b(n-1, m+1)))

%p end:

%p T:= (n, k)-> coeff(b(n, 0), x, k):

%p seq(seq(T(n, k), k=n..n*(n+1)/2), n=0..10);

%p # second Maple program:

%p b:= proc(n, i, t) option remember; `if`(i*(i+1)/2<n, 0,

%p `if`(n=0, t^i, `if`(t=0, 0, t*b(n, i-1, t))+

%p (t+1)^max(0, 2*i-n-1)*b(n-i, min(n-i, i-1), t+1)))

%p end:

%p T:= (n, k)-> b(k, n, 0):

%p seq(seq(T(n, k), k=n..n*(n+1)/2), n=0..10);

%t 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 T[0, 0] = 1; T[n_, k_] := b[k, n, 0];

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

%Y Row sums give A000110.

%Y Column sums give A204856.

%Y Antidiagonal sums give A368102.

%Y T(2n,3n) gives A365441.

%Y T(n,2n) gives A368675.

%Y Row maxima give A367969.

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

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

%K nonn,tabf

%O 0,7

%A _Alois P. Heinz_, Dec 05 2023