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: