Initialising the lists:

AllOpt[1]=AllOpt[2]=AllOpt[3]={{0,0,{}}};AllOpt[4]={{1,0,{}}};

Function to combine two branches:

Combine[{a1_,b1_,k1_},{a2_,b2_,k2_}]:={a1+a2+Binomial[k1,2]Binomial[k2,2],b1+b2+k1 a2+k2 a1};

Generating a first list of candidate trees:

PotentialList[n_]:=Module[{l={}},Do[
r=L[k];While[Which[r==L[k],True,r<1,False,True,Slopes[k][[r]]>n-k],s=L[n-k];While[Which[s==L[n-k],True,s<1,False,True,Slopes[n-k][[s]]>k],l=Append[l,Append[Combine[{AllOpt[k][[r,1]],AllOpt[k][[r,2]],k},{AllOpt[n-k][[s,1]],AllOpt[n-k][[s,2]],n-k}],{{k,r},{n-k,s}}]];s--];r--],{k,1,Floor[n/2]}];l];

First round of elimination: removing trees that are dominated by others.

NoDomin[l_,k_]:=Select[l,(#[[1]]>l[[k,1]])||(#[[2]]>l[[k,2]])||(#[[1]]+#[[2]]==l[[k,1]]+l[[k,2]])&];

DeleteAllDomin[l_]:=Module[{h=Union[l],i=1},While[i≤Length[h],h=NoDomin[h,i];i++];h];

Second round of elimination: determining the upper envelope.

UpperEnvelope[l_]:=Module[{A={First[l]},B=Rest[l]},While[B≠{},Which[Length[A]==1,A=Append[A,First[B]];B=Rest[B],(A[[-1,2]]-A[[-2,2]])(B[[1,1]]-A[[-1,1]])<=(B[[1,2]]-A[[-1,2]])(A[[-1,1]]-A[[-2,1]]),A=Delete[A,-1],True,A=Append[A,First[B]];B=Rest[B]]];A];

The recursion:

AllOpt[n_]:=AllOpt[n]=UpperEnvelope[FixedPoint[DeleteAllDomin,PotentialList[n]]];

Length of the n-th list:

L[n_]:=L[n]=Length[AllOpt[n]];

List of slopes from n-th list:

ABOnly[n_]:=Map[Delete[#,-1]&,AllOpt[n]];

Slopes[n_]:=Map[-#[[2]]/#[[1]]&,Delete[ABOnly[n],1]-Delete[ABOnly[n],-1]];

Generating lists up to n=2000:

Do[AllOpt[n],{n,5,2000}];

Selecting specific values:

MyList={5,6,7,8,9,10,20,30,40,50,60,70,80,90,100,150,200,250,300,350,400,500,600,700,800,900,1000,1200,1400,1600,1800,2000};

Map[AllOpt[#][[1,2]]/Binomial[#,5]&,MyList]

N[%]

Exporting the lists into a text file:

Export["AllOptA5.txt",Table[AllOpt[n],{n,1,2000}],"Text"];