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,2

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.

Links

Alois P. Heinz, Rows n = 0..140, flattened

Wikipedia, Partition of a set

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

Example

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;
  ...

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

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.

Sequence in context: A188416 A361654 A160185 * A188392 A356558 A143409

Adjacent sequences: A283421 A283422 A283423 * A283425 A283426 A283427

Keyword

nonn,tabl

Author

Alois P. Heinz, May 14 2017

Status

approved