login
This site is supported by donations to The OEIS Foundation.

 

Logo


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. 26
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

T. D. Noe, Table of n, a(n) for n=0..100

INRIA, Algolib: The Algorithms Project's Library

P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 571

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

Index entries for sequences related to parenthesizing

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);

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[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 *)

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: A208676 A113869 A084357 * A127131 A083355 A141763

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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified February 18 02:09 EST 2018. Contains 299297 sequences. (Running on oeis4.)