|
|
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..n-1} binomial(n-1,k) * Bell(k) * Bell(n-k). - 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 super-classes, 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^(k-1)-1), {k, 0, n}];
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|