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: