A000558 -id:A000558 - cp's OEIS frontend

A039810 Matrix square of Stirling2 triangle A008277: 2-levels set partitions of [n] into k first-level subsets.

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, 5660615, 2350950, 487704, 53550, 3120, 90, 1

Offset: 1

Christian G. Bower, Feb 15 1999

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

			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)

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.
T. Mansour, A. Munagi, and M. Shattuck, Recurrence Relations and Two-Dimensional Set Partitions , J. Int. Seq. 14 (2011) # 11.4.1.

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.

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

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

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)

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

A130191 Square of the Stirling2 matrix A048993.

Original entry on oeis.org

1, 0, 1, 0, 2, 1, 0, 5, 6, 1, 0, 15, 32, 12, 1, 0, 52, 175, 110, 20, 1, 0, 203, 1012, 945, 280, 30, 1, 0, 877, 6230, 8092, 3465, 595, 42, 1, 0, 4140, 40819, 70756, 40992, 10010, 1120, 56, 1, 0, 21147, 283944, 638423, 479976, 156072, 24570, 1932, 72, 1

Offset: 0

Wolfdieter Lang, Jun 01 2007

Without row n=0 and column k=0 this is triangle A039810.
This is an associated Sheffer matrix with e.g.f. of the m-th column ((exp(f(x))-1)^m)/m! with f(x)=:exp(x)-1.
The triangle is also called the exponential Riordan array [1, exp(exp(x)-1)]. - Peter Luschny, Apr 19 2015
Also the Bell transform of shifted Bell numbers A000110(n+1). For the definition of the Bell transform see A264428. - Peter Luschny, Jan 27 2016

			Triangle starts:
  1;
  0,   1;
  0,   2,    1;
  0,   5,    6,    1;
  0,  15,   32,   12,    1;
  0,  52,  175,  110,   20,   1;
  0, 203, 1012,  945,  280,  30,  1;
  0, 877, 6230, 8092, 3465, 595, 42, 1;

G. C. Greubel, Rows n=0..100 of triangle, flattened
Marin Knežević, Vedran Krčadinac, and Lucija Relić, Matrix products of binomial coefficients and unsigned Stirling numbers, arXiv:2012.15307 [math.CO], 2020.
Wolfdieter Lang, First 10 rows and more
John Riordan, Letter, Apr 28 1976. (See third page)

Columns k=0..3 give A000007, A000110 (for n > 0), A000558, A000559.
Row sums: A000258.
Alternating row sums: A130410.
T(2n,n) gives A321712.
Cf. A039810 (another version), A048993.

# The function BellMatrix is defined in A264428.
BellMatrix(n -> combinat:-bell(n+1), 9); # Peter Luschny, Jan 27 2016

