A283424 Number T(n,k) of blocks of size >= k in all set partitions of [n], assuming that every set partition contains one block of size zero; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

1, 2, 1, 5, 3, 1, 15, 10, 4, 1, 52, 37, 17, 5, 1, 203, 151, 76, 26, 6, 1, 877, 674, 362, 137, 37, 7, 1, 4140, 3263, 1842, 750, 225, 50, 8, 1, 21147, 17007, 9991, 4307, 1395, 345, 65, 9, 1, 115975, 94828, 57568, 25996, 8944, 2392, 502, 82, 10, 1

Offset: 0

Author

Alois P. Heinz, May 14 2017

Keywords

• nonn
• tabl

Comments

T(n,k) is defined for all n,k >= 0. The triangle contains only the terms with k<=n. T(n,k) = 0 for k>n.

Examples

			T(3,2) = 4 because the number of blocks of size >= 2 in all set partitions of [3] (123, 12|3, 13|2, 1|23, 1|2|3) is 1+1+1+1+0 = 4.
Triangle T(n,k) begins:
      1;
      2,     1;
      5,     3,    1;
     15,    10,    4,    1;
     52,    37,   17,    5,    1;
    203,   151,   76,   26,    6,   1;
    877,   674,  362,  137,   37,   7,  1;
   4140,  3263, 1842,  750,  225,  50,  8, 1;
  21147, 17007, 9991, 4307, 1395, 345, 65, 9, 1;
  ...
		

Links

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

Crossrefs

Columns k=0-10 give: A000110(n+1), A138378 or A005493(n-1), A124325, A288785, A288786, A288787, A288788, A288789, A288790, A288791, A288792.

Row sums give A124427(n+1).

T(2n,n) gives A286896.

Cf. A005493, A056857, A056860, A070071, A224271, A285595.

Programs

Maple

T:= proc(n, k) option remember; `if`(k>n, 0,
      binomial(n, k)*combinat[bell](n-k)+T(n, k+1))
    end:
seq(seq(T(n, k), k=0..n), n=0..14);

Mathematica

T[n_, k_] := Sum[Binomial[n, j]*BellB[j], {j, 0, n - k}];
Table[T[n, k], {n, 0, 14}, {k, 0, n}] // Flatten (* Jean-François Alcover, Apr 30 2018 *)

Formula

T(n,k) = Sum_{j=0..n-k} binomial(n,j) * Bell(j).

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

T(n,k) = Sum_{j=k..n} A056857(n+1,j) = Sum_{j=k..n} A056860(n+1,n+1-j).

Sum_{k=0..n} T(n,k) = n*Bell(n)+Bell(n+1) = A124427(n+1).

Sum_{k=1..n} T(n,k) = n*Bell(n) = A070071(n).

T(n,0)-T(n,1) = Bell(n).

Sum_{k=0..n} (-1)^k * T(n,k) = A224271(n+1). - Alois P. Heinz, May 17 2023