A000558 Generalized Stirling numbers of second kind.

1, 6, 32, 175, 1012, 6230, 40819, 283944, 2090424, 16235417, 132609666, 1135846062, 10175352709, 95108406130, 925496853980, 9357279554071, 98118527430960, 1065259283215810, 11956366813630835, 138539436100687988, 1655071323662574756, 20361556640795422729

Offset: 2

Author

N. J. A. Sloane

Keywords

• nonn
• easy

Comments

From Olivier Gérard, Mar 25 2009: (Start)

a(n) is the number of hierarchical partitions of a set of n elements into two second level classes : k>1 subsets of [n] are further grouped in two classes.

a(n) is equivalently the number of trees of uniform height 3 with n labeled leaves, and a root of order two. (End)

Examples

			From _Olivier Gérard_, Mar 25 2009: (Start)
a(2) = 1, since there is only one partition of {1,2} into two classes, and only one way to partition those classes.
a(4) = 32 = 7*1 + 6*3 + 1*7 since there are 7 ways of partitioning {1,2,3,4} into two classes (which cannot be grouped further), 6 ways of partitioning a set of 4 elements into three classes and three ways to partition three classes into two super-classes, etc. (End)
		

References

• 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).

Links

• T. D. Noe, Table of n, a(n) for n = 2..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.

Crossrefs

Column k=2 of A130191.

Cf. A000110, A000559, A046817.

Cf. A001861 for the related bicolor set partitions. - Olivier Gérard, Mar 25 2009

Programs

Mathematica

nn = 22; t = Range[0, nn]! CoefficientList[Series[1/2*(Exp[Exp[x] - 1] - 1)^2, {x, 0, nn}], x]; Drop[t, 2] (* T. D. Noe, Aug 10 2012 *)
a[n_] := Sum[StirlingS2[n, k] (2^(k-1)-1), {k, 0, n}];
a /@ Range[2, 100] (* Jean-François Alcover, Mar 30 2021 *)

Formula

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

a(n) = Sum_{k=0..n} Stirling2(n,k) * Stirling2(k,2). - Olivier Gérard, Mar 25 2009

a(n) = Sum_{k=1..n-1} binomial(n-1,k) * Bell(k) * Bell(n-k). - Ilya Gutkovskiy, Feb 15 2021

Extensions

More terms from David W. Wilson, Jan 13 2000