#C5.txt, Sept. 22, 2016 (Math640 (Fall 2016), Rutgers University)
#Goulden-Jackson
Help:=proc(): print(` GJ(A,BadW,t), Clu(A,BadW,t) `): end:

#GJ(A,BadW,t): inputs a finite alphabet A, and a set of words in A , "the bad words"
#and a variable t, outputs a rational function in t whose Maclaurin coef. of t^n
#is the number of n-letter words in A AVOIDING (as consecutive subwords) ANY
#bad words
GJ:=proc(A,BadW,t) local C:
C:=Clu(A,BadW,t):
normal(1/(1- t*nops(A)-C)):

end:

#Clu(A,BadW,t): inputs a finite alphabet A, and a set of words in A , "the bad words"
#and a variable t, outputs the cluster generating function
Clu:=proc(A,BadW,t) local eq,var,x,w,v,eq1,i:
eq:={}:
var:={}:

for  w in BadW do
 var:=var union {x[w]}:
 eq1:=x[w]- (t^nops(w))*(-1):
  for v in BadW do
    for i from 1 to min(nops(v)-1,nops(w)-1) do
     if v[nops(v)-i+1..nops(v)]=w[1..i] then 
        eq1:=eq1-t^(nops(w)-i)*(-1)*x[v]:
     fi:
    od:
 od:
 eq:=eq union {eq1}:
od:

 var:=solve(eq,var):


  normal(add(subs(var,x[w]),w in BadW)):
end: