1,2

This triangle groups certain generalized Stirling numbers of the second kind A000558, A000559, ... They can also be interpreted in terms of trees of height 3 with n leaves and constraints on the order of the root.

From Peter Bala, Jul 19 2014: (Start)

The (n,k)-th entry in this table gives the number of double partitions of the set [n] = {1,2,...,n} into k blocks. To form a double partition of [n] we first write [n] as a disjoint union X_1 U...U X_k of k nonempty subsets (blocks) X_i of [n]. Then each block X_i is further partitioned into sub-blocks to give a double partition. For instance, {1,2,4} U {3,5} is a partition of [5] into 2 blocks and {{1,4},{2}} U {{3},{5}} is a refinement of this partition to a double partition of [5] into 2 blocks (and 4 sub-blocks).

Compare the above interpretation for the (n,k)-th entry of this table with the interpretation of the (n,k)-th entry of A013609 (the square of Pascal's triangle but with the rows read in reverse order) as counting the pairs (X,Y) of subsets of [n] such that |Y| = k and X is contained in Y. (End)

Also the Bell transform of the shifted Bell numbers B(n+1) without column 0. For the definition of the Bell transform see A264428. - Peter Luschny, Jan 28 2016

T(n,k) is the number of partitions of an n-set into colored blocks, such that exactly k colors are used and the colors are introduced in increasing order. T(3,2) = 6: 1a|23b, 13a|2b, 12a|3b, 1a|2a|3b, 1a|2b|3a, 1a|2b|3b. - Alois P. Heinz, Aug 27 2019

Tilman Piesk, First 100 rows, flattened

A. Aboud, J.-P. Bultel, A. Chouria, J.-G. Luque, and O. Mallet, Bell polynomials in combinatorial Hopf algebras, arXiv preprint arXiv:1402.2960 [math.CO], 2014-2015.

Peter Bala, Generalized Dobinski formulas.

T. Mansour, A. Munagi, and M. Shattuck, Recurrence Relations and Two-Dimensional Set Partitions , J. Int. Seq. 14 (2011) # 11.4.1.

S2 = A008277 (Stirling numbers of the second kind).

T = (S2)^2.

T(n,k) = Sum_{i=k..n} S2(n,i) * S2(i,k).

E.g.f. of k-th column: (exp(exp(x)-1)-1)^k/k!. [corrected by Seiichi Manyama, Feb 12 2022]

From Peter Bala, Jul 19 2014: (Start)

T(n,k) = Sum_{disjoint unions X_1 U...U X_k = [n]} Bell(|X_1|)*...*Bell(|X_k|), where Bell(n) = A000110(n).

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

Row sums [1,3,12,60,358,...] = A000258. (End)

Dobinski-type formula for the n-th row polynomial: R(n, x) = exp(-x) * Sum_{k >= 0} Bell(n, k)*x^k/k!, where Bell(n, x) denotes the n-th row polynomial of A008277. - Peter Bala, Nov 07 2025

Triangle begins:

k = 1 2 3 4 5 sum

n

1 1 1

2 2 1 3

3 5 6 1 12

4 15 32 12 1 60

5 52 175 110 20 1 358

Matrix multiplication Stirling2 * Stirling2:

1 0 0 0

1 1 0 0

1 3 1 0

1 7 6 1

.

1 0 0 0 1 0 0 0

1 1 0 0 2 1 0 0

1 3 1 0 5 6 1 0

1 7 6 1 15 32 12 1

From Peter Bala, Jul 19 2014: (Start)

T(5,2) = 175: A 5-set can be partitioned into 2 blocks as either a union of a 3-set and a 2-set or as a union of a 4-set and a singleton set.

In the first case there are 10 ways of partitioning a 5-set into a 3-set and a 2-set. Each 3-set can be further partitioned into sub-blocks in Bell(3) = 5 ways and each 2-set can be further partitioned into sub-blocks in Bell(2) = 2 ways. So altogether we obtain 10*5*2 = 100 double partitions of this type.

In the second case, there are 5 ways of partitioning a 5-set into a 4-set and a 1-set. Each 4-set can be further partitioned in Bell(4) = 15 ways and each 1-set can be further partitioned in Bell(1) = 1 way. So altogether we obtain 5*15*1 = 75 double partitions of this type.

Hence, in total, T(5,2) = 100 + 75 = 175. (End)

# The function BellMatrix is defined in A264428.

# Adds (1, 0, 0, 0, ..) as column 0.

BellMatrix(n -> combinat:-bell(n+1), 10); # Peter Luschny, Jan 28 2016

Flatten[Table[Sum[StirlingS2[n, i]*StirlingS2[i, k], {i, k, n}], {n, 1, 10}, {k, 1, n}]] (* Indranil Ghosh, Feb 22 2017 *)

rows = 10;

t = Table[BellB[n+1], {n, 0, rows}];

T[n_, k_] := BellY[n, k, t];

Table[T[n, k], {n, 1, rows}, {k, 1, n}] // Flatten (* Jean-François Alcover, Jun 22 2018, after Peter Luschny *)

(PARI) T(n, k) = sum(j=0, n, stirling(n, j, 2)*stirling(j, k, 2)); \\ Seiichi Manyama, Feb 13 2022

Cf. A039811, A039814, A039813 (other products of Stirling matrices).

T(n, 1) = A000110(n) (first column) (Bell numbers).

T(n, 2) = A000558(n) 2-levels set partitions with 2 first-level classes.

T(n, n-1) = A002378(n-1) = n*(n-1) = 2*C(n,2) = set-partitions into (n-2) singletons and one of the two possible set partitions of [2].

Sum is A000258(n), 2-levels set partitions.

Another version with offset 0: A130191.

Horizontal mirror triangle is A046817.

T(2n,n) gives A321712.

Sequence in context: A345394 A217204 A179455 * A378588 A328297 A124575

Adjacent sequences: A039807 A039808 A039809 * A039811 A039812 A039813

nonn,tabl

Christian G. Bower, Feb 15 1999

Definition and interpretation edited by Olivier Gérard, Jul 31 2011

approved