# hw23 Pablo Blanco
# OK to post


TT:=proc(n) local T1,T2,T3,k,T,t1,t2,t3,j:
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
  for j from 1 to n-1-k do:
   T1:=TT(k):
   T2:=TT(j):
   T3:=TT(n-k-j):
   T:=T union {seq(seq(seq( [ t1,t2,t3   ]   , t1 in T1), t2 in T2), t3 in T3)}:
  od:
od:

T:
end:

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

Images3:=proc(T):


end:


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

# this was the name of the proc in the homework, but it's a bad name. I renamed it below.
UBT3:=proc(n):
 UTT(n)
end:

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

# UT3(n)
UT3:=proc(N) local x,f,i:
f:=x:
for i from 1 to 2*N do
 f:=expand(x+1/6*( f^3+ 3*f*subs(x=x^2,f)+ 2*subs(x=x^3,f)) ):
 f:=add(coeff(f,x,i)*x^i,i=1..2*N):
od:
[seq(coeff(f,x,2*i-1),i=1..N)]:
end:


# UT3(40):
# output: [1, 1, 1, 2, 4, 8, 17, 39, 89, 211, 507, 1238, 3057, 7639, 19241, 48865, 124906, 321198, 830219, 2156010, 5622109, 14715813, 38649152, 101821927, 269010485, 712566567, 1891993344, 5034704828, 13425117806, 35866550869, 95991365288, 257332864506, 690928354105, 1857821351559, 5002305607153, 13486440075669, 36404382430278, 98380779170283, 266158552000477, 720807976831447]
# OEIS seq: A000598