A109509 Number of hierarchical orderings with at least 2 elements on each level for n unlabeled elements. Unlabeled analog of A097236.
1, 0, 1, 1, 3, 4, 9, 14, 28, 47, 88, 152, 279, 486, 876, 1539, 2744, 4824, 8551, 15023, 26503, 46509, 81747, 143210, 251007, 438915, 767403, 1339487, 2336955, 4071906, 7090589, 12333894, 21440241, 37235775, 64624267, 112067176, 194209732, 336313393, 582019000
Offset: 0
Keywords
Examples
Let * denote an unlabeled element. Let | denote a delimiter between two hierarchies. E.g., for n=3 we have in **|* two hierarchies (each with one level only). Let : denote a higher level (within a single hierarchy). E.g., for n=6 we have in ***:**:* a single hierarchy distributed over three levels. Then a(5) = 4 because we have *****, ***:**, **:***, **|***.
Links
- Alois P. Heinz, Table of n, a(n) for n = 0..1000
- Vaclav Kotesovec, Asymptotics of the Euler transform of Fibonacci numbers, arXiv:1508.01796 [math.CO], Aug 07 2015.
- N. J. A. Sloane and Thomas Wieder, The Number of Hierarchical Orderings, Order 21 (2004), 83-89.
Programs
-
Maple
SeqSetSetxU := [T, {T=Set(S),S=Sequence(U,card>=1),U=Set(Z,card>=2)},unlabeled]; seq(count(SeqSetSetxU,size=j),j=1..25); # where x is an integer 1, 2, 3,... # x=2 gives 2 individuals per level. -
Mathematica
CoefficientList[Series[Product[1/(1-x^k)^Fibonacci[k-1], {k, 1, 40}], {x, 0, 40}], x] (* Vaclav Kotesovec, Aug 06 2015 *) -
PARI
ET(v)=Vec(prod(k=1,#v,1/(1-x^k+x*O(x^#v))^v[k])) ET(vector(40,n,fibonacci(n-1)))
Formula
a(n) ~ phi^(n-1/4) / (2 * sqrt(Pi) * 5^(1/8) * n^(3/4)) * exp(phi/10 - 1/2 + 2*5^(-1/4)*sqrt(n/phi) + s), where s = Sum_{k>=2} 1/((phi^(2*k) - phi^k - 1)*k) = 0.189744799982532613329750744326543900883761701983311537716143669... and phi = A001622 = (1+sqrt(5))/2 is the golden ratio. - Vaclav Kotesovec, Aug 06 2015
Extensions
Edited with more terms from Franklin T. Adams-Watters, Oct 21 2009
Comments