# OK to post homework
# Aurora Hiveley, 4/18/25, Assignment 23

Help := proc(): print(`TT(n), T3(N), Images3(T), UBT3(n), UT3(N)`): end:

with(combinat):


## rooted ternary trees 

#TT(n): the SET of full binary trees with n leaves
TT:=proc(n) local T1,T2,T3,k,j,T,t1,t2,t3:
if n=1 then
 RETURN({[]}):
fi:
#k is the number of leaves in the left child
T:={}:
for k from 1 to n-2 do
    for j from 1 to n-k-1 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 binary trees with n leaves
T3:=proc(N) local x,f,i:
f:=x:
for i from 1 to N do
 f:=expand(x+f^3):
f:=add(coeff(f,x,i)*x^i,i=1..N):
od:
[seq(coeff(f,x,i),i=1..N)]:
end:

#Images3(T):Images3(T)=[Images3(T1),Images3(T2)]
Images3:=proc(T) local T1,T2,T3,t1,t2,t3,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 convert(permute({t1,t2,t3}),set):
  od:
 od:
od:
S:
end:

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

#UT3(N): the first N terms of the sequence enumerating the number of UNLABELED full TERNARY trees with n leaves
#gen. function satisfies the functional equation r(x)=x+1/6*(r(x)^3+ 3*r(x)*r(x^2)+ 2*r(x^3))
#Note that the number of leaves is always odd so only extract the odd coefficients

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



## UT3(40);
# [1, 1, 1, 2, 4, 8, 17, 39, 89, 211, 507, 1238, 3057, 7639, 19241, 48865, 124906, 321198, 830219, 2156010]
# this is A000598





## consider any four 3x3 matrices A1,A2,A3,A4 where the only the diagonal entries as well as the [1,2] entry are 0, i.e. matrices of the form
## [[a11,a12,0],[0,a22,0],[0,0,a33]]
## for any four such matrices, (A1A2-A2A1)(A3A4-A4A3)= 0 matrix

## proof: 
# if A1 = [[a,b,0],[0,c,0],[0,0,d]] and A2 = [[x,y,0],[0,z,0],[0,0,w]], then A1A2 = [[ax,ay+bz,0],[0,cz,0],[0,0,dw]] and A2A1 = [[ax,bx+cy,0],[0,cz,0],[0,0,dw]]
# then A1A2 - A2A1 = [[0,(ay+bz)-(bx+cy),0],[0,0,0],[0,0,0]]
# the same is true for A3A4-A4A3, so we have the product of two matrices whose only nonzero entry is a12. 
# this product is the zero matrix 












### copied from C23.txt 

#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: