A056207 Number of binary trees of height <= n.

3, 24, 675, 458328, 210066388899, 44127887745906175987800, 1947270476915296449559703445493848930452791203, 3791862310265926082868235028027893277370233152247388584761734150717768254410341175325352024

Offset: 1

Author

Todd K. Moon (Todd.Moon(AT)ece.usu.edu), Aug 02 2000

Keywords

• easy
• nonn

References

• Todd K. Moon, "Enumerations of binary trees, types of trees and the number of reversible variable length codes," submitted to Discrete Applied Mathematics, 2000.

Links

• Index entries for sequences of form a(n+1)=a(n)^2 + ...

Crossrefs

Cf. A001699, A002449, A003095.

Programs

Python

from itertools import accumulate
def f(anm1, _): return anm1**2 + 4*anm1 + 3
def aupton(terms): return list(accumulate([3]*terms, f))
print(aupton(8)) # Michael S. Branicky, Mar 24 2021

Formula

a(n) = d(n) + a(n-1), d(n) = A001699(n) is the number of binary trees of depth exactly n.

a(n) = A003095(n+2) - 2 = A004019(n+1) - 1 = a(n-1)^2 + 4*a(n-1) + 3.

Extensions

More terms from Henry Bottomley, Jul 09 2001