A285595 Sum T(n,k) of the k-th entries in all blocks of all set partitions of [n]; triangle T(n,k), n>=1, 1<=k<=n, read by rows.

1, 4, 2, 17, 10, 3, 76, 52, 18, 4, 362, 274, 111, 28, 5, 1842, 1500, 675, 200, 40, 6, 9991, 8614, 4185, 1380, 325, 54, 7, 57568, 51992, 26832, 9568, 2510, 492, 70, 8, 351125, 329650, 178755, 67820, 19255, 4206, 707, 88, 9, 2259302, 2192434, 1239351, 494828, 149605, 35382, 6629, 976, 108, 10

Offset: 1

Author

Alois P. Heinz, Apr 22 2017

Keywords

• nonn
• tabl

Comments

T(n,k) is also k times the number of blocks of size >k in all set partitions of [n+1]. T(3,2) = 10 = 2 * 5 because there are 5 blocks of size >2 in all set partitions of [4], namely in 1234, 123|4, 124|3, 134|2, 1|234.

Examples

			T(3,2) = 10 because the sum of the second entries in all blocks of all set partitions of [3] (123, 12|3, 13|2, 1|23, 1|2|3) is 2+2+3+3+0  = 10.
Triangle T(n,k) begins:
      1;
      4,     2;
     17,    10,     3;
     76,    52,    18,    4;
    362,   274,   111,   28,    5;
   1842,  1500,   675,  200,   40,   6;
   9991,  8614,  4185, 1380,  325,  54,  7;
  57568, 51992, 26832, 9568, 2510, 492, 70, 8;
  ...
		

Links

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

Crossrefs

Column k=1 gives A124325(n+1).

Row sums give A000110(n) * A000217(n) = A105488(n+3).

Main diagonal and first lower diagonal give: A000027, A028552.

Cf. A007318, A175757, A278677, A283424, A285362, A285793, A286897.

Programs

Maple

T:= proc(h) option remember; local b; b:=
      proc(n, l) option remember; `if`(n=0, [1, 0],
        (p-> p+[0, (h-n+1)*p[1]*x^1])(b(n-1, [l[], 1]))+
         add((p-> p+[0, (h-n+1)*p[1]*x^(l[j]+1)])(b(n-1,
         sort(subsop(j=l[j]+1, l), `>`))), j=1..nops(l)))
      end: (p-> seq(coeff(p, x, i), i=1..n))(b(h, [])[2])
    end:
seq(T(n), n=1..12);
# second Maple program:
b:= proc(n) option remember; `if`(n=0, [1, 0],
      add((p-> p+[0, p[1]*add(x^k, k=1..j-1)])(
         b(n-j)*binomial(n-1, j-1)), j=1..n))
    end:
T:= n-> (p-> seq(coeff(p, x, i)*i, i=1..n))(b(n+1)[2]):
seq(T(n), n=1..12);

Mathematica

b[n_] := b[n] = If[n == 0, {1, 0}, Sum[# + {0, #[[1]]*Sum[x^k, {k, 1, j-1} ]}&[b[n - j]*Binomial[n - 1, j - 1]], {j, 1, n}]];
T[n_] := Table[Coefficient[#, x, i]*i, {i, 1, n}] &[b[n + 1][[2]]];
Table[T[n], {n, 1, 12}] // Flatten (* Jean-François Alcover, May 23 2018, translated from 2nd Maple program *)

Formula

T(n,k) = k * Sum_{j=k+1..n+1} binomial(n+1,j)*A000110(n+1-j).

T(n,k) = k * Sum_{j=k+1..n+1} A175757(n+1,j).

Sum_{k=1..n} T(n,k)/k = A278677(n-1).