#C23.txt: April 17, 2025
Help23:=proc(): print(`BT(n), T(N), Images(T) , UBT(n), UT(N) `):end:

#Def. a full binary tree is either a single vertex called the root,
#or it has a root that has EXACTLY two children
#T=*  or
#      *
#    T1  T2
#T=[] or T=[T1,T2]
#BT(1)={[]}; BT(2)={[[],[]]}: BT(3)={[[],[[],[]]], ...

#BT(n): the SET of full binary trees with n leaves
BT:=proc(n) local T1,T2,k,T,t1,t2:
if n=1 then
 RETURN({[]}):
fi:
#k is the number of leaves in the left child
T:={}:
for k from 1 to n-1 do
 T1:=BT(k):
  T2:=BT(n-k):
 T:=T union {seq(seq( [ t1,t2   ]   , t1 in T1), t2 in T2)}:
od:

T:
end:

#T(N): the first N terms of the sequence enumerating the number of full binary trees with n leaves
T:=proc(N) local x,f,i:
f:=x:
for i from 1 to N do
 f:=expand(x+f^2):
f:=add(coeff(f,x,i)*x^i,i=1..N):
od:
[seq(coeff(f,x,i),i=1..N)]:
end:

#Images(T):Images(T)=[Images(T1),Images(T2)]
Images:=proc(T) local T1,T2,t1,t2,S:
if T=[] then
 RETURN({[]}):
fi:
T1:=Images(T[1]):
T2:=Images(T[2]):
S:={}:
for t1 in T1 do
 for t2 in T2 do
  S:=S union {[t1,t2],[t2,t1]}:
 od:
od:
S:
end:

#UBT(n): the set of all unlabeled full binary trees (one reprentative each)
UBT:=proc(n) local S1,S2,S3:
S1:=BT(n):
S2:={}:
while S1<>{} do
  S3:=Images(S1[1]):
 S2:=S2 union {S1[1]}:
  S1:=S1 minus S3:
od:
S2:
end:

#UT(N): the first N terms of the sequence enumerating the number of UNLABELED full binary trees with n leaves
#gen. function satisfies the functional equation f(x)=x+(f(x)^2+f(x^2))/2
UT:=proc(N) local x,f,i:
f:=x:
for i from 1 to N do
 f:=expand(x+(f^2+subs(x=x^2,f))/2):
f:=add(coeff(f,x,i)*x^i,i=1..N):
od:
[seq(coeff(f,x,i),i=1..N)]:
end: