# IMPORTANT: Change leading dots to spaces before running it
# number of left-leaning AVL height-balanced trees
# ie for each node height of left subtree - height of right subtree = 0 or 1
# Maximum number of inner nodes
vmax=122
# Fibonacci sequence and its sume, for boundaries
fib=[0,1]
sfib=[0,1]
i=0
while(sfib[i+1]<=vmax):
....fib.append(fib[i]+fib[i+1])
....sfib.append(fib[i+2]+sfib[i+1])
....i=i+1
# Maximum height of a tree we'll need to consider
hmax=i
# List of numbers of trees with given height and number of nodes
# ntrees[h+1][v]= sum for l+r=v-1 of ntrees[h][l]*ntrees[h-1][r] + ntrees[h][l]*ntrees[h][r] (Because every tree is defined by picking its left and right subtree. Left subtree must have height h-1, right can have h-1 or h-2 and their numbers of nodes sum to v-1)
ntrees=[]
n0=[1]
ntrees.append(n0)
n1=[1,1]
ntrees.append(n1)
# List of numbers of trees with given number of nodes, for all heights
ntrees_allh=[1,1,1]
for h in range (2,hmax):
....nh=[]
....vmaxlocal=2**(h+1)
....if (vmaxlocal>vmax+1):
........vmaxlocal=vmax+1
....for v in range(sfib[h+1], vmaxlocal):
........s=0
........# the important part starts here
........for l in range(sfib[h],2**h):
............r=v-1-l
............if(r in range(sfib[h],2**h)):
................s=s+ntrees[h-1][l-sfib[h]]*ntrees[h-1][r-sfib[h]]
............if(r in range(sfib[h-1],2**(h-1))):
................s=s+ntrees[h-1][l-sfib[h]]*ntrees[h-2][r-sfib[h-1]]
........if (v-1<len(ntrees_allh)):
............ntrees_allh[v-1]=ntrees_allh[v-1]+s
........else:
............ntrees_allh.append(s)
........nh.append(s)
....ntrees.append(nh)
for i in ntrees_allh:
....print i