A108458 Triangle read by rows: T(n,k) is the number of set partitions of {1,2,...,n} in which the last block is the singleton {k}, 1<=k<=n; the blocks are ordered with increasing least elements.

1, 0, 1, 0, 1, 2, 0, 1, 3, 5, 0, 1, 5, 10, 15, 0, 1, 9, 22, 37, 52, 0, 1, 17, 52, 99, 151, 203, 0, 1, 33, 130, 283, 471, 674, 877, 0, 1, 65, 340, 855, 1561, 2386, 3263, 4140, 0, 1, 129, 922, 2707, 5451, 8930, 12867, 17007, 21147, 0, 1, 257, 2572, 8919, 19921, 35098, 53411, 73681, 94828, 115975

Offset: 1

Author

Christian G. Bower, Jun 03 2005; Emeric Deutsch, Nov 14 2006

Keywords

• nonn
• tabl

Comments

Another way to obtain this sequence (with offset 0): Form the infinite array U(n,k) = number of labeled partitions of (n,k) into pairs (i,j), for n >= 0, k >= 0 and read it by antidiagonals. In other words, U(n,k) = number of partitions of n black objects labeled 1..n and k white objects labeled 1..k. Each block must have at least one white object.

Then T(n,k)=U(n+k,k+1). Thus the two versions are related like "multichoose" to "choose". - Augustine O. Munagi, Jul 16 2007

Examples

			Triangle T(n,k) starts:
  1;
  0,1;
  0,1,2;
  0,1,3,5;
  0,1,5,10,15;
T(5,3)=5 because we have 1245|3, 145|2|3, 14|25|3, 15|24|3 and 1|245|3.
The arrays U(n,k) starts:
   1  0  0   0   0 ...
   1  1  1   1   1 ...
   2  3  5   9  17 ...
   5 10 22  52 130 ...
  15 37 99 283 855 ...
		

Links

• Alois P. Heinz, Rows n = 1..141, flattened

Crossrefs

Row sums of T(n, k) yield A124496(n, 1).

Cf. A108461.

Columns of U(n, k): A000110, A005493, A033452.

Rows of U(n, k): A000007, A000012, A000051.

Main diagonal: A108459.

Programs

Mathematica

T[n_, k_] := Sum[If[n == k, 1, i^(n-k)]*StirlingS2[k, i], {i, 0, k}];
Table[T[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* Jean-François Alcover, Dec 10 2024, after Vladeta Jovovic *)

Formula

T(n,1)=0 for n>=2; T(n,2)=1 for n>=2; T(n,3)=1+2^(n-3) for n>=3; T(n,n)=B(n-1), T(n,n-1)=B(n-1)-B(n-2), where B(q) are the Bell numbers (A000110).

Double e.g.f.: exp(exp(x)*(exp(y)-1)).

U(n,k) = Sum_{i=0..k} i^(n-k)*Stirling2(k,i). - Vladeta Jovovic, Jul 12 2007

Extensions

Edited by N. J. A. Sloane, May 22 2008, at the suggestion of Vladeta Jovovic. This entry is a composite of two entries submitted independently by Christian G. Bower and Emeric Deutsch, with additional comments from Augustine O. Munagi.