login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A120803 Number of series-reduced balanced trees with n leaves. 17
1, 1, 1, 2, 2, 4, 4, 8, 9, 16, 20, 37, 47, 80, 111, 183, 256, 413, 591, 940, 1373, 2159, 3214, 5067, 7649, 12054, 18488, 29203, 45237, 71566, 111658, 176710, 276870, 437820, 687354, 1085577, 1705080, 2688285, 4221333, 6644088, 10425748 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,4

COMMENTS

In other words, rooted trees with all leaves at the same level and no node having exactly one child; the order of children is not significant.

LINKS

Alois P. Heinz, Table of n, a(n) for n = 1..1000

FORMULA

Let s_0(n) = 1 if n = 1, 0 otherwise; s_{k+1}(n) = EULER(s_k)(n) - s_k(n), where EULER is the Euler transform. Then a_n = sum_k s_k(n). (s_k(n) is the number of such trees of height k.) Note that s_k(n) = 0 for n < 2^k.

EXAMPLE

From Gus Wiseman, Oct 07 2018: (Start)

The a(10) = 16 series-reduced balanced rooted trees:

  (oooooooooo)

  ((ooooo)(ooooo))

  ((oooo)(oooooo))

  ((ooo)(ooooooo))

  ((oo)(oooooooo))

  ((ooo)(ooo)(oooo))

  ((oo)(oooo)(oooo))

  ((oo)(ooo)(ooooo))

  ((oo)(oo)(oooooo))

  ((oo)(oo)(ooo)(ooo))

  ((oo)(oo)(oo)(oooo))

  ((oo)(oo)(oo)(oo)(oo))

  (((oo)(ooo))((oo)(ooo)))

  (((oo)(oo))((ooo)(ooo)))

  (((oo)(oo))((oo)(oooo)))

  (((oo)(oo))((oo)(oo)(oo)))

(End)

PROG

(PARI) EulerT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, 1/n))))-1, -#v)}

seq(n)={my(u=vector(n), v=vector(n)); u[1]=1; while(u, v+=u; u=EulerT(u)-u); v} \\ Andrew Howroyd, Oct 26 2018

CROSSREFS

Cf. A000081, A000669, A001003, A001678, A007059, A048816, A079500, A119262, A244925, A316624, A320154, A320160, A320169, A320179.

Sequence in context: A222708 A324843 A306692 * A316624 A318770 A284613

Adjacent sequences:  A120800 A120801 A120802 * A120804 A120805 A120806

KEYWORD

nonn

AUTHOR

Franklin T. Adams-Watters, Aug 18 2006

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 June 4 04:39 EDT 2020. Contains 334815 sequences. (Running on oeis4.)