BellMatrix[f_Function, len_] := With[{t = Array[f, len, 0]}, Table[BellY[n, k, t], {n, 0, len - 1}, {k, 0, len - 1}]];
rows = 10;
M = BellMatrix[BellB[# + 1]&, rows];
Table[M[[n, k]], {n, 1, rows}, {k, 1, n}] // Flatten (* Jean-François Alcover, Jun 23 2018, after Peter Luschny *)
a[n_, m_]:= Sum[StirlingS2[n, k]*StirlingS2[k, m], {k,m,n}]; Table[a[n, m], {n, 0, 100}, {m, 0, n}]//Flatten (* G. C. Greubel, Jul 10 2018 *)

for(n=0, 9, for(k=0, n, print1(sum(j=k, n, stirling(n, j, 2)*stirling(j, k, 2)), ", "))) \\ G. C. Greubel, Jul 10 2018

# uses[riordan_array from A256893]
riordan_array(1, exp(exp(x) - 1), 8, exp=true) # Peter Luschny, Apr 19 2015

a(n,k) = Sum_{j=k..n} S2(n,j) * S2(j,k), n>=k>=0.
E.g.f. row polynomials with argument x: exp(x*f(f(z))).
E.g.f. column k: ((exp(exp(x) - 1) - 1)^k)/k!.

A341587 E.g.f.: log(1 + log(1 - x))^2 / 2.

Original entry on oeis.org

1, 6, 40, 315, 2908, 30989, 375611, 5112570, 77305024, 1286640410, 23387713930, 461187042992, 9808283703684, 223833267479764, 5456669750439788, 141540592345674800, 3892707724320135616, 113153294901088030320, 3466501398608272647984, 111636571036702743967104, 3770483138507706753943584

Offset: 2

Ilya Gutkovskiy, Feb 15 2021

nonn

Seiichi Manyama, Table of n, a(n) for n = 2..418

Cf. A000254, A000558, A003713, A008275, A039814, A052822, A302547, A302548, A341588.

nmax = 22; CoefficientList[Series[Log[1 + Log[1 - x]]^2/2, {x, 0, nmax}], x] Range[0, nmax]! // Drop[#, 2] &
Table[Sum[Abs[StirlingS1[n, k] StirlingS1[k, 2]], {k, 2, n}], {n, 2, 22}]

a(n) = Sum_{k=2..n} |Stirling1(n, k) * Stirling1(k, 2)|.
a(n) = Sum_{k=2..n} |Stirling1(n, k)| * (k-1)! * H(k-1), where H(k) is the k-th harmonic number.
a(n) = Sum_{k=1..n-1} binomial(n-1, k) * A003713(k) * A003713(n-k).
a(n) = A052822(n) / 2.
a(n) ~ sqrt(2*Pi) * log(n) * n^(n - 1/2) / (exp(1) - 1)^n * (1 + (gamma - log(exp(1) - 1))/log(n)), where gamma is the Euler-Mascheroni constant A001620. - Vaclav Kotesovec, Feb 15 2021

A000559 Generalized Stirling numbers of second kind.

Original entry on oeis.org

1, 12, 110, 945, 8092, 70756, 638423, 5971350, 57996774, 585092607, 6128147610, 66579524648, 749542556193, 8733648533696, 105203108066962, 1308549777461505, 16787682400875456, 221901108871482760, 3018891886411332135, 42230736603244134242

Offset: 3

N. J. A. Sloane

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n = 3..100
P. Blasiak, K. A. Penson and A. I. Solomon, The general boson normal ordering problem, arXiv:quant-ph/0402027, 2004.
R. Fray, A generating function associated with the generalized Stirling numbers, Fib. Quart. 5 (1967), 356-366.

Column k=3 of A130191.

Cf. A000558, A046817.

nn = 23; t = Range[0, nn]! CoefficientList[Series[1/6*(Exp[Exp[x] - 1] - 1)^3, {x, 0, nn}], x]; Drop[t, 3] (* T. D. Noe, Aug 10 2012 *)

E.g.f.: (1/3!) * (exp(exp(x) - 1) - 1)^3. - Vladeta Jovovic, Sep 28 2003

a(n) = Sum_{k=0..n} Stirling2(n,k) * Stirling2(k,3).

More terms from David W. Wilson, Jan 13 2000

A046817 Triangle of generalized Stirling numbers of 2nd kind.

Original entry on oeis.org

1, 1, 2, 1, 6, 5, 1, 12, 32, 15, 1, 20, 110, 175, 52, 1, 30, 280, 945, 1012, 203, 1, 42, 595, 3465, 8092, 6230, 877, 1, 56, 1120, 10010, 40992, 70756, 40819, 4140, 1, 72, 1932, 24570, 156072, 479976, 638423, 283944, 21147, 1, 90, 3120, 53550, 487704, 2350950, 5660615, 5971350

Offset: 0

N. J. A. Sloane

			Triangle begins:
      k = 0    1    2    3    4          sum
n
1         1                                1
2         1    2                           3
3         1    6    5                     12
4         1   12   32   15                60
5         1   20  110  175   52          358

Tilman Piesk, First 100 rows, flattened
R. Fray, A generating function associated with the generalized Stirling numbers, Fib. Quart. 5 (1967), 356-366.

Diagonals give A000558, A000559, A000110, A002378, etc.
Row sums give A000258.
Horizontal mirror triangle is A039810 (matrix square of Stirling2).

a[n_, k_] = Sum[StirlingS2[n, i]*StirlingS2[i, k], {i, k, n}]; Flatten[Table[a[n, k], {n, 1, 10}, {k, n, 1, -1}]][[1 ;; 53]]  (* Jean-François Alcover, Apr 26 2011 *)

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

E.g.f.: exp(exp(exp(x*y)-1)-1)^(1/y). - Vladeta Jovovic, Dec 14 2003

More terms from David W. Wilson, Jan 13 2000

A351513 Expansion of e.g.f. (exp(exp(exp(x)-1)-1)-1)^2 / 2.

Original entry on oeis.org

1, 9, 75, 660, 6288, 65051, 728556, 8792910, 113805204, 1572387410, 23094192960, 359209182397, 5896792771795, 101854538628396, 1846058978130172, 35021271971160507, 693843099578350329, 14326635965967487711, 307729547549467823822, 6864250658908517748384

Offset: 2

Seiichi Manyama, Feb 12 2022

nonn

Column 2 of A039811.

Cf. A000258, A000558, A351514, A351515.

my(N=40, x='x+O('x^N)); Vec(serlaplace((exp(exp(exp(x)-1)-1)-1)^2/2))

T(n, k) = if(k==0, n<=1, sum(j=0, n, stirling(n, j, 2)*T(j, k-1)));
a(n) = sum(k=1, n-1, binomial(n-1, k)*T(k, 3)*T(n-k, 3));

a(n) = Sum_{k=1..n-1} binomial(n-1,k) * A000258(k) * A000258(n-k).

A351514 Expansion of e.g.f. (exp(exp(exp(exp(x)-1)-1)-1)-1)^2 / 2.

Original entry on oeis.org

1, 12, 136, 1650, 21904, 318521, 5051988, 86910426, 1612648066, 32107793135, 682724688430, 15439016490989, 369914992674530, 9359103270641290, 249292192469843244, 6971850327184526783, 204215496402215939638, 6251233458455082035922

Offset: 2

Seiichi Manyama, Feb 12 2022

nonn

Column 2 of A039812.

Cf. A000307, A000558, A351513, A351515.

my(N=20, x='x+O('x^N)); Vec(serlaplace((exp(exp(exp(exp(x)-1)-1)-1)-1)^2/2))

