|
| |
|
|
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.
|
|
22
| |
|
|
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; internal format)
|
|
|
|
OFFSET
| 0,3
|
|
|
COMMENTS
| If all indviduals 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).
|
|
|
REFERENCES
| 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. [From Thomas Wieder (thomas.wieder(AT)t-online.de), Nov 14 2009]
|
|
|
LINKS
| T. D. Noe, Table of n, a(n) for n=0..100
INRIA, Algolib: The Algorithms Project's Library
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.
Index entries for sequences related to parenthesizing
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 571
Kruchinin Vladimir Victorovich, Composition of ordinary generating functions, arXiv:1009.2565
|
|
|
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
In Latex notation, a(n) = sum_{ (m_1, m_2, \ldots, m_n)} \frac{ n! \; \prod_{j=1}^{n} B_j^{m_{j}} }{ \prod_{j=1}^{n} m_{j}! \; (j!)^{m_{j}}}, where the sum is over all $(m_1, m_2, \ldots, 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*ln(2))-3/4)/(2*sqrt(pi*sqrt(2*ln(2))))*n!*exp(-ln(ln(2))*n)*exp(sqrt(2*n/ln(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 (vladeta(AT)eunet.rs), Sep 25 2006
a(n)=sum(sum(stirling2(n,k)*k!*binomial(k-1,m-1),k,m,n)/m!,m,1,n) [From Kruchinin Vladimir (kru(AT)ie.tusur.ru), Aug 10 2010]
|
|
|
EXAMPLE
| E.g. a(3) = 23: Let the n = 3 indviduals 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 indviduals 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);
a(n):=sum(sum(stirling2(n, k)*k!*binomial(k-1, m-1), k, m, n)/m!, m, 1, n) (for Maxima) [From Kruchinin Vladimir (kru(AT)ie.tusur.ru), Aug 10 2010]
|
|
|
MATHEMATICA
| Range[0, 20]!CoefficientList[Series[E^(1/(2 - E^x) - 1), {x, 0, 20}], x] (from Robert G. Wilson v Jul 13 2004)
|
|
|
CROSSREFS
| Cf. A000670, A075744. See A075900 for the unlabeled case.
Sequence in context: A053525 A113869 A084357 * A127131 A083355 A141763
Adjacent sequences: A075726 A075727 A075728 * A075730 A075731 A075732
|
|
|
KEYWORD
| nonn,nice
|
|
|
AUTHOR
| Thomas Wieder (wieder.thomas(AT)t-online.de) and N. J. A. Sloane (njas(AT)research.att.com), Oct 06 2002
|
| |
|
|
