A256894 Triangle read by rows, T(n,k) = Sum_{j=0..n-k+1} C(n-1,j-1)*T(n-j,k-1) if k != 0 else 1, n>=0, 0<=k<=n.

1, 1, 1, 1, 2, 1, 1, 4, 4, 1, 1, 8, 13, 7, 1, 1, 16, 40, 35, 11, 1, 1, 32, 121, 155, 80, 16, 1, 1, 64, 364, 651, 490, 161, 22, 1, 1, 128, 1093, 2667, 2751, 1316, 294, 29, 1, 1, 256, 3280, 10795, 14721, 9597, 3108, 498, 37, 1, 1, 512, 9841, 43435, 76630, 65352

Offset: 0

Author

Peter Luschny, Apr 28 2015

Keywords

• nonn
• tabl
• easy

Comments

Can be understood as a convolution matrix or as a sequence-to-triangle transformation similar to the partial Bell polynomials defined as: S -> T(n, k, S) = Sum_{j=0..n-k+1} C(n-1,j-1)*S(j)*T(n-j,k-1,S) if k != 0 else S(0)^n. Here S(n) = 1 for all n. The case S(n) = n gives the triangle of idempotent numbers A059297.

From Manfred Boergens, Mar 04 2025: (Start)

T(n,k) = number of collections of k+1 disjoint [n]-subsets covering [n], with [0]={}.

For disjoint covers (collections without an empty set) see A008277.

For non-disjoint collections see A163353.

For non-disjoint covers see A055154. (End)

Examples

			Triangle starts:
  1;
  1,  1;
  1,  2,   1;
  1,  4,   4,   1;
  1,  8,  13,   7,   1;
  1, 16,  40,  35,  11,   1;
  1, 32, 121, 155,  80,  16,  1;
  1, 64, 364, 651, 490, 161, 22, 1;
The signed version is the inverse of A326326:
   1;
  -1,   1;
   1,  -2,    1;
  -1,   4,   -4,    1;
   1,  -8,   13,   -7,    1;
  -1,  16,  -40,   35,  -11,   1;
   1, -32,  121, -155,   80, -16,   1;
  -1,  64, -364,  651, -490, 161, -22, 1. - _Peter Luschny_, Jul 02 2019
T(4,3)=7 is the number of disjoint [4]-covering collections of 4 subsets:
 {{1},{2},{3},{4}}
 {{1,2},{3},{4},{}}
 {{1,3},{2},{4},{}}
 {{1,4},{2},{3},{}}
 {{2,3},{1},{4},{}}
 {{2,4},{1},{3},{}}
 {{3,4},{1},{2},{}}. - _Manfred Boergens_, Mar 04 2025
		

Crossrefs

Row sums are A186021.

Partial row sums are A381682.

T(n+1,1) = A000079(n).

T(n+1,n) = A000124(n).

Cf. A059297, A256895, A326326.

Cf. A008277, A055154, A163353.

Programs

Maple

# Implemented as a sequence transformation acting on f: n -> 1,1,1,1,... .
F := proc(n, k, f) option remember; `if`(k=0, f(0)^n,
add(binomial(n-1,j-1)*f(j)*F(n-j,k-1,f),j=0..n-k+1)) end:
for n from 0 to 7 do seq(F(n,k,j->1), k=0..n) od;

Mathematica

Table[StirlingS2[n, m+1]+StirlingS2[n, m], {n, 0, 10}, {m, 0, n}]//Flatten (* Manfred Boergens, Mar 04 2025 *)

Formula

From Manfred Boergens, Mar 04 2025: (Start)

T(n,k) = S2(n,k) + S2(n,k+1).

T(n,k) = A008277(n,k) + A008277(n,k+1) for n>=1, k>=1. (End)