f ={0:1,1:1,2:2}
for n in range (2,20):
  f[n] = sum(
     ( sum(f[j-1]*f[i-1-j] for j in range(1,i))/float(i-1) if i>1 else 1)
     * f[n-i] for i in range(1,n+1))
  print n, f[n], f[n]/f[n-1]

from itertools import permutations

def normalize(lis):
    s = [(j,i) for i,j in enumerate(lis)]
    s.sort()
    s = [(i,a) for a,(j,i) in enumerate(s)]
    s.sort()
    return(tuple(a for i,a in s))

g= {():1}
sopt= {0:1}
for n in range (1,11):
    smax = 0
    for p in permutations(range(n)):
#    for p in (tuple(range(n)),):
        s = 0
        for i in range(n):
            p11 = normalize (x for x in p[:i] if x<p[i])
            p12 = normalize (x for x in p[:i] if x>p[i])
  #          p2 = normalize (p[i+1:])
  #          print p,i,p11,p12,p2
            s += g[p11]*g[p12]*sopt[n-i-1] #g[p2]
        g[p] = s
        if s>smax:
            smax = s
            popt = p
    sopt[n]=smax
    print (n,smax,popt,
           float(smax)/sopt[n-1])