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

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

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

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

Prog

(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 */

Crossrefs

Cf. A003095, A070939, A309049.

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

Sequence in context: A037026 A116651 A135586 * A116646 A306318 A091188

Adjacent sequences: A168539 A168540 A168541 * A168543 A168544 A168545

Keyword

nonn

Author

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

Extensions

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

Status

approved