|
%I #76 Feb 13 2022 08:34:44
%S 1,2,1,5,6,1,15,32,12,1,52,175,110,20,1,203,1012,945,280,30,1,877,
%T 6230,8092,3465,595,42,1,4140,40819,70756,40992,10010,1120,56,1,21147,
%U 283944,638423,479976,156072,24570,1932,72,1,115975,2090424,5971350,5660615,2350950,487704,53550,3120,90,1
%N Matrix square of Stirling2 triangle A008277: 2-levels set partitions of [n] into k first-level subsets.
%C 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.
%C From _Peter Bala_, Jul 19 2014: (Start)
%C 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).
%C 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)
%C 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
%C 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
%H Tilman Piesk, <a href="/A039810/b039810.txt">First 100 rows, flattened</a>
%H A. Aboud, J.-P. Bultel, A. Chouria, J.-G. Luque, and O. Mallet, <a href="http://arxiv.org/abs/1402.2960">Bell polynomials in combinatorial Hopf algebras</a>, arXiv preprint arXiv:1402.2960 [math.CO], 2014-2015.
%H T. Mansour, A. Munagi, and M. Shattuck, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL14/Mansour/mansour4.html">Recurrence Relations and Two-Dimensional Set Partitions </a>, J. Int. Seq. 14 (2011) # 11.4.1.
%F S2 = A008277 (Stirling numbers of the second kind).
%F T = (S2)^2.
%F T(n,k) = Sum_{i=k..n} S2(n,i) * S2(i,k).
%F E.g.f. of k-th column: (exp(exp(x)-1)-1)^k/k!. [corrected by _Seiichi Manyama_, Feb 12 2022]
%F From _Peter Bala_, Jul 19 2014: (Start)
%F T(n,k) = Sum_{disjoint unions X_1 U...U X_k = [n]} Bell(|X_1|)*...*Bell(|X_k|), where Bell(n) = A000110(n).
%F Recurrence equation: T(n+1,k+1) = Sum_{j = k..n} Bell(n+1-j)*binomial(n,j)* T(j,k).
%F Row sums [1,3,12,60,358,...] = A000258. (End)
%e Triangle begins:
%e k = 1 2 3 4 5 sum
%e n
%e 1 1 1
%e 2 2 1 3
%e 3 5 6 1 12
%e 4 15 32 12 1 60
%e 5 52 175 110 20 1 358
%e Matrix multiplication Stirling2 * Stirling2:
%e 1 0 0 0
%e 1 1 0 0
%e 1 3 1 0
%e 1 7 6 1
%e .
%e 1 0 0 0 1 0 0 0
%e 1 1 0 0 2 1 0 0
%e 1 3 1 0 5 6 1 0
%e 1 7 6 1 15 32 12 1
%e From _Peter Bala_, Jul 19 2014: (Start)
%e 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.
%e 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.
%e 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.
%e Hence, in total, T(5,2) = 100 + 75 = 175. (End)
%p # The function BellMatrix is defined in A264428.
%p # Adds (1,0,0,0, ..) as column 0.
%p BellMatrix(n -> combinat:-bell(n+1), 10); # _Peter Luschny_, Jan 28 2016
%t Flatten[Table[Sum[StirlingS2[n,i]*StirlingS2[i,k],{i,k,n}],{n,1,10},{k,1,n}]] (* _Indranil Ghosh_, Feb 22 2017 *)
%t rows = 10;
%t t = Table[BellB[n+1], {n, 0, rows}];
%t T[n_, k_] := BellY[n, k, t];
%t Table[T[n, k], {n, 1, rows}, {k, 1, n}] // Flatten (* _Jean-François Alcover_, Jun 22 2018, after _Peter Luschny_ *)
%o (PARI) T(n, k) = sum(j=0, n, stirling(n, j, 2)*stirling(j, k, 2)); \\ _Seiichi Manyama_, Feb 13 2022
%Y Cf. A039811, A039814, A039813 (other products of Stirling matrices).
%Y T(n, 1) = A000110(n) (first column) (Bell numbers).
%Y T(n, 2) = A000558(n) 2-levels set partitions with 2 first-level classes.
%Y 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].
%Y Sum is A000258(n), 2-levels set partitions.
%Y Another version with offset 0: A130191.
%Y Horizontal mirror triangle is A046817.
%Y T(2n,n) gives A321712.
%K nonn,tabl
%O 1,2
%A _Christian G. Bower_, Feb 15 1999
%E Definition and interpretation edited by _Olivier Gérard_, Jul 31 2011
|
