|
%I #72 Nov 09 2023 12:14:19
%S 1,1,4,23,173,1602,17575,222497,3188806,50988405,899222457,
%T 17329515172,362164300173,8155216185781,196789115887252,
%U 5064722539020379,138457553073641465,4006059432756066914,122284085809137076203,3926775294104305483621,132313462760902116605534
%N Number of different hierarchical orderings that can be formed from n labeled elements: these are divided into groups and the elements in each group are then arranged in a "preferential arrangement" or "weak order" as in A000670.
%C If all individuals form a single society ("uniparate society"), then the number of different hierarchies for that single society is equal to the ordered Bell number Bell_ordered(n) (A000670).
%C Represent a labeled pre-order (quasi-order, topology, A000798) as a directed graph. a(n) is the number of such digraphs in which the underlying graph of each component is complete. a(3)=23 because there are 29 such digraphs but o->o<-o and o<-o->o are not counted. Each has 3 labelings. 29 - 6 = 23. - _Geoffrey Critzer_, Jul 30 2014
%H Alois P. Heinz, <a href="/A075729/b075729.txt">Table of n, a(n) for n = 0..419</a> (first 101 terms from T. D. Noe)
%H José A. Adell and Sithembele Nkonkobe, <a href="http://math.colgate.edu/~integers/x80/x80.pdf">A unified generalization of Touchard and Fubini polynomial extensions</a>, Integers (2023) 23, #A80.
%H INRIA, <a href="http://algo.inria.fr/libraries/software.html">Algolib: The Algorithms Project's Library</a>
%H P. Flajolet and R. Sedgewick, <a href="http://algo.inria.fr/flajolet/Publications/books.html">Analytic Combinatorics</a>, 2009; see page 571.
%H Robert Gill, <a href="https://doi.org/10.1016/S0012-365X(97)00187-8">The number of elements in a generalized partition semilattice</a>, Discrete mathematics 186.1-3 (1998): 125-134. See Example 2.
%H Norihiro Nakashima and Shuhei Tsujie, <a href="https://arxiv.org/abs/1904.09748">Enumeration of Flats of the Extended Catalan and Shi Arrangements with Species</a>, arXiv:1904.09748 [math.CO], 2019.
%H K. A. Penson, P. Blasiak, G. Duchamp, A. Horzela and A. I. Solomon, <a href="http://arXiv.org/abs/quant-ph/0312202">Hierarchical Dobinski-type relations via substitution and the moment problem</a> [J. Phys. A 37 (2004), 3475-3487]
%H N. J. A. Sloane and Thomas Wieder, <a href="http://arXiv.org/abs/math.CO/0307064">The Number of Hierarchical Orderings</a>, Order 21 (2004), 83-89.
%H Kruchinin Vladimir Victorovich, <a href="http://arxiv.org/abs/1009.2565">Composition of ordinary generating functions</a>, arXiv:1009.2565 [math.CO], 2010.
%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
%H <a href="/index/Par#parens">Index entries for sequences related to parenthesizing</a>
%F E.g.f.: exp(f(x)-1) where f(x) = 1/(2-exp(x)) = e.g.f. for A000670.
%F STIRLINGi transform of A000262.
%F a(n) = (n-1)! * Sum_k=1^n a(n-k)*b(k)/((n-k)!*(k-1)!); a(n) = a(n) + C(n-1, k-1)*a(n-k)*b(k) (where b(n) = A000670(n)). - _Thomas Wieder_, Dec 31 2002
%F a(n) = (Sum_{j=1..n} m(j))*(n!*Product_{j=1..n} B(j)^m(j))/(Product_{j=1..n} (m(j))!*(j!)^m(j)), where the sum is over all (m(1),m(2),...,m(n)) such that Sum_{j=1..n} (j*m(j)) = n. - _Thomas Wieder_, May 18 2003
%F a(n) is asymptotic to exp(1/(4*log(2))-3/4) /(2*sqrt(Pi*sqrt(2*log(2)))) *n!*exp(-log(log(2))*n)*exp(sqrt(2*n /log(2))) /n^(3/4). Calculated using the Maple package "algolib", using the command "equivalent(exp(1/(2-exp(x))-1), x, n);". - _Thomas Wieder_, Nov 12 2002
%F a(n) = Sum_{k=0..n} A079641(n,k)*A000110(k). - _Vladeta Jovovic_, Sep 25 2006
%F a(n) = sum(sum(stirling2(n,k)*k!*C(k-1,m-1), k=m..n)/m!, m=1..n). - _Vladimir Kruchinin_, Aug 10 2010
%e a(3) = 23: Let the n = 3 individuals be named 1, 2 and 3. Let a pair of parentheses () indicate a society and let square brackets [] denote a set of disparate societies. Finally, let the ranks be ordered from left to right and separated by a colon, e.g., (1,2:3) is a society with individual 3 on top and individuals 1 and 2 on the same bottom rank.
%e Then the hierarchical ordering for n = 3 is composed of the following sets: [(1),(2),(3)], [(1,2)(3)], [(3,2)(1)], [(3,1)(2)], [(1:2)(3)], [(3:2)(1)], [(1:3)(2)], [(2:1)(3)], [(2:3)(1)], [(3:1)(2)], [(3:2:1)], [(1:3:2)], [(2:1:3)], [(1:2:3)], [(3:1:2)], [(2:3:1)], [(1,3:2)], [(3,2:1)], [(2,1:3)], [(3:1,2)], [(1:2,3)], [(2:3,1)], [(1,2,3)].
%p A075729 := n->n!*exp(1/4/ln(2)-3/4)/2/sqrt(Pi)/(2*ln(2))^(1/4)*exp(-n*ln(ln(2)))*exp(sqrt(2*n/ln(2)))*n^(-3/4);
%p with(combstruct); SetSeqSetL := [T, {T=Set(S), S=Sequence(U,card >= 1), U=Set(Z,card >=1)},labeled]; seq(count(SetSeqSetL,size=j),j=1..12);
%p # alternative Maple program:
%p b:= proc(n) option remember: `if`(n<2, 1,
%p (2*n-1)*b(n-1) -(n-1)*(n-2)*b(n-2))
%p end:
%p a:= n-> add(b(k)*Stirling2(n,k), k=0..n):
%p seq(a(n), n=0..20); # _Alois P. Heinz_, May 22 2018
%t Range[0, 20]!CoefficientList[Series[E^(1/(2 - E^x) - 1), {x, 0, 20}], x] (* _Robert G. Wilson v_, Jul 13 2004 *)
%t Fubini[n_, r_] := Sum[k!*Sum[(-1)^(i+k+r)(i+r)^(n-r)/(i!*(k-i-r)!), {i, 0, k-r}], {k, r, n}]; Fubini[0, 1] = 1; a[0] = 1; a[n_] := a[n] = (n-1)! Sum[a[n-k] Fubini[k, 1]/((n-k)! (k-1)!), {k, 1, n}]; Table[a[n], {n, 0, 20}] (* _Jean-François Alcover_, Mar 31 2016 *)
%t Table[Sum[BellY[n, k, PolyLog[-Range[n], 1/2]/2], {k, 0, n}], {n, 0, 20}] (* _Vladimir Reshetnikov_, Nov 09 2016 *)
%t With[{nn=20},CoefficientList[Series[Exp[1/(2-Exp[x])-1],{x,0,nn}],x] Range[0,nn]!] (* _Harvey P. Dale_, Aug 26 2022 *)
%o (Maxima) a(n):= sum(sum(stirling2(n,k)*k!*binomial(k-1,m-1), k,m,n)/m!, m,1,n) /* _Vladimir Kruchinin_, Aug 10 2010 */
%Y Cf. A000670, A075744. See A075900 for the unlabeled case.
%K nonn,nice
%O 0,3
%A _Thomas Wieder_ and _N. J. A. Sloane_, Oct 06 2002
|
