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

 

Logo

Annual appeal: Please make a donation to keep the OEIS running! Over 6000 articles have referenced us, often saying "we discovered this result with the help of 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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified December 12 16:36 EST 2017. Contains 295939 sequences.