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

 

Logo

Annual Appeal: Please make a donation to keep the OEIS running. In 2018 we replaced the server with a faster one, added 20000 new sequences, and reached 7000 citations (often saying "discovered thanks to the OEIS").
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A109509 Number of hierarchical orderings with at least 2 elements on each level for n unlabeled elements. Unlabeled analog of A097236. 2
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 (list; graph; refs; listen; history; text; internal format)
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

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.

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 13 11:01 EST 2018. Contains 318086 sequences. (Running on oeis4.)