Measure of Asymmetry of Strongly Binary Trees

rulesG={{x_,{x_,y_}}:>y,{{x_,y_},z_}:>{x,{y,z}},{x_,{{y_,z_},w_}}:>{x,{y,{z,w}}},{x_,{y_,z_}}:>{x,{z,y}},{x_,{{y_,z_},w_}}:>{x,{z,{y,w}}}};

Convert[p_]:=(p/;AtomQ[p]);
Convert[{p_,q_}]:=StringJoin["E",Convert[p],Convert[q]];

pletters=CharacterRange["p","v"];

formulaexample={{{{x,y},z},w},{{{{{x,y},z},w},v},a},{{{{{{{x,y},z},w},v},a},b},c},{{{{{{{{{x,y},z},w},v},a},b},c},d},e},{{{{{{{{{{{x,y},z},w},v},a},b},c},d},e},f},g}};

RandomKsublist[set_,k_]:=Module[{sub={},rest=set,new},
Do[new=rest[[RandomInteger[{1,Length[rest]}]]];sub=AppendTo[sub,new];rest=Complement[rest,{new}],{k}];sub];
Randompermut[k_]:=RandomKsublist[Range[k],k];
set2[n_]:=Flatten[Table[{i,j},{i,-n+1,n-1},{j,-n+1,n-1}],1];

taut= {{{2,2}},{{2,2,2},{4,2}},{{2,2,2,2},{4,2,2},{4,4}},{{2,2,2,2,2},{4,2,2,2},{4,4,2}},{{2,2,2,2,2,2},{4,2,2,2,2},{4,4,2,2},{4,4,4}}};

set[k_]:=Module[{kom=Random[Integer,{1,Length[taut[[k]]]}],komb},komb=taut[[k,kom]];Flatten[Table[Table[pletters[[i]],{komb[[i]]}],{i,1,Length[komb]}]][[Randompermut[2k+2]]]];

rulesLetter1={x,y,z,w,v,a,b,c,d,e,f,g};

randformulaT[k_]:=Module[{formula=formulaexample[[k]],kk=Random[Integer,{1,k}],set1,rul},Do[formula=formula/.rulesG,{i,0,Random[Integer,{0,2kk}]} ];set1=set[k];rul=Table[rulesLetter1[[i]]->set1[[i]],{i,1,2k+2}];formula/.rul]

setpl=Join[Take[pletters,3],Take[pletters,3],Take[pletters,3],Take[pletters,3]][[Randompermut[12]]];

randformula[k_]:=Module[{formula=formulaexample[[k]],kk=Random[Integer,{1,k}],rul,setpl1=setpl[[Randompermut[12]]]},Do[formula=formula/.rulesG,{i,0,Random[Integer,{0,2k}]} ];rul=Table[rulesLetter1[[i]]->setpl1[[i]],{i,1,12}];formula/.rul];

Convert[p_]:=(p/;AtomQ[p]);
Convert[{p_,q_}]:=StringJoin["E",Convert[p],Convert[q]];

Convert1[p_]:=(p/;AtomQ[p]);
Convert1[{p_,q_}]:=StringJoin["(",Convert[p],"≡",Convert[q],")"];

τ[x_]:={x}/;MemberQ[pletters,x];
τ[{x_,y_}]:=Union[{{x,y}},Complement[τ[x],τ[y]],Complement[τ[y],τ[x]]];

as[tree_]:=Length[τ[tree]];

randtree[k_]:=If[Random[Integer,{1,2}]==1,randformulaT[k],randformula[k]];

Manipulate[With[{ran=SeedRandom[ranint],tr=randtree[k]},Column[{"",Row[{"What is the measure of asymmetry of the tree: ",If[shan,as[tr],""]}],"",If[sh,TreeForm[tr,ImageSize->{450,350}],tr]}]],{{ranint,RandomInteger[{1,234717}]},ControlType->None},{k,1,5,1,Appearance->"Labeled"},Button["new example",ranint=RandomInteger[{1,13467}];shan=False;ImageSize->130],{{sh,True,"show tree-form"},{False,True}},{{shan,False,"show answer"},{False,True}},ContentSize->{500,430},SaveDefinitions->True]

A measure of asymmetry of strongly binary trees, represented as lists, with 2k leaves is defined. We first define function τ(x)={x} if x is a leaf, otherwise τ({x,y})={{x,y}}⋃(τ(x)-τ(y))⋃(τ(y)-τ(x)) which gives a set of subtrees of a tree. The asymmetry  of x is the number of elements of τ(x).

Contributed by: Izidor Hafner