|
%I #38 Mar 17 2021 02:54:32
%S 1,4,20,129,1012,9341,99213,1191392,15958404,235939211,3817327362,
%T 67103292438,1273789853650,25973844914959,566329335460917,
%U 13150556885604115,324045146807055210,8446201774570017379,232198473069120178475,6715304449424099384968
%N Total number of all hierarchical orderings for all set partitions of n.
%H Vaclav Kotesovec, <a href="/A140585/b140585.txt">Table of n, a(n) for n = 1..420</a> (first 160 terms from Alois P. Heinz)
%H Thomas Wieder, <a href="http://www.m-hikari.com/ams/ams-password-2009/ams-password53-56-2009/wiederAMS53-56-2009.pdf">The number of certain rankings and hierarchies formed from labeled or unlabeled elements and sets</a>, Applied Mathematical Sciences, vol. 3, 2009, no. 55, 2707 - 2724. [_Thomas Wieder_, Nov 14 2009]
%F Stirling transform of A005651 = Sum of multinomial coefficients: a(n) = Sum_{i=1..n} S2(n,k) A005651(k).
%F E.g.f.: 1/Product_{k>=1} (1 - (exp(x)-1)^k/k!). - _Thomas Wieder_, Sep 04 2008
%F 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
%e We are considering all set partitions of the n-set {1,2,3,...,n}.
%e 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.
%e 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.
%e Let the colon ":" separate two consecutive levels L and L+1.
%e n=2 --> 1+3=4
%e {1,2} {1}{2}
%e {1}:{2}
%e {2}:{1}
%e -----------------------
%e n=3 --> 1+9+10=20
%e 1*1 3*3=9 1*10
%e {1,2,3} {1,2}{3} {1}{2}{3}
%e {1,3}{2}
%e {2,3}{1} {1}{2}:{3}
%e {3}{1}:{2}
%e {1,2}:{3} {2}{3}:{1}
%e {1,3}:{2}
%e {2,3}:{1} {1}:{2}:{3}
%e {3}:{1}:{2}
%e {3}:{1,2} {2}:{3}:{1}
%e {2}:{1,3} {1}:{3}:{2}
%e {1}:{2,3} {2}:{1}:{3}
%e {3}:{2}:{1}
%e -----------------------
%e n=4 --> 1+12+9+60+47=129
%e 1*1 4*3=12 3*3=9 6*10=60 1*47
%e {1,2,3,4} {1,2,3}{4} {1,2}{3,4} {1,2}{3}{4} {1}{2}{3}{4}
%e {1,2,4}{3} {1,3}{2,4} {1,2}{3}:{4}
%e {1,3,4}{2} {1,4}{2,3} {1,2}{4}:{3} {1}{2}:{3}:{4}
%e {2,3,4}{1} {1}{2}:{3,4} {1}{3}:{2}:{4}
%e {1,2}:{3,4} {1,2}:{3}:{4} {1}{4}:{2}:{3}
%e {1,2,3}:{4} {1,3}:{2,4} {1,2}:{4}:{3} {1}{2}:{4}:{3}
%e {1,2,4}:{3} {1,4}:{2,3} {1}:{2}:{3,4} {1}{3}:{4}:{2}
%e {1,3,4}:{2} {3,4}:{1,2} {2}:{1}:{3,4} {1}{4}:{3}:{2}
%e {2,3,4}:{1} {2,4}:{1,3} {1}:{3,4}:{2}
%e {2,3}:{1,4} {2}:{3,4}:{1} {2}{3}:{1}:{4}
%e {4}:{1,2,3} {2}{4}:{1}:{3}
%e {3}:{1,2,4} likewise for: {2}{3}:{4}:{1}
%e {2}:{1,3,4} {3,4}{1}{2} {2}{4}:{3}:{1}
%e {1}:{2,3,4} {2,4}{1}{3}
%e {2,3}{1}{4} {3}{4}:{1}:{2}
%e {1,4}{2}{3} {3}{4}:{2}:{1}
%e {1,3}{2}{4}
%e {1}{2}:{3}{4}
%e {1}{3}:{2}{4}
%e {1}{4}:{2}{3}
%e {2}{3}:{1}{4}
%e {2}{4}:{1}{3}
%e {3}{4}:{1}{2}
%e {2}{3}{4}:{1}
%e {1}{3}{4}:{2}
%e {1}{2}{4}:{3}
%e {1}{2}{3}:{4}
%e {1}:{2}:{3}:{4}
%e +23 permutations
%p 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;
%p E.g.f.: series(1/mul(1-(exp(x)-1)^k/k!,k=1..10),x=0,10). # _Thomas Wieder_, Sep 04 2008
%p # second Maple program:
%p 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
%t 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 *)
%Y Cf. A005651, A075729, A034691, A083355, A109186, A000670.
%K nonn
%O 1,2
%A _Thomas Wieder_, May 17 2008
%E More terms from _Alois P. Heinz_, Oct 10 2008
|
