#John Kim #Use whatever you like #read "C:/Users/John Y. Kim/Documents/Maple/hw20.txt": with(combinat): Help:=proc(): print(` AdjustBFP(a,B,FP,BFP) , GFun(A,B,FP,x) `): print(`GFun(A,B,FP,T)`): end: #AdjustBFP(a,B,FP,BFP): inputs a letter a, a symbol B for #blank, a set of forbidden patterns FP, and another set #of forbidden patterns at the beginning #outputs the new BFP for the chopped word assuming #it starts with a AdjustBFP:=proc(a,B,FP,BFP) local NBFP,fp: NBFP:={}: if member([],BFP) then RETURN(FAIL): fi: for fp in FP union BFP do if fp[1]=a or fp[1]=B then NBFP:=NBFP union {fp[2..nops(fp)]}: fi: od: NBFP: end: #GFun(A,B,FP,x): inputs an alphabet A ( a set of symbols or numbers) #and a letter B (NOT in A) and a set of forbidden patterns #FP, and another symbol x (not in A union {B}) and outputs #a rational function in x[A[1]], ..., x[A[nops(A)]] such #the if you mtaylor it the coeff. of #x[A1]^a1*x[A2]^a2*... is the EXACT number of words in #the alphabet A, avoiding the patterns in FP with #a1 occurrences of A1, #a2 occurrences of A2, .... #For example #GFun({1},B,{},x); should output: #1/(1-x[1]); #GFun({1},B,{[1,1]},x); should output: #1+X[1] #weight([1,2,1,1])=x[1]*x[2]*x[1]*x[1] GFun:=proc(A,B,FP,x) local eq,var, F,S, ToDo,BFP,eq1,ABFP,a: #F[BFP]=generating function of all words in the alphabet A #that avoid FP and in addition avoid BFP #S, the set of BFPs that show up #f=1+x[1]*f+x[2]*f+...+x[n]*f #(1-x[1]-...-x[n])*f=1 #f=1/(1-x[1]-...-x[n]) #f=1/(1-n*t) (if x[1]=...=x[n]=t) eq:={}: S:={{}}: var:={}: ToDo:={{}}: while ToDo<>{} do BFP:=ToDo[1]: S:=S union {BFP}: eq1:=F[BFP]-1: var:=var union {F[BFP]}: for a in A do ABFP:=AdjustBFP(a,B,FP,BFP): if not member([],ABFP) then eq1:=eq1-x[a]*F[ABFP]: ToDo:=ToDo union {ABFP}: fi: od: ToDo:=ToDo minus S: eq:=eq union {eq1}: od: var:=solve(eq,var): subs(var,F[{}]): end: #GFunT(A,B,FP,T): inputs an alphabet A ( a set of symbols or numbers) #and a letter B (NOT in A) and a set of forbidden patterns #FP, and another symbol x (not in A union {B}) and outputs #a rational function in x[A[1]], ..., x[A[nops(A)]] such #the if you mtaylor it the coeff. of #T^(length) #For example #GFunT({1},B,{},T); should output: #1/(1-T); #GFun({1},B,{[1,1]},T); should output: #1+T GFunT:=proc(A,B,FP,T) local eq,var, F,S, ToDo,BFP,eq1,ABFP,a: #F[BFP]=generating function of all words in the alphabet A #that avoid FP and in addition avoid BFP #S, the set of BFPs that show up #f=1+x[1]*f+x[2]*f+...+x[n]*f #(1-x[1]-...-x[n])*f=1 #f=1/(1-x[1]-...-x[n]) #f=1/(1-n*t) (if x[1]=...=x[n]=t) eq:={}: S:={{}}: var:={}: ToDo:={{}}: while ToDo<>{} do BFP:=ToDo[1]: S:=S union {BFP}: eq1:=F[BFP]-1: var:=var union {F[BFP]}: for a in A do ABFP:=AdjustBFP(a,B,FP,BFP): if not member([],ABFP) then eq1:=eq1-T*F[ABFP]: ToDo:=ToDo union {ABFP}: fi: od: ToDo:=ToDo minus S: eq:=eq union {eq1}: od: var:=solve(eq,var): subs(var,F[{}]): end: ################################################################ ######################START HW20.TXT############################ ################################################################ #UA(k): inputs a positive integer k, and outputs the set of sets #of length-k-patterns that are unavoidable, i.e. if every #sufficiently long word in {0,1} must contain one of its members. UA:= proc(k) local A,B,FP,T,allPat,GF,UAP: A:={0,1}: allPat:=powerset(AW(A,k)): UAP:={}: for FP in allPat do: GF:=GFunT(A,B,FP,T): if denom(GF)=1 then UAP:=UAP union {FP}: fi: od: UAP: end: #AW(A,k): inputs an alphabet A and a positive integer k and #outputs the set of all words of length k with letters in A. AW:=proc(A,k) local words,a,ends,w,word: option remember: if k=0 then RETURN({[]}): else words:={}: for a in A do ends:=AW(A,k-1): for w in ends do word:=[a,op(w)]: words:=words union {word}: od: od: RETURN(words): fi: end: #UA(1) #{{[0], [1]}} #UA(2) #{{[0, 0], [0, 1], [1, 1]}, {[0, 0], [1, 0], [1, 1]}, {[0, 0], [0, 1], [1, 0], [1, 1]}} #UA(3) #{{[0, 0, 0], [0, 0, 1], [1, 0, 1], [1, 1, 1]}, {[0, 0, 0], [0, 1, 0], [0, 1, 1], [1, 1, 1]}, {[0, 0, 0], [0, 1, 0], [1, 1, 0], [1, 1, 1]}, {[0, 0, 0], [1, 0, 0], [1, 0, 1], [1, 1, 1]}, {[0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 1, 1], [1, 1, 1]}, {[0, 0, 0], [0, 0, 1], [0, 1, 0], [1, 0, 1], [1, 1, 1]}, {[0, 0, 0], [0, 0, 1], [0, 1, 0], [1, 1, 0], [1, 1, 1]}, {[0, 0, 0], [0, 0, 1], [0, 1, 1], [1, 0, 1], [1, 1, 1]}, {[0, 0, 0], [0, 0, 1], [1, 0, 0], [1, 0, 1], [1, 1, 1]}, {[0, 0, 0], [0, 0, 1], [1, 0, 1], [1, 1, 0], [1, 1, 1]}, {[0, 0, 0], [0, 1, 0], [0, 1, 1], [1, 0, 0], [1, 1, 1]}, {[0, 0, 0], [0, 1, 0], [0, 1, 1], [1, 0, 1], [1, 1, 1]}, {[0, 0, 0], [0, 1, 0], [0, 1, 1], [1, 1, 0], [1, 1, 1]}, {[0, 0, 0], [0, 1, 0], [1, 0, 0], [1, 0, 1], [1, 1, 1]}, {[0, 0, 0], [0, 1, 0], [1, 0, 0], [1, 1, 0], [1, 1, 1]}, {[0, 0, 0], [0, 1, 0], [1, 0, 1], [1, 1, 0], [1, 1, 1]}, {[0, 0, 0], [0, 1, 1], [1, 0, 0], [1, 0, 1], [1, 1, 1]}, {[0, 0, 0], [1, 0, 0], [1, 0, 1], [1, 1, 0], [1, 1, 1]}, {[0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 1, 1], [1, 0, 0], [1, 1, 1]}, {[0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 1, 1], [1, 0, 1], [1, 1, 1]}, {[0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 1, 1], [1, 1, 0], [1, 1, 1]}, {[0, 0, 0], [0, 0, 1], [0, 1, 0], [1, 0, 0], [1, 0, 1], [1, 1, 1]}, {[0, 0, 0], [0, 0, 1], [0, 1, 0], [1, 0, 0], [1, 1, 0], [1, 1, 1]}, {[0, 0, 0], [0, 0, 1], [0, 1, 0], [1, 0, 1], [1, 1, 0], [1, 1, 1]}, {[0, 0, 0], [0, 0, 1], [0, 1, 1], [1, 0, 0], [1, 0, 1], [1, 1, 1]}, {[0, 0, 0], [0, 0, 1], [0, 1, 1], [1, 0, 1], [1, 1, 0], [1, 1, 1]}, {[0, 0, 0], [0, 0, 1], [1, 0, 0], [1, 0, 1], [1, 1, 0], [1, 1, 1]}, {[0, 0, 0], [0, 1, 0], [0, 1, 1], [1, 0, 0], [1, 0, 1], [1, 1, 1]}, {[0, 0, 0], [0, 1, 0], [0, 1, 1], [1, 0, 0], [1, 1, 0], [1, 1, 1]}, {[0, 0, 0], [0, 1, 0], [0, 1, 1], [1, 0, 1], [1, 1, 0], [1, 1, 1]}, {[0, 0, 0], [0, 1, 0], [1, 0, 0], [1, 0, 1], [1, 1, 0], [1, 1, 1]}, {[0, 0, 0], [0, 1, 1], [1, 0, 0], [1, 0, 1], [1, 1, 0], [1, 1, 1]}, {[0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 1, 1], [1, 0, 0], [1, 0, 1], [1, 1, 1]}, {[0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 1, 1], [1, 0, 0], [1, 1, 0], [1, 1, 1]}, {[0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 1, 1], [1, 0, 1], [1, 1, 0], [1, 1, 1]}, {[0, 0, 0], [0, 0, 1], [0, 1, 0], [1, 0, 0], [1, 0, 1], [1, 1, 0], [1, 1, 1]}, {[0, 0, 0], [0, 0, 1], [0, 1, 1], [1, 0, 0], [1, 0, 1], [1, 1, 0], [1, 1, 1]}, {[0, 0, 0], [0, 1, 0], [0, 1, 1], [1, 0, 0], [1, 0, 1], [1, 1, 0], [1, 1, 1]}, {[0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 1, 1], [1, 0, 0], [1, 0, 1], [1, 1, 0], [1, 1, 1]}} #AUA(k): inputs a positive integer k, and outputs the set of sets #of patterns of length k that are almost unavoidable, that is #if asymptotically, the number of words of length n avoiding that #set of patterns has polynomial growth. AUA:=proc(k) local A,B,FP,T,allPat,GF,d,roots,AUAP: A:={0,1}: allPat:=powerset(AW(A,k)): AUAP:={}: for FP in allPat do: GF:=GFunT(A,B,FP,T): d:=denom(GF): roots:={solve(d,T)}: if big1(roots) or d=1 then AUAP:=AUAP union {FP}: fi: od: AUAP: end: #big1(S): input a set S and returns true iff all elts of S have #absolute value at least 1. big1:=proc(S) local x: for x in S do if evalf(abs(x))<1 then RETURN(false): fi: od: RETURN(true): end: #AUA(1) #{{[0]}, {[1]}, {[0], [1]}} #AUA(2) #{{[0, 1]}, {[1, 0]}, {[0, 0], [0, 1]}, {[0, 0], [1, 0]}, {[0, 0], [1, 1]}, {[0, 1], [1, 0]}, {[0, 1], [1, 1]}, {[1, 0], [1, 1]}, {[0, 0], [0, 1], [1, 0]}, {[0, 0], [0, 1], [1, 1]}, {[0, 0], [1, 0], [1, 1]}, {[0, 1], [1, 0], [1, 1]}, {[0, 0], [0, 1], [1, 0], [1, 1]}} #AUA(3) #{{[0, 0, 1], [0, 1, 1]}, {[0, 0, 1], [1, 0, 1]}, {[0, 0, 1], [1, 1, 0]}, {[0, 1, 0], [0, 1, 1]}, {[0, 1, 0], [1, 1, 0]}, {[0, 1, 1], [1, 0, 0]}, {[1, 0, 0], [1, 0, 1]}, {[1, 0, 0], [1, 1, 0]}, {[0, 0, 0], [0, 0, 1], [0, 1, 1]}, {[0, 0, 0], [0, 0, 1], [1, 0, 1]}, {[0, 0, 0], [0, 0, 1], [1, 1, 0]}, {[0, 0, 0], [0, 1, 0], [0, 1, 1]}, {[0, 0, 0], [0, 1, 0], [1, 1, 0]}, {[0, 0, 0], [0, 1, 1], [1, 0, 0]}, {[0, 0, 0], [0, 1, 1], [1, 0, 1]}, {[0, 0, 0], [1, 0, 0], [1, 0, 1]}, {[0, 0, 0], [1, 0, 0], [1, 1, 0]}, {[0, 0, 0], [1, 0, 1], [1, 1, 0]}, {[0, 0, 1], [0, 1, 0], [0, 1, 1]}, {[0, 0, 1], [0, 1, 0], [1, 0, 1]}, {[0, 0, 1], [0, 1, 0], [1, 1, 0]}, {[0, 0, 1], [0, 1, 0], [1, 1, 1]}, {[0, 0, 1], [0, 1, 1], [1, 0, 0]}, {[0, 0, 1], [0, 1, 1], [1, 0, 1]}, {[0, 0, 1], [0, 1, 1], [1, 1, 0]}, {[0, 0, 1], [0, 1, 1], [1, 1, 1]}, {[0, 0, 1], [1, 0, 0], [1, 0, 1]}, {[0, 0, 1], [1, 0, 0], [1, 1, 0]}, {[0, 0, 1], [1, 0, 1], [1, 1, 0]}, {[0, 0, 1], [1, 0, 1], [1, 1, 1]}, {[0, 0, 1], [1, 1, 0], [1, 1, 1]}, {[0, 1, 0], [0, 1, 1], [1, 0, 0]}, {[0, 1, 0], [0, 1, 1], [1, 0, 1]}, {[0, 1, 0], [0, 1, 1], [1, 1, 0]}, {[0, 1, 0], [0, 1, 1], [1, 1, 1]}, {[0, 1, 0], [1, 0, 0], [1, 0, 1]}, {[0, 1, 0], [1, 0, 0], [1, 1, 0]}, {[0, 1, 0], [1, 0, 0], [1, 1, 1]}, {[0, 1, 0], [1, 0, 1], [1, 1, 0]}, {[0, 1, 0], [1, 1, 0], [1, 1, 1]}, {[0, 1, 1], [1, 0, 0], [1, 0, 1]}, {[0, 1, 1], [1, 0, 0], [1, 1, 0]}, {[0, 1, 1], [1, 0, 0], [1, 1, 1]}, {[1, 0, 0], [1, 0, 1], [1, 1, 0]}, {[1, 0, 0], [1, 0, 1], [1, 1, 1]}, {[1, 0, 0], [1, 1, 0], [1, 1, 1]}, {[0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 1, 1]}, {[0, 0, 0], [0, 0, 1], [0, 1, 0], [1, 0, 1]}, {[0, 0, 0], [0, 0, 1], [0, 1, 0], [1, 1, 0]}, {[0, 0, 0], [0, 0, 1], [0, 1, 0], [1, 1, 1]}, {[0, 0, 0], [0, 0, 1], [0, 1, 1], [1, 0, 0]}, {[0, 0, 0], [0, 0, 1], [0, 1, 1], [1, 0, 1]}, {[0, 0, 0], [0, 0, 1], [0, 1, 1], [1, 1, 0]}, {[0, 0, 0], [0, 0, 1], [0, 1, 1], [1, 1, 1]}, {[0, 0, 0], [0, 0, 1], [1, 0, 0], [1, 0, 1]}, {[0, 0, 0], [0, 0, 1], [1, 0, 0], [1, 1, 0]}, {[0, 0, 0], [0, 0, 1], [1, 0, 1], [1, 1, 0]}, {[0, 0, 0], [0, 0, 1], [1, 0, 1], [1, 1, 1]}, {[0, 0, 0], [0, 0, 1], [1, 1, 0], [1, 1, 1]}, {[0, 0, 0], [0, 1, 0], [0, 1, 1], [1, 0, 0]}, {[0, 0, 0], [0, 1, 0], [0, 1, 1], [1, 0, 1]}, {[0, 0, 0], [0, 1, 0], [0, 1, 1], [1, 1, 0]}, {[0, 0, 0], [0, 1, 0], [0, 1, 1], [1, 1, 1]}, {[0, 0, 0], [0, 1, 0], [1, 0, 0], [1, 0, 1]}, {[0, 0, 0], [0, 1, 0], [1, 0, 0], [1, 1, 0]}, {[0, 0, 0], [0, 1, 0], [1, 0, 0], [1, 1, 1]}, {[0, 0, 0], [0, 1, 0], [1, 0, 1], [1, 1, 0]}, {[0, 0, 0], [0, 1, 0], [1, 0, 1], [1, 1, 1]}, {[0, 0, 0], [0, 1, 0], [1, 1, 0], [1, 1, 1]}, {[0, 0, 0], [0, 1, 1], [1, 0, 0], [1, 0, 1]}, {[0, 0, 0], [0, 1, 1], [1, 0, 0], [1, 1, 0]}, {[0, 0, 0], [0, 1, 1], [1, 0, 0], [1, 1, 1]}, {[0, 0, 0], [0, 1, 1], [1, 0, 1], [1, 1, 0]}, {[0, 0, 0], [0, 1, 1], [1, 0, 1], [1, 1, 1]}, {[0, 0, 0], [1, 0, 0], [1, 0, 1], [1, 1, 0]}, {[0, 0, 0], [1, 0, 0], [1, 0, 1], [1, 1, 1]}, {[0, 0, 0], [1, 0, 0], [1, 1, 0], [1, 1, 1]}, {[0, 0, 0], [1, 0, 1], [1, 1, 0], [1, 1, 1]}, {[0, 0, 1], [0, 1, 0], [0, 1, 1], [1, 0, 0]}, {[0, 0, 1], [0, 1, 0], [0, 1, 1], [1, 0, 1]}, {[0, 0, 1], [0, 1, 0], [0, 1, 1], [1, 1, 0]}, {[0, 0, 1], [0, 1, 0], [0, 1, 1], [1, 1, 1]}, {[0, 0, 1], [0, 1, 0], [1, 0, 0], [1, 0, 1]}, {[0, 0, 1], [0, 1, 0], [1, 0, 0], [1, 1, 0]}, {[0, 0, 1], [0, 1, 0], [1, 0, 0], [1, 1, 1]}, {[0, 0, 1], [0, 1, 0], [1, 0, 1], [1, 1, 0]}, {[0, 0, 1], [0, 1, 0], [1, 0, 1], [1, 1, 1]}, {[0, 0, 1], [0, 1, 0], [1, 1, 0], [1, 1, 1]}, {[0, 0, 1], [0, 1, 1], [1, 0, 0], [1, 0, 1]}, {[0, 0, 1], [0, 1, 1], [1, 0, 0], [1, 1, 0]}, {[0, 0, 1], [0, 1, 1], [1, 0, 0], [1, 1, 1]}, {[0, 0, 1], [0, 1, 1], [1, 0, 1], [1, 1, 0]}, {[0, 0, 1], [0, 1, 1], [1, 0, 1], [1, 1, 1]}, {[0, 0, 1], [0, 1, 1], [1, 1, 0], [1, 1, 1]}, {[0, 0, 1], [1, 0, 0], [1, 0, 1], [1, 1, 0]}, {[0, 0, 1], [1, 0, 0], [1, 0, 1], [1, 1, 1]}, {[0, 0, 1], [1, 0, 0], [1, 1, 0], [1, 1, 1]}, {[0, 0, 1], [1, 0, 1], [1, 1, 0], [1, 1, 1]}, {[0, 1, 0], [0, 1, 1], [1, 0, 0], [1, 0, 1]}, {[0, 1, 0], [0, 1, 1], [1, 0, 0], [1, 1, 0]}, {[0, 1, 0], [0, 1, 1], [1, 0, 0], [1, 1, 1]}, {[0, 1, 0], [0, 1, 1], [1, 0, 1], [1, 1, 0]}, {[0, 1, 0], [0, 1, 1], [1, 0, 1], [1, 1, 1]}, {[0, 1, 0], [0, 1, 1], [1, 1, 0], [1, 1, 1]}, {[0, 1, 0], [1, 0, 0], [1, 0, 1], [1, 1, 0]}, {[0, 1, 0], [1, 0, 0], [1, 0, 1], [1, 1, 1]}, {[0, 1, 0], [1, 0, 0], [1, 1, 0], [1, 1, 1]}, {[0, 1, 0], [1, 0, 1], [1, 1, 0], [1, 1, 1]}, {[0, 1, 1], [1, 0, 0], [1, 0, 1], [1, 1, 0]}, {[0, 1, 1], [1, 0, 0], [1, 0, 1], [1, 1, 1]}, {[0, 1, 1], [1, 0, 0], [1, 1, 0], [1, 1, 1]}, {[1, 0, 0], [1, 0, 1], [1, 1, 0], [1, 1, 1]}, {[0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 1, 1], [1, 0, 0]}, {[0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 1, 1], [1, 0, 1]}, {[0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 1, 1], [1, 1, 0]}, {[0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 1, 1], [1, 1, 1]}, {[0, 0, 0], [0, 0, 1], [0, 1, 0], [1, 0, 0], [1, 0, 1]}, {[0, 0, 0], [0, 0, 1], [0, 1, 0], [1, 0, 0], [1, 1, 0]}, {[0, 0, 0], [0, 0, 1], [0, 1, 0], [1, 0, 0], [1, 1, 1]}, {[0, 0, 0], [0, 0, 1], [0, 1, 0], [1, 0, 1], [1, 1, 0]}, {[0, 0, 0], [0, 0, 1], [0, 1, 0], [1, 0, 1], [1, 1, 1]}, {[0, 0, 0], [0, 0, 1], [0, 1, 0], [1, 1, 0], [1, 1, 1]}, {[0, 0, 0], [0, 0, 1], [0, 1, 1], [1, 0, 0], [1, 0, 1]}, {[0, 0, 0], [0, 0, 1], [0, 1, 1], [1, 0, 0], [1, 1, 0]}, {[0, 0, 0], [0, 0, 1], [0, 1, 1], [1, 0, 0], [1, 1, 1]}, {[0, 0, 0], [0, 0, 1], [0, 1, 1], [1, 0, 1], [1, 1, 0]}, {[0, 0, 0], [0, 0, 1], [0, 1, 1], [1, 0, 1], [1, 1, 1]}, {[0, 0, 0], [0, 0, 1], [0, 1, 1], [1, 1, 0], [1, 1, 1]}, {[0, 0, 0], [0, 0, 1], [1, 0, 0], [1, 0, 1], [1, 1, 0]}, {[0, 0, 0], [0, 0, 1], [1, 0, 0], [1, 0, 1], [1, 1, 1]}, {[0, 0, 0], [0, 0, 1], [1, 0, 0], [1, 1, 0], [1, 1, 1]}, {[0, 0, 0], [0, 0, 1], [1, 0, 1], [1, 1, 0], [1, 1, 1]}, {[0, 0, 0], [0, 1, 0], [0, 1, 1], [1, 0, 0], [1, 0, 1]}, {[0, 0, 0], [0, 1, 0], [0, 1, 1], [1, 0, 0], [1, 1, 0]}, {[0, 0, 0], [0, 1, 0], [0, 1, 1], [1, 0, 0], [1, 1, 1]}, {[0, 0, 0], [0, 1, 0], [0, 1, 1], [1, 0, 1], [1, 1, 0]}, {[0, 0, 0], [0, 1, 0], [0, 1, 1], [1, 0, 1], [1, 1, 1]}, {[0, 0, 0], [0, 1, 0], [0, 1, 1], [1, 1, 0], [1, 1, 1]}, {[0, 0, 0], [0, 1, 0], [1, 0, 0], [1, 0, 1], [1, 1, 0]}, {[0, 0, 0], [0, 1, 0], [1, 0, 0], [1, 0, 1], [1, 1, 1]}, {[0, 0, 0], [0, 1, 0], [1, 0, 0], [1, 1, 0], [1, 1, 1]}, {[0, 0, 0], [0, 1, 0], [1, 0, 1], [1, 1, 0], [1, 1, 1]}, {[0, 0, 0], [0, 1, 1], [1, 0, 0], [1, 0, 1], [1, 1, 0]}, {[0, 0, 0], [0, 1, 1], [1, 0, 0], [1, 0, 1], [1, 1, 1]}, {[0, 0, 0], [0, 1, 1], [1, 0, 0], [1, 1, 0], [1, 1, 1]}, {[0, 0, 0], [0, 1, 1], [1, 0, 1], [1, 1, 0], [1, 1, 1]}, {[0, 0, 0], [1, 0, 0], [1, 0, 1], [1, 1, 0], [1, 1, 1]}, {[0, 0, 1], [0, 1, 0], [0, 1, 1], [1, 0, 0], [1, 0, 1]}, {[0, 0, 1], [0, 1, 0], [0, 1, 1], [1, 0, 0], [1, 1, 0]}, {[0, 0, 1], [0, 1, 0], [0, 1, 1], [1, 0, 0], [1, 1, 1]}, {[0, 0, 1], [0, 1, 0], [0, 1, 1], [1, 0, 1], [1, 1, 0]}, {[0, 0, 1], [0, 1, 0], [0, 1, 1], [1, 0, 1], [1, 1, 1]}, {[0, 0, 1], [0, 1, 0], [0, 1, 1], [1, 1, 0], [1, 1, 1]}, {[0, 0, 1], [0, 1, 0], [1, 0, 0], [1, 0, 1], [1, 1, 0]}, {[0, 0, 1], [0, 1, 0], [1, 0, 0], [1, 0, 1], [1, 1, 1]}, {[0, 0, 1], [0, 1, 0], [1, 0, 0], [1, 1, 0], [1, 1, 1]}, {[0, 0, 1], [0, 1, 0], [1, 0, 1], [1, 1, 0], [1, 1, 1]}, {[0, 0, 1], [0, 1, 1], [1, 0, 0], [1, 0, 1], [1, 1, 0]}, {[0, 0, 1], [0, 1, 1], [1, 0, 0], [1, 0, 1], [1, 1, 1]}, {[0, 0, 1], [0, 1, 1], [1, 0, 0], [1, 1, 0], [1, 1, 1]}, {[0, 0, 1], [0, 1, 1], [1, 0, 1], [1, 1, 0], [1, 1, 1]}, {[0, 0, 1], [1, 0, 0], [1, 0, 1], [1, 1, 0], [1, 1, 1]}, {[0, 1, 0], [0, 1, 1], [1, 0, 0], [1, 0, 1], [1, 1, 0]}, {[0, 1, 0], [0, 1, 1], [1, 0, 0], [1, 0, 1], [1, 1, 1]}, {[0, 1, 0], [0, 1, 1], [1, 0, 0], [1, 1, 0], [1, 1, 1]}, {[0, 1, 0], [0, 1, 1], [1, 0, 1], [1, 1, 0], [1, 1, 1]}, {[0, 1, 0], [1, 0, 0], [1, 0, 1], [1, 1, 0], [1, 1, 1]}, {[0, 1, 1], [1, 0, 0], [1, 0, 1], [1, 1, 0], [1, 1, 1]}, {[0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 1, 1], [1, 0, 0], [1, 0, 1]}, {[0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 1, 1], [1, 0, 0], [1, 1, 0]}, {[0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 1, 1], [1, 0, 0], [1, 1, 1]}, {[0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 1, 1], [1, 0, 1], [1, 1, 0]}, {[0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 1, 1], [1, 0, 1], [1, 1, 1]}, {[0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 1, 1], [1, 1, 0], [1, 1, 1]}, {[0, 0, 0], [0, 0, 1], [0, 1, 0], [1, 0, 0], [1, 0, 1], [1, 1, 0]}, {[0, 0, 0], [0, 0, 1], [0, 1, 0], [1, 0, 0], [1, 0, 1], [1, 1, 1]}, {[0, 0, 0], [0, 0, 1], [0, 1, 0], [1, 0, 0], [1, 1, 0], [1, 1, 1]}, {[0, 0, 0], [0, 0, 1], [0, 1, 0], [1, 0, 1], [1, 1, 0], [1, 1, 1]}, {[0, 0, 0], [0, 0, 1], [0, 1, 1], [1, 0, 0], [1, 0, 1], [1, 1, 0]}, {[0, 0, 0], [0, 0, 1], [0, 1, 1], [1, 0, 0], [1, 0, 1], [1, 1, 1]}, {[0, 0, 0], [0, 0, 1], [0, 1, 1], [1, 0, 0], [1, 1, 0], [1, 1, 1]}, {[0, 0, 0], [0, 0, 1], [0, 1, 1], [1, 0, 1], [1, 1, 0], [1, 1, 1]}, {[0, 0, 0], [0, 0, 1], [1, 0, 0], [1, 0, 1], [1, 1, 0], [1, 1, 1]}, {[0, 0, 0], [0, 1, 0], [0, 1, 1], [1, 0, 0], [1, 0, 1], [1, 1, 0]}, {[0, 0, 0], [0, 1, 0], [0, 1, 1], [1, 0, 0], [1, 0, 1], [1, 1, 1]}, {[0, 0, 0], [0, 1, 0], [0, 1, 1], [1, 0, 0], [1, 1, 0], [1, 1, 1]}, {[0, 0, 0], [0, 1, 0], [0, 1, 1], [1, 0, 1], [1, 1, 0], [1, 1, 1]}, {[0, 0, 0], [0, 1, 0], [1, 0, 0], [1, 0, 1], [1, 1, 0], [1, 1, 1]}, {[0, 0, 0], [0, 1, 1], [1, 0, 0], [1, 0, 1], [1, 1, 0], [1, 1, 1]}, {[0, 0, 1], [0, 1, 0], [0, 1, 1], [1, 0, 0], [1, 0, 1], [1, 1, 0]}, {[0, 0, 1], [0, 1, 0], [0, 1, 1], [1, 0, 0], [1, 0, 1], [1, 1, 1]}, {[0, 0, 1], [0, 1, 0], [0, 1, 1], [1, 0, 0], [1, 1, 0], [1, 1, 1]}, {[0, 0, 1], [0, 1, 0], [0, 1, 1], [1, 0, 1], [1, 1, 0], [1, 1, 1]}, {[0, 0, 1], [0, 1, 0], [1, 0, 0], [1, 0, 1], [1, 1, 0], [1, 1, 1]}, {[0, 0, 1], [0, 1, 1], [1, 0, 0], [1, 0, 1], [1, 1, 0], [1, 1, 1]}, {[0, 1, 0], [0, 1, 1], [1, 0, 0], [1, 0, 1], [1, 1, 0], [1, 1, 1]}, {[0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 1, 1], [1, 0, 0], [1, 0, 1], [1, 1, 0]}, {[0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 1, 1], [1, 0, 0], [1, 0, 1], [1, 1, 1]}, {[0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 1, 1], [1, 0, 0], [1, 1, 0], [1, 1, 1]}, {[0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 1, 1], [1, 0, 1], [1, 1, 0], [1, 1, 1]}, {[0, 0, 0], [0, 0, 1], [0, 1, 0], [1, 0, 0], [1, 0, 1], [1, 1, 0], [1, 1, 1]}, {[0, 0, 0], [0, 0, 1], [0, 1, 1], [1, 0, 0], [1, 0, 1], [1, 1, 0], [1, 1, 1]}, {[0, 0, 0], [0, 1, 0], [0, 1, 1], [1, 0, 0], [1, 0, 1], [1, 1, 0], [1, 1, 1]}, {[0, 0, 1], [0, 1, 0], [0, 1, 1], [1, 0, 0], [1, 0, 1], [1, 1, 0], [1, 1, 1]}, {[0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 1, 1], [1, 0, 0], [1, 0, 1], [1, 1, 0], [1, 1, 1]}} #IsSubPattern(pat1,pat2,B): inputs two patterns, pat1, pat2 and #outputs true if and only if any occurrence of pat1 implies an #occurence of pat2, i.e. pat2 is a subpattern of pat1. IsSubPattern:=proc(pat1,pat2,B) IsBad1(pat1,pat2,B): end: #IsBad1(w,fp1,B): returns true if and only if #the word w contains the single pattern fp1. IsBad1:=proc(w,fp1,B) local fp2,w1: option remember: if nops(fp1)>nops(w) then RETURN(false): fi: if fp1=[] then RETURN(true): fi: w1:=w[2..nops(w)]: if IsBad1(w1,fp1,B) then RETURN(true): fi: fp2:=fp1[2..nops(fp1)]: if (w[1]=fp1[1] or fp1[1]=B) and IsBad1(w1[1..nops(fp2)],fp2,B) then RETURN(true): fi: RETURN(false): end: #MinimalFP(B,FP): inputs a symbol for blank, B, and a set of #patterns (expressed as lists), and returns a subset of FP, #whose avoidance implies the avoidance of all the other patterns. #For example, #MinimalFP(B,{[1,1,1],[1,1,1,1],[1,B,1],[1,2,1]}); #should return #{[1,B,1]} MinimalFP:=proc(B,FP) local SFP,MFP,P: SFP:=powerset(FP): for MFP in SFP do if IsEquivFP(B,FP,MFP) then RETURN(MFP): fi: od: end: #IsEquivFP(B,FP1,FP2): inputs two sets of forbidden patterns #where FP2 is a subset of FP1 #and outputs true iff they are equivalent. IsEquivFP:=proc(B,FP1,FP2) local p1,p2,c: for p1 in FP1 do c:=0: for p2 in FP2 do if IsSubPattern(p1,p2,B) then c:=c+1: fi: od: if c=0 then RETURN(false): fi: od: RETURN(true): end: #ConvWalkToC(W): inputs a walk W (list in alphabet {-1,1,-2,2}) #and outputs the corresponding walk on the complex plane #in the alphabet {-1,1,-I,I}. ConvWalkToC:=proc(W) local CW,i: CW:=[]: for i from 1 to nops(W) do if abs(W[i])=2 then CW:=[op(CW),W[i]/2*I]: else CW:=[op(CW),W[i]]: fi: od: CW: end: #SAW(n): inputs a non-negative integer n, and outputs the #set of all self-avoiding walks of length n. For example, #SAW(2); #should yield #{[1,1],[1,2],[1,-2],[2,2],[2,1],[2,-1], [-1,-1],[-1,-2],[-1,2],[-2,-2],[-2,-1],[-2,1]} SAW:=proc(n) local A,SAW1,w,a,walk,cwalk,S,AllSAW: option remember: A:={-1,1,-2,2}: if n=0 then {[]}: else SAW1:=SAW(n-1): AllSAW:={}: for w in SAW1 do for a in A do walk:=[op(w),a]: cwalk:=ConvWalkToC(walk): S:={seq(sum(cwalk[j],j=nops(cwalk)-2*i+1..nops(cwalk)),i=1..nops(cwalk)/2)}: if not 0 in S then AllSAW:=AllSAW union {walk}: fi: od: od: AllSAW: fi: end: #seq(nops(SAW(n)),n=0..8); #1, 4, 12, 36, 100, 284, 780, 2172, 5916 #This is in Sloane. #Number of n-step self-avoiding walks on square lattice. #SAP(n): inputs a non-negative integer n, and outputs the #set of all self-avoiding polygons of length 2n. For example, #SAP(1); #should yield #{[1,-1],[-1,1],[2,-2],[-2,2]} SAP:=proc(n) local A,SAP1,w,a,walk,cwalk,S,AllSAP: option remember: A:={-1,1,-2,2}: if n=0 then {[]}: else SAP1:=SAW(2*n-1): AllSAP:={}: for w in SAP1 do for a in A do walk:=[op(w),a]: cwalk:=ConvWalkToC(walk): S:={seq(sum(cwalk[j],j=nops(cwalk)-2*i+1..nops(cwalk)),i=1..nops(cwalk)/2-1)}: if not 0 in S and sum(cwalk[j],j=1..nops(cwalk))=0 then AllSAP:=AllSAP union {walk}: fi: od: od: AllSAP: fi: end: #GFsawd(d,T): inputs a pos. integer d, and a variable T, #and outputs the rational function in T whose Maclaurin #coefficient of T^n would give the number of #memory-d-self-avoiding walks of length n. For example, #GFsawd(1,T); #should yield (1+T)/(1-3*T) . GFsawd:=proc(d,T) local A,B,FP,i: A:={-1,1,-2,2}: FP:={}: for i from 1 to d do FP:=FP union SAP(i): od: GFunT(A,B,FP,T): end: #GFsawd(1,T); #-(T+1)/(3*T-1) #1, 4, 12, 36, 108, 324, 972, 2916, 8748, 26244, 78732, 236196, 708588, 2125764, 6377292, 19131876, 57395628, 172186884, 516560652, 1549681956, 4649045868 #GFsawd(2,T); #-(2*T^2+1+3*T^3+2*T)/(T^3+2*T^2+2*T-1) #1, 4, 12, 36, 100, 284, 804, 2276, 6444, 18244, 51652, 146236, 414020, 1172164, 3318604, 9395556, 26600484, 75310684, 213217892, 603657636, 1709061740 #GFsawd(3,T); #-(8*T^8+3*T^7-T^6+8*T^5+3*T^4+4*T^3+2*T^2+2*T+1)/((T+1)*(T^6+T^3-T^2+3*T-1)) #1, 4, 12, 36, 100, 284, 780, 2172, 6028, 16732, 46436, 128892, 357748, 992964, 2756060, 7649700, 21232436, 58932564, 163572700, 454010940, 1260148740 #GFsawd(4,T); #-(1+2*T+101*T^36+52*T^37-16*T^38-72*T^39+14*T^5+41*T^7+9*T^6+6*T^3-80*T^40-94*T^31+50*T^23-82*T^24+3*T^2+5*T^10+22*T^11+49*T^34+32*T^44-4*T^19-33*T^41-61*T^18+24*T^45+8*T^46+24*T^25+16*T^27+61*T^29+2*T^26+47*T^28-117*T^16+6*T^4-36*T^14-132*T^15+28*T^9-54*T^33-21*T^12-T^13+24*T^43-117*T^30+74*T^21+141*T^22+11*T^42+141*T^35+84*T^20-153*T^17-117*T^32-18*T^8)/(-1+2*T-T^36-4*T^37+2*T^5-5*T^7-T^6+2*T^3-2*T^31+2*T^23-2*T^24+T^2+3*T^10-2*T^11+3*T^34+12*T^19+T^41+T^18+4*T^25+4*T^27-5*T^29+2*T^26-3*T^28-7*T^16+2*T^4-8*T^14-8*T^15-4*T^9+2*T^33+T^12-7*T^13-7*T^30+6*T^21-13*T^22+T^42+3*T^35+4*T^20+9*T^17+5*T^32+2*T^8) #1, 4, 12, 36, 100, 284, 780, 2172, 5916, 16268, 44660, 122596, 336428, 923316, 2533924, 6954340, 19085796, 52380228, 143755252, 394530428, 1082772220 #Only the first is in Sloane.