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]) # 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])