

A000558


Generalized Stirling numbers of second kind.
(Formerly M4213 N1758)


11



1, 6, 32, 175, 1012, 6230, 40819, 283944, 2090424, 16235417, 132609666, 1135846062, 10175352709, 95108406130, 925496853980, 9357279554071, 98118527430960, 1065259283215810, 11956366813630835, 138539436100687988, 1655071323662574756, 20361556640795422729
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

2,2


COMMENTS

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)


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



FORMULA

a(n) = Sum_{k=0..n} Stirling2(n,k)*Stirling2(k,2).  Olivier Gérard, Mar 25 2009
a(n) = Sum_{k=1..n1} binomial(n1,k) * Bell(k) * Bell(nk).  Ilya Gutkovskiy, Feb 15 2021


EXAMPLE

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 superclasses, etc. (End)


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^(k1)1), {k, 0, n}];


CROSSREFS



KEYWORD

nonn,easy


AUTHOR



EXTENSIONS



STATUS

approved



