login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A039810 Matrix square of Stirling-2 Triangle A008277: 2-levels set partitions of [n] into k first-level subsets. 15
1, 2, 1, 5, 6, 1, 15, 32, 12, 1, 52, 175, 110, 20, 1, 203, 1012, 945, 280, 30, 1, 877, 6230, 8092, 3465, 595, 42, 1, 4140, 40819, 70756, 40992, 10010, 1120, 56, 1, 21147, 283944, 638423, 479976, 156072, 24570, 1932, 72, 1, 115975, 2090424, 5971350 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

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

LINKS

Tilman Piesk, First 100 rows, flattened

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

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

FORMULA

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. k-th column: (exp(exp(x)-1))^k/k!.

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)

EXAMPLE

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)

MAPLE

# 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

MATHEMATICA

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

CROSSREFS

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.

Sequence in context: A128567 A217204 A179455 * A124575 A178121 A302595

Adjacent sequences:  A039807 A039808 A039809 * A039811 A039812 A039813

KEYWORD

nonn,tabl

AUTHOR

Christian G. Bower, Feb 15 1999

EXTENSIONS

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

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 15 01:01 EST 2018. Contains 317224 sequences. (Running on oeis4.)