all_trees2.py

import sys

a = []

def go(s, c0, c1, n):
  if c0 + c1 == 2*n:
    a.append(s)
  elif c0 == 0 or c0 == c1:
    go(s + "0", c0+1, c1, n)
  elif c0 == n:
    go(s + "1", c0, c1+1, n)
  else:
    go(s + "0", c0+1, c1, n)
    go(s + "1", c0, c1+1, n)

def to_can(s):
  res = []
  while s != "":
    t = i = 0
    while True:
      t += 1 if s[i] == '0' else -1
      i += 1
      if t == 0: break
    ss = s[:i]
    res.append(ss if len(ss) <= 2 else "0" + to_can(ss[1:-1]) + "1")
    s = s[i:]
  res.sort()
  return "".join(res)

def uniq(seq):
    seen = set()
    seen_add = seen.add
    return [x for x in seq if not (x in seen or seen_add(x))]

def make(n):
  global a
  n = int(n)
  go("", 0, 0, n)
  for i, s in enumerate(a):
    a[i] = to_can(s)
  a = uniq(a)

for i in range(20):
  make(i)
  print("Count ", i+1, "-vertices trees is ", len(a), sep="")
  a = []

res.txt

Count 1-vertices trees is 1
Count 2-vertices trees is 1
Count 3-vertices trees is 2
Count 4-vertices trees is 4
Count 5-vertices trees is 9
Count 6-vertices trees is 20
Count 7-vertices trees is 48
Count 8-vertices trees is 115
Count 9-vertices trees is 286
Count 10-vertices trees is 719
Count 11-vertices trees is 1842
Count 12-vertices trees is 4766
Count 13-vertices trees is 12486
Count 14-vertices trees is 32973
Count 15-vertices trees is 87811

res2.txt

['']
['01']
['0011', '0101']
['000111', '001011', '001101', '010101']
['00001111', '00010111', '00011011', '00011101', '00101011', '00101101', '00110011', '00110101', '01010101']
['0000011111', '0000101111', '0000110111', '0000111011', '0000111101', '0001010111', '0001011011', '0001011101', 
'0001100111', '0001101011', '0001101101', '0001110011', '0001110101', '0010101011', '0010101101', '0010110011', 
'0010110101', '0011001101', '0011010101', '0101010101']