print("Welcome to TERNARYTREES, a Maple package to accompany the paper"):
print("`Pattern Avoidance in Ternary Trees'"):
print("by Nathan Gabriel, Katherine Peske, Lara Pudwell, and Samuel Tay"):
print(""):
print("The main function is Av(T,n)."):
print("Type Help(); for a description of how to use this procedure"):

Help:=proc()
print("The main procedure is Av(T,n).  It inputs a ternary tree pattern T and a positive integer n."):
print("Tree pattern T should be input as a set of integer words where each word gives a path to an m-leaf parent of T."):
print("For example, the three-leaf claw is represented by {[]}, the tree t_7_1 is represented by {[1],[2]},"):
print("and the tree t_7_6 is represented by {[2,1]}."):
print(""):
print("The output is a list of length 2.  The first entry is a functional equation satisfied by the avoidance generating function"):
print("a=sum(av_n(T)x^n,x), and the second entry is the first n terms of the avoidance sequence for T."):
print(""):
print("For example, try Av({[1],[2]},20)."):
end:

#interstree(T1,T2): the intersection of tree patterns T1 and T2.  
#T1 and T2 should be entered in the following form: 
#	[1,0] denotes the one leaf tree
#	[1,L1,L2,L3,0] denotes a tree with left, center, and right subtrees L1, L2, L3
interstree := proc (T1::list, T2::list) option remember; 
if T1 = [1, 0] then 
	return T2: 
elif T2 = [1, 0] then 
	return T1:
fi:
[1, interstree(T1[2], T2[2]), interstree(T1[3], T2[3]), interstree(T1[4], T2[4]), 0]
end:

#TS(B): inputs a list of 1s, 2s, and 3s B and outputs the corresponding ternary tree in [0,L2,L3,L4,1] list notation.
TS := proc (B::list) local a, c, V; option remember; 
if B = [] then 
	return [1, [1, 0], [1, 0], [1, 0], 0]
fi:
if B[1] = 1 then 
	return [1, TS(B[2 .. nops(B)]), [1, 0], [1, 0], 0]
fi:
if B[1] = 2 then 
	return [1, [1, 0], TS(B[2 .. nops(B)]), [1, 0], 0]
fi:
if B[1] = 3 then 
	return [1, [1, 0], [1, 0], TS(B[2 .. nops(B)]), 0]
fi:
end:

#Listt(A): inputs a set of lists of 1s, 2s, and 3s and returns the corresponding ternary tree in [0,L2,L3,L4,1] form
Listt := proc (A::set) local c, k, t, F; option remember; 
if A = {} then 
	return [1, 0]:
fi:
if A = {[]} then 
	return [1, [1, 0], [1, 0], [1, 0], 0]
fi: 
F := TS(A[1]); 
for k from 2 to nops(A) do 
	F := interstree(F, TS(A[k]))
od: 
F:
end:

#Av01(T,n): inputs a ternary tree pattern in [0,L2,L3,L4,1] form and a positive integer n
#ouputs a list of length 2.  The first entry is a functional equation for the avoidance generating function for T
#where a stands for the generating function
#the second list is the first n terms of the avoidance sequence for T
Av01:=proc(T::list, n::posint)  local a,x,c,p,B,S,t,i,m,K,U,V,L,Y,E,z;  option remember;  
E:={};
U:={}; 
V:={};  
z[0]:=a[1,0]=x+ a[1,[1,0],[1,0],[1,0],0];  
z[1]:=a[1,[1,0],[1,0],[1,0],0]= a[1,0]*a[1,0]*a[1,0]-a[op(interstree([1,0],T[2]))]*a[op(interstree([1,0],T[3]))]*a[op(interstree([1,0],T[4]))];  
U:=U union {a[1,0], a[1,[1,0],[1,0],[1,0],0]};  
V:=V union {a[1,0], a[1,[1,0],[1,0],[1,0],0],a[op(interstree([1,0],T[2]))],a[op(interstree([1,0],T[3]))],a[op(interstree([1,0],T[4]))]};  
E:=E union{z[0],z[1]};  
c:=2;
while V minus U <>{} do
	B:=V minus U;  
	for i from 1 to nops(V minus U ) do  
		z[c]:= B[i]=a[op(op(2,B[i]))]*a[op(op(3,B[i]))]*a[op(op(4,B[i]))]-a[op(interstree(op(2,B[i]),T[2]))]*a[op(interstree(op(3,B[i]),T[3]))]*a[op(interstree(op(4,B[i]),T[4]))];  
		U:=U union {B[i]};  
		V:=V union  {a[op(op(2,B[i]))],a[op(op(3,B[i]))],a[op(op(4,B[i]))],a[op(interstree(op(2,B[i]),T[2]))],a[op(interstree(op(3,B[i]),T[3]))],a[op(interstree(op(4,B[i]),T[4]))]};  
		E:=E union {z[c]};  
		c:=c+1;  
	od:
od:  
m:=nops(E);  
K:=eliminate(E, {seq(lhs[i](E[i]), i=2..m)});  
L:=op(K[2]);


L:=subs(a[1,0]=add(q[k]*x^k,k=0..n),L):
Y:=expand(L); 
for i from 0 to degree(Y,x) do  
	p[i]:=coeff(Y,x,i);
od:
S:=solve({ seq(p[t]=0, t=0..n)}, {seq(q[t], t=0..n)});


[normal(sort(subs(a[1,0]=a,op(K[2])),a))=0,subs(S,[seq(q[t], t=0..n)])]:     
end:

#Av(T,n): inputs a ternary tree pattern in word form and a positive integer n
#ouputs a list of length 2.  The first entry is a functional equation for the avoidance generating function for T
#where a stands for the generating function
#the second list is the first n terms of the avoidance sequence for T
Av:=proc(T::set, n::posint)
Av01(Listt(T),n):
end: