%I M4213 N1758 #51 Dec 19 2021 11:21:41

%S 1,6,32,175,1012,6230,40819,283944,2090424,16235417,132609666,

%T 1135846062,10175352709,95108406130,925496853980,9357279554071,

%U 98118527430960,1065259283215810,11956366813630835,138539436100687988,1655071323662574756,20361556640795422729

%N Generalized Stirling numbers of second kind.

%C From _Olivier Gérard_, Mar 25 2009: (Start)

%C 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.

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

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

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

%H T. D. Noe, <a href="/A000558/b000558.txt">Table of n, a(n) for n = 2..100</a>

%H P. Blasiak, K. A. Penson and A. I. Solomon, <a href="http://www.arXiv.org/abs/quant-ph/0402027">The general boson normal ordering problem</a>, arXiv:quant-ph/0402027, 2004.

%H R. Fray, <a href="http://www.fq.math.ca/Scanned/5-4/fray.pdf">A generating function associated with the generalized Stirling numbers</a>, Fib. Quart. 5 (1967), 356-366.

%F E.g.f.: (1/2)*(exp(exp(x)-1)-1)^2. - _Vladeta Jovovic_, Sep 28 2003

%F a(n) = Sum_{k=0..n} Stirling2(n,k)*Stirling2(k,2). - _Olivier Gérard_, Mar 25 2009

%F a(n) = Sum_{k=1..n-1} binomial(n-1,k) * Bell(k) * Bell(n-k). - _Ilya Gutkovskiy_, Feb 15 2021

%e From _Olivier Gérard_, Mar 25 2009: (Start)

%e a(2) = 1, since there is only one partition of {1,2} into two classes, and only one way to partition those classes.

%e 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)

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

%t a[n_] := Sum[StirlingS2[n, k] (2^(k-1)-1), {k, 0, n}];

%t a /@ Range[2, 100] (* _Jean-François Alcover_, Mar 30 2021 *)

%Y Cf. A000110, A000559, A046817.

%Y Cf. A001861 for the related bicolor set partitions. - _Olivier Gérard_, Mar 25 2009

%K nonn,easy

%O 2,2

%A _N. J. A. Sloane_

%E More terms from _David W. Wilson_, Jan 13 2000