A270701 Total sum T(n,k) of the sizes of all blocks with maximal element k in all set partitions of {1,2,...,n}; triangle T(n,k), n>=1, 1<=k<=n, read by rows.

1, 1, 3, 2, 4, 9, 5, 9, 16, 30, 15, 25, 41, 67, 112, 52, 82, 127, 195, 299, 463, 203, 307, 456, 670, 979, 1429, 2095, 877, 1283, 1845, 2623, 3702, 5204, 7307, 10279, 4140, 5894, 8257, 11437, 15717, 21485, 29278, 39848, 54267, 21147, 29427, 40338, 54692, 73561, 98367, 131007, 174029, 230884, 306298

Offset: 1

Author

Alois P. Heinz, Mar 21 2016

Keywords

• nonn
• tabl

Examples

			Row n=3 is [2, 4, 9] = [0+0+0+1+1, 0+2+1+0+1, 3+1+2+2+1] because the set partitions of {1,2,3} are: 123, 12|3, 13|2, 1|23, 1|2|3.
Triangle T(n,k) begins:
:     1;
:     1,    3;
:     2,    4,    9;
:     5,    9,   16,    30;
:    15,   25,   41,    67,   112;
:    52,   82,  127,   195,   299,   463;
:   203,  307,  456,   670,   979,  1429,  2095;
:   877, 1283, 1845,  2623,  3702,  5204,  7307, 10279;
:  4140, 5894, 8257, 11437, 15717, 21485, 29278, 39848, 54267;
		

Links

• Alois P. Heinz, Rows n = 1..141, flattened
• Wikipedia, Partition of a set

Crossrefs

Columns k=1-10 give: A000110(n-1), A270756, A270757, A270758, A270759, A270760, A270761, A270762, A270763, A270764.

Main and lower diagonals give: A124427, A270765, A270766, A270767, A270768, A270769, A270770, A270771, A270772, A270773.

Row sums give A070071.

Reflected triangle gives A270702.

T(2n-1,n) gives A270703.

Programs

Maple

b:= proc(n, m, t) option remember; `if`(n=0, [1, 0], add(
     `if`(t=1 and j<>m+1, 0, (p->p+`if`(j=-t or t=1 and j=m+1,
      [0, p[1]], 0))(b(n-1, max(m, j), `if`(t=1 and j=m+1, -j,
     `if`(t<0, t, `if`(t>0, t-1, 0)))))), j=1..m+1))
    end:
T:= (n, k)-> b(n, 0, max(0, 1+n-k))[2]:
seq(seq(T(n, k), k=1..n), n=1..12);

Mathematica

b[n_, m_, t_] := b[n, m, t] = If[n == 0, {1, 0}, Sum[If[t == 1 && j != m+1, 0, Function[p, p + If[j == -t || t == 1 && j == m+1, {0, p[[1]]}, 0]][b[ n-1, Max[m, j], If[t == 1 && j == m+1, -j, If[t < 0, t, If[t > 0, t-1, 0] ]]]]], {j, 1, m+1}]];
T[n_, k_] := b[n, 0, Max[0, 1+n-k]][[2]];
Table[Table[T[n, k], {k, 1, n}], {n, 1, 12}] // Flatten (* Jean-François Alcover, Apr 24 2016, translated from Maple *)

Formula

T(n,k) = A270702(n,n-k+1).