OFFSET
1,2
LINKS
Vaclav Kotesovec, Table of n, a(n) for n = 1..420 (first 160 terms from Alois P. Heinz)
Thomas Wieder, The number of certain rankings and hierarchies formed from labeled or unlabeled elements and sets, Applied Mathematical Sciences, vol. 3, 2009, no. 55, 2707 - 2724. [Thomas Wieder, Nov 14 2009]
FORMULA
Stirling transform of A005651 = Sum of multinomial coefficients: a(n) = Sum_{i=1..n} S2(n,k) A005651(k).
E.g.f.: 1/Product_{k>=1} (1 - (exp(x)-1)^k/k!). - Thomas Wieder, Sep 04 2008
a(n) ~ c * n! / (log(2))^n, where c = 1/(2*log(2)) * Product_{k>=2} 1/(1-1/k!) = A247551 / (2*log(2)) = 1.82463230250447246267598544320244231645906135137... . - Vaclav Kotesovec, Sep 04 2014, updated Jan 21 2017
EXAMPLE
We are considering all set partitions of the n-set {1,2,3,...,n}.
For each such set partition we examine all possible hierarchical arrangements of the subsets. A hierarchy is a distribution of elements (sets in the present case) onto levels.
A distribution onto levels is "hierarchical" if a level L+1 contains at most as many elements as level L. Thus for n=4 the arrangement {1,2}:{3}{4} is not allowed.
Let the colon ":" separate two consecutive levels L and L+1.
n=2 --> 1+3=4
{1,2} {1}{2}
{1}:{2}
{2}:{1}
-----------------------
n=3 --> 1+9+10=20
1*1 3*3=9 1*10
{1,2,3} {1,2}{3} {1}{2}{3}
{1,3}{2}
{2,3}{1} {1}{2}:{3}
{3}{1}:{2}
{1,2}:{3} {2}{3}:{1}
{1,3}:{2}
{2,3}:{1} {1}:{2}:{3}
{3}:{1}:{2}
{3}:{1,2} {2}:{3}:{1}
{2}:{1,3} {1}:{3}:{2}
{1}:{2,3} {2}:{1}:{3}
{3}:{2}:{1}
-----------------------
n=4 --> 1+12+9+60+47=129
1*1 4*3=12 3*3=9 6*10=60 1*47
{1,2,3,4} {1,2,3}{4} {1,2}{3,4} {1,2}{3}{4} {1}{2}{3}{4}
{1,2,4}{3} {1,3}{2,4} {1,2}{3}:{4}
{1,3,4}{2} {1,4}{2,3} {1,2}{4}:{3} {1}{2}:{3}:{4}
{2,3,4}{1} {1}{2}:{3,4} {1}{3}:{2}:{4}
{1,2}:{3,4} {1,2}:{3}:{4} {1}{4}:{2}:{3}
{1,2,3}:{4} {1,3}:{2,4} {1,2}:{4}:{3} {1}{2}:{4}:{3}
{1,2,4}:{3} {1,4}:{2,3} {1}:{2}:{3,4} {1}{3}:{4}:{2}
{1,3,4}:{2} {3,4}:{1,2} {2}:{1}:{3,4} {1}{4}:{3}:{2}
{2,3,4}:{1} {2,4}:{1,3} {1}:{3,4}:{2}
{2,3}:{1,4} {2}:{3,4}:{1} {2}{3}:{1}:{4}
{4}:{1,2,3} {2}{4}:{1}:{3}
{3}:{1,2,4} likewise for: {2}{3}:{4}:{1}
{2}:{1,3,4} {3,4}{1}{2} {2}{4}:{3}:{1}
{1}:{2,3,4} {2,4}{1}{3}
{2,3}{1}{4} {3}{4}:{1}:{2}
{1,4}{2}{3} {3}{4}:{2}:{1}
{1,3}{2}{4}
{1}{2}:{3}{4}
{1}{3}:{2}{4}
{1}{4}:{2}{3}
{2}{3}:{1}{4}
{2}{4}:{1}{3}
{3}{4}:{1}{2}
{2}{3}{4}:{1}
{1}{3}{4}:{2}
{1}{2}{4}:{3}
{1}{2}{3}:{4}
{1}:{2}:{3}:{4}
+23 permutations
MAPLE
A140585 := proc(n::integer) local k, Result; Result:=0: for k from 1 to n do Result:=Result+stirling2(n, k)*A005651(k); end do; lprint(Result); end proc;
E.g.f.: series(1/mul(1-(exp(x)-1)^k/k!, k=1..10), x=0, 10). # Thomas Wieder, Sep 04 2008
# second Maple program:
with(numtheory): b:= proc(k) option remember; add(d/d!^(k/d), d=divisors(k)) end: c:= proc(n) option remember; `if`(n=0, 1, add((n-1)!/ (n-k)!* b(k)* c(n-k), k=1..n)) end: a:= n-> add(Stirling2(n, k) *c(k), k=1..n): seq(a(n), n=1..30); # Alois P. Heinz, Oct 10 2008
MATHEMATICA
Table[n!*SeriesCoefficient[1/Product[(1-(E^x-1)^k/k!), {k, 1, n}], {x, 0, n}], {n, 1, 20}] (* Vaclav Kotesovec, Sep 03 2014 *)
CROSSREFS
KEYWORD
nonn
AUTHOR
Thomas Wieder, May 17 2008
EXTENSIONS
More terms from Alois P. Heinz, Oct 10 2008
STATUS
approved