A168542 Number of trees that have a maximum 'n'.

1, 1, 1, 2, 2, 4, 5, 10, 10, 20, 25, 50, 52, 104, 130, 260, 260, 520, 650, 1300, 1352, 2704, 3380, 6760, 6770, 13540, 16925, 33850, 35204, 70408, 88010, 176020, 176020, 352040, 440050, 880100, 915304, 1830608, 2288260, 4576520, 4583290, 9166580, 11458225

Offset: 0

Author

Endi Begeja (andy.bege(AT)libero.it), Nov 29 2009

Keywords

• nonn

Comments

a(2^n) = Product_{k=1..n} A003095(k). - Michael Somos, Dec 20 2018

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..5654

Crossrefs

Cf. A003095, A070939, A309049.

Partial differences of A091980. - Alois P. Heinz, Jul 12 2019

Programs

Maple

b:= proc(n) option remember; `if`(n=0, 1, (g-> (f->
      1+b(f)*b(n-1-f))(min(g-1, n-g/2)))(2^ilog2(n)))
    end:
a:= n-> b(n)-`if`(n=0, 0, b(n-1)):
seq(a(n), n=0..45);  # Alois P. Heinz, Jul 12 2019

Mathematica

a[ n_] := If[ n < 3, Boole[n > 0], With[{m = BitLength[Quotient[n, 3]] - 1}, Nest[#^2 + 1 &, 2, m] a[n - 2 2^m]]]; (* Michael Somos, Dec 20 2018 *)

PARI

{a(n) = if( n<3, n>0, my(m = #binary(n\3)-1, t = 2); for(i=1, m, t = t^2+1); t*a(n - 2*2^m))}; /* Michael Somos, Dec 20 2018 */

Formula

a(1) = a(2) = 1, a(3*2^m + k) = A003095(m+2) * a(n - 2*2^m) where 0 <= k < 3*2^m. - Michael Somos, Dec 20 2018

a(n) = Sum_{k=0..n} (A309049(n,k)-A309049(n-1,k)) for n > 0, a(0) = 1. - Alois P. Heinz, Jul 12 2019

Extensions

a(0)=1 prepended by Alois P. Heinz, Jul 12 2019