This site is supported by donations to The OEIS Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A075729 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. 27
 1, 1, 4, 23, 173, 1602, 17575, 222497, 3188806, 50988405, 899222457, 17329515172, 362164300173, 8155216185781, 196789115887252, 5064722539020379, 138457553073641465, 4006059432756066914, 122284085809137076203, 3926775294104305483621, 132313462760902116605534 (list; graph; refs; listen; history; text; internal format)
 OFFSET 0,3 COMMENTS 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). 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 LINKS Alois P. Heinz, Table of n, a(n) for n = 0..419 (first 101 terms from T. D. Noe) P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 571. Robert Gill, The number of elements in a generalized partition semilattice, Discrete mathematics 186.1-3 (1998): 125-134. See Example 2. Norihiro Nakashima, Shuhei Tsujie, Enumeration of Flats of the Extended Catalan and Shi Arrangements with Species, arXiv:1904.09748 [math.CO], 2019. K. A. Penson, P. Blasiak, G. Duchamp, A. Horzela and A. I. Solomon, Hierarchical Dobinski-type relations via substitution and the moment problem [J. Phys. A 37 (2004), 3475-3487] N. J. A. Sloane and Thomas Wieder, The Number of Hierarchical Orderings, Order 21 (2004), 83-89. Kruchinin Vladimir Victorovich, Composition of ordinary generating functions, arXiv:1009.2565 [math.CO], 2010. 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 E.g.f.: exp(f(x)-1) where f(x) = 1/(2-exp(x)) = e.g.f. for A000670. STIRLINGi transform of A000262. 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 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 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 a(n) = Sum_{k=0..n} A079641(n,k)*A000110(k). - Vladeta Jovovic, Sep 25 2006 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 EXAMPLE 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. 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)]. MAPLE 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); 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); # alternative Maple program: b:= proc(n) option remember: `if`(n<2, 1,       (2*n-1)*b(n-1) -(n-1)*(n-2)*b(n-2))     end: a:= n-> add(b(k)*Stirling2(n, k), k=0..n): seq(a(n), n=0..20);  # Alois P. Heinz, May 22 2018 MATHEMATICA Range[0, 20]!CoefficientList[Series[E^(1/(2 - E^x) - 1), {x, 0, 20}], x] (* Robert G. Wilson v, Jul 13 2004 *) 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 = 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 *) Table[Sum[BellY[n, k, PolyLog[-Range[n], 1/2]/2], {k, 0, n}], {n, 0, 20}] (* Vladimir Reshetnikov, Nov 09 2016 *) PROG (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 */ CROSSREFS Cf. A000670, A075744. See A075900 for the unlabeled case. Sequence in context: A317276 A113869 A084357 * A328006 A127131 A083355 Adjacent sequences:  A075726 A075727 A075728 * A075730 A075731 A075732 KEYWORD nonn,nice AUTHOR Thomas Wieder and N. J. A. Sloane, Oct 06 2002 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified October 21 22:47 EDT 2019. Contains 328315 sequences. (Running on oeis4.)