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,5

Comments

A109509 is the Euler transform of the right-shifted Fibonacci numbers A000045.

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.

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

Example

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 *****, ***:**, **:***, **|***.

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

Prog

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

Crossrefs

Cf. A000045, A075729, A097236, A166861.

Sequence in context: A007293 A014596 A002823 * A006053 A051841 A096081

Adjacent sequences: A109506 A109507 A109508 * A109510 A109511 A109512

Keyword

nonn

Author

Thomas Wieder, Jun 30 2005

Extensions

Edited with more terms from Franklin T. Adams-Watters, Oct 21 2009

Status

approved