T(n, k) = if(k==0, n<=1, sum(j=0, n, stirling(n, j, 2)*T(j, k-1)));
a(n) = sum(k=1, n-1, binomial(n-1, k)*T(k, 4)*T(n-k, 4));

a(n) = Sum_{k=1..n-1} binomial(n-1,k) * A000307(k) * A000307(n-k).

A351515 Expansion of e.g.f. (exp(exp(exp(exp(exp(x)-1)-1)-1)-1)-1)^2 / 2.

Original entry on oeis.org

1, 15, 215, 3325, 56605, 1060780, 21772595, 486459105, 11760431325, 305942552245, 8521928511915, 253041654671949, 7977871631560394, 266128899746035160, 9363456107172891499, 346487270686107589124, 13450341325170239245308, 546470289216642540029570

Offset: 2

Seiichi Manyama, Feb 12 2022

nonn

Column 2 of A039813.

Cf. A000357, A000558, A351513, A351514.

my(N=20, x='x+O('x^N)); Vec(serlaplace((exp(exp(exp(exp(exp(x)-1)-1)-1)-1)-1)^2/2))

T(n, k) = if(k==0, n<=1, sum(j=0, n, stirling(n, j, 2)*T(j, k-1)));
a(n) = sum(k=1, n-1, binomial(n-1, k)*T(k, 5)*T(n-k, 5));

