Initialising the lists:

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

Function to combine three branches:

Combine[{a1_,b1_,k1_},{a2_,b2_,k2_},{a3_,b3_,k3_}]:={a1+a2+a3+k1 k2 k3,b1+b2+b3+k1 a2+k2 a1+k1 a3+k3 a1+k2 a3+k3 a2};

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[j];While[Which[s==L[j],True,s<1,False,True,Slopes[j][[s]]>n-j],t=L[n-j-k];While[Which[t==L[n-j-k],True,t<1,False,True,Slopes[n-j-k][[t]]>j+k],l=Append[l,Append[Combine[{AllOpt[k][[r,1]],AllOpt[k][[r,2]],k},{AllOpt[j][[s,1]],AllOpt[j][[s,2]],j},{AllOpt[n-j-k][[t,1]],AllOpt[n-j-k][[t,2]],n-j-k}],{{k,r},{j,s},{n-j-k,t}}]];t--];s--];r--],{k,0,Floor[n/3]},{j,1,Floor[(n-k)/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=500:

Do[AllOpt[n],{n,4,500}];

Selecting specific values:

MyList={4,5,6,7,8,9,10,15,20,25,30,35,40,45,50,60,70,80,90,100,150,200,250,300,350,400,450,500};

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

N[%]

Exporting the lists into a text file:

Export["AllOptQ4.txt",Table[AllOpt[n],{n,1,500}],"Text"];