A368338 Number T(n,k) of partitions of [n] whose sum of block maxima minus block minima gives k, triangle T(n,k), n>=0, 0<=k<=A002620(n), read by rows.

1, 1, 1, 1, 1, 2, 2, 1, 3, 5, 4, 2, 1, 4, 9, 12, 12, 8, 6, 1, 5, 14, 25, 34, 36, 36, 28, 18, 6, 1, 6, 20, 44, 74, 100, 122, 132, 132, 108, 78, 36, 24, 1, 7, 27, 70, 139, 224, 318, 408, 490, 534, 536, 468, 378, 258, 162, 96, 24, 1, 8, 35, 104, 237, 440, 710, 1032, 1398, 1764, 2094, 2296, 2364, 2220, 1962, 1584, 1242, 816, 528, 192, 120

Offset: 0

Author

Alois P. Heinz, Dec 21 2023

Keywords

• nonn
• tabf

Examples

			T(4,0) = 1: 1|2|3|4.
T(4,1) = 3: 12|3|4, 1|23|4, 1|2|34.
T(4,2) = 5: 123|4, 12|34, 13|2|4, 1|234, 1|24|3.
T(4,3) = 4: 1234, 124|3, 134|2, 14|2|3.
T(4,4) = 2: 13|24, 14|23.
T(5,5) = 8: 124|35, 125|34, 13|245, 13|25|4, 145|23, 15|23|4, 14|2|35, 15|2|34.
T(5,6) = 6: 134|25, 135|24, 14|235, 15|234, 14|25|3, 15|24|3.
T(6,9) = 6: 14|25|36, 14|26|35, 15|24|36, 16|24|35, 15|26|34, 16|25|34.
Triangle T(n,k) begins:
  1;
  1;
  1, 1;
  1, 2,  2;
  1, 3,  5,  4,  2;
  1, 4,  9, 12, 12,   8,   6;
  1, 5, 14, 25, 34,  36,  36,  28,  18,   6;
  1, 6, 20, 44, 74, 100, 122, 132, 132, 108, 78, 36, 24;
  ...
		

Links

• Alois P. Heinz, Rows n = 0..33, flattened
• Wikipedia, Partition of a set

Crossrefs

Columns k=0..3 give: A000012, A001477(n-1), A000096(n-2), A000297(n-4).

Row sums give A000110.

Cf. A002620, A081123, A367450, A367850, A368401.

Programs

Maple

b:= proc(n, m) option remember; `if`(n=0, x^add(-i, i=m), add(
      b(n-1, subs(j=n, m)), j=m)+expand(b(n-1, {m[], n})*x^n))
    end:
T:= (n, k)-> coeff(b(n, {}), x, k):
seq(seq(T(n, k), k=0..(h-> h*(n-h))(iquo(n, 2))), n=0..10);
# second Maple program:
b:= proc(n, s) option remember; `if`(n=0, 1, (k-> `if`(n>k,
      b(n-1, s)*(k+1), 0)+`if`(n>k+1, b(n-1, {s[], n}), 0)+
      add(expand(x^(h-n)*b(n-1, s minus {h})), h=s))(nops(s)))
    end:
T:= (n, k)-> coeff(b(n, {}), x, k):
seq(seq(T(n, k), k=0..floor(n^2/4)), n=0..10);

Formula

Sum_{k=0..A002620(n)} k * T(n,k) = A367850(n).

T(n,A002620(n)) = A081123(n+1).