a(n) = Sum_{k=1..n-1} binomial(n-1,k) * A000357(k) * A000357(n-k).

A341575 E.g.f.: log(1 - log(1 - x))^2 / 2.

Original entry on oeis.org

1, 0, 4, 5, 58, 217, 2035, 13470, 134164, 1243770, 14129410, 164244808, 2151576620, 29671566836, 444758323628, 7055358559376, 119546765395744, 2139179551573104, 40486788832168944, 805969129348431936, 16860672502118423136, 369459637224850523808, 8467140450141232328160

Offset: 2

Ilya Gutkovskiy, Feb 15 2021

nonn

Cf. A000254, A000558, A008275, A079642, A081048, A089064, A302547, A302548, A341587.

nmax = 24; CoefficientList[Series[Log[1 - Log[1 - x]]^2/2, {x, 0, nmax}], x] Range[0, nmax]! // Drop[#, 2] &
Table[Sum[Abs[StirlingS1[n, k]] StirlingS1[k, 2], {k, 2, n}], {n, 2, 24}]

a(n) = Sum_{k=2..n} |Stirling1(n, k)| * Stirling1(k, 2).

a(n) = (-1)^n * Sum_{k=2..n} Stirling1(n, k) * (k-1)! * H(k-1), where H(k) is the k-th harmonic number.

A052896 E.g.f.: (exp(exp(x)-1)-1)^2.

Original entry on oeis.org

0, 0, 2, 12, 64, 350, 2024, 12460, 81638, 567888, 4180848, 32470834, 265219332, 2271692124, 20350705418, 190216812260, 1850993707960, 18714559108142, 196237054861920, 2130518566431620, 23912733627261670, 277078872201375976, 3310142647325149512

Offset: 0

encyclopedia(AT)pommard.inria.fr, Jan 25 2000

Previous name was: A simple grammar.

a(n) is the number of ways to place n labeled balls into unlabeled (but two-colored) boxes so that at least one box is red and one box is blue. - Geoffrey Critzer, Oct 16 2011

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 872

Equals twice A000558.

Cf. A001861, A008277.

spec := [S,{B=Set(Z,1 <= card),C=Set(B,1 <= card),S=Prod(C,C)},labeled]: seq(combstruct[count](spec,size=n), n=0..20);

a=Exp[Exp[x]-1]; Range[0,20]! CoefficientList[Series[(a-1)^2,{x,0,20}],x]

E.g.f.: exp(exp(x)-1)^2 - 2*exp(exp(x)-1) + 1.

For n >= 1: a(n) = Sum_{k=0...n} Stirling2(n,k)*(2^k-2) where Stirling2(n,k) is the number of set partitions of {1,2,...,n} into exactly k blocks (A008277).

New name using e.g.f., Vaclav Kotesovec, Nov 20 2017

cp's OEIS Frontend

A039810 Matrix square of Stirling2 triangle A008277: 2-levels set partitions of [n] into k first-level subsets.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A130191 Square of the Stirling2 matrix A048993.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Sage

Formula

A341587 E.g.f.: log(1 + log(1 - x))^2 / 2.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A000559 Generalized Stirling numbers of second kind.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A046817 Triangle of generalized Stirling numbers of 2nd kind.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A351513 Expansion of e.g.f. (exp(exp(exp(x)-1)-1)-1)^2 / 2.

Views

Author

Keywords

Crossrefs

Programs

PARI

PARI

Formula

A351514 Expansion of e.g.f. (exp(exp(exp(exp(x)-1)-1)-1)-1)^2 / 2.

Views

Author

Keywords

Crossrefs

Programs

PARI

PARI

Formula

A351515 Expansion of e.g.f. (exp(exp(exp(exp(exp(x)-1)-1)-1)-1)-1)^2 / 2.

Views