print(` Version of April 18, 1997`):
print(`This is GJseries, A Maple program`):
print(`that finds a series expansion for the generating function of`):
print(`the enumerating sequence of words avoiding a finite set of`):
print(`of MISTAKES.`):
print(`It uses a clever implementation of the Goulden-Jackson method`):
lprint(``):
print(`Written by John Noonan and Doron Zeilberger.`):
lprint(``):
print(`It is one of the packages accompanying Noonan and Zeilberger's `):
print(`article: "The Goulden-Jackson Cluster Method: Extensions,`):
print(`Applications, and Implementations", where the method`):
print(`is explained in detail, and then extended and generalized in`):
print(`various directions. `):
 
lprint(``):
print(`The paper, and the packages, including the present one`):
print(`is available from http://www.math.temple.edu/~zeilberg/gj.html`):
lprint(``):
print(`For general help, and a list of the available functions,`):
print(` type "ezra();". For specific help type "ezra(procedure_name)" `):
lprint(``):
lprint(`Please report to: zeilberg@math.temple.edu `):
 
ezra:=proc()
if args=NULL then
print(` GJseries `):
print(`A Maple program`):
print(` for finding series exapansions`):
print(`for the number of words avoiding a prescribed, finite, set of`):
print(`"mistakes". Contains Procedures `):
print(` GJs, GJ , bdok `):
 
print(` For specific help type "ezra(procedure_name)" `):
fi:
 
 
 
if nops([args])=1 and op(1,[args])=`GJs` then
print(`GJs(NUMLETTERS,MISTAKES,s,L) finds the first L terms `):
print(`of the sequence: wt. enumer. of words of length n, according to`):
print(`the weight s^(number of factors `):
print(`( i.e. subsequences of conssecutive letters) that belong to the`):
print(`set of lists MISTAKES), where the number of letters of the alphabet`):
print(` is NUMLETTERS. For example to find the sequnce a_n(s) (0<=n<=15)`):
print(`where a_n:= wt. enumerator of words in {1,2,3} with MISTAKES=`):
print(` {123,231,312}. type GJs(3,{[1,2,3],[2,3,1],[3,1,2]},s,15)`):
fi:
 
 
 
if nops([args])=1 and op(1,[args])=`GJ` then
print(`GJ(NUMLETTERS,MISTAKES,L) finds the first L terms `):
print(`of the sequence: number of words of length n,  that avoid`):
print(`as factors,`):
print(`( i.e. subsequences of conssecutive letters) the members of the `):
print(`set of lists MISTAKES), where the number of letters of the alphabet`):
print(` is NUMLETTERS. For example to find the sequnce a_n (0<=n<=15)`):
print(`where a_n:= wt. numbers of words in {1,2,3} without factors in `):
print(` MISTAKES={123,231,312}. type GJ(3,{[1,2,3],[2,3,1],[3,1,2]},15)`):
fi:
 
 
if nops([args])=1 and op(1,[args])=`Lclusts` then
 print(`Lclust(MISTAKES,NUTERMS,s): computes the first NUTERMS terms of`):
 print(`the L-cluster expansion of the g.f. if the set of mistakes is`):
 print(` MISTAKES . For example Lclusts({[1,2]},10,s) `):
fi:
 
 
if nops([args])=1 and op(1,[args])=`Lclust` then
 print(`Lclust(MISTAKES,NUTERMS): computes the first NUTERMS terms of`):
 print(`the L-cluster expansion of the g.f. if the set of mistakes is`):
 print(` MISTAKES . For example Lclust({[1,2]},10,s) `):
fi:
 
 
if nops([args])=1 and op(1,[args])=`bdok` then
 print(`bdok(MISTAKES) checks that the setof Mistakes is minimal with `):
 print(`respect to containment`):
fi:
end:
 
 
#bdok(MISTAKES) checks that the set of Mistakes is minimal with 
#respect to containment
 
bdok:=proc(MISTAKES)
local mila,i,j,k,mila1:
 
for i from 1 to nops(MISTAKES) do
mila:=op(i,MISTAKES):
 
for j from 1 to nops(mila) do
 for k from j to nops(mila) do
  mila1:=[op(j..k,mila)]:
  if k-j<nops(mila)-1 and member(mila1,MISTAKES) then
   RETURN(0):
  fi:
 od:
od:
od:
1:
end:
 
 
Lclusts:=proc(MISTAKES,NUTERMS,s)
local LEN,SUFFI,i,j,x,Lt,LIS,mila,EFES,I1,r,pref,tot,gu,resh,i1,suffi:
 
#LIS is the output: the list of coeffs of the L-cluster expansion
#here we initialize it to the empty list
LIS:=[]:
 
#SUFFI is the set of all suffixes (tails) of all words
SUFFI:={[]}:
 
for i from 1 to nops(MISTAKES) do
 mila:=op(i,MISTAKES):
 
 for j from 2 to nops(mila) do
  SUFFI:=SUFFI union {[op(j..nops(mila),mila)]}:
 od:
od:
 
#LEN is the maximum length of a mistake
LEN:=0:
 
for i from 1 to nops(MISTAKES) do
  mila:=op(i,MISTAKES):
  if nops(mila)>LEN then
    LEN:=nops(mila):
  fi:
od:
 
#Lt[word] is an inedex variable whose argument, word, is a mistake or
#or prefix of a mistake, and which is a list of length LEN-1 that describes
#the coeffs. of the wt. enumerators of L-clusters at the previous LEN-1 
#coeffs. in the case of word being a mistake. If word is a suffix of a mistake
#then it is the sum of the coeffs. of all
#wt. enumerators of mistakes that end with [word] 
 
#We now initialize all these lists Lt[word] to be the zero lists
 
EFES:=[seq(0,j=1..LEN-1)]:
 
 
for i from 1 to nops(SUFFI) do
mila:=op(i,SUFFI):
Lt[op(mila)]:=EFES:
od:
 
#x[word] is the new coeffs. of t^(I1) to be computed using the
#recurrences, in case word is a mistake and the sum of all these
#x[mistakes] over the mistakes that end in word if word is in PREFS
 
for I1 from 0 to NUTERMS do
 
tot:=0:
#we now initialize all x[word]'s to be 0
#when word is a suffix of a mistake
 
for i from 1 to nops(SUFFI) do
mila:=op(i,SUFFI):
x[op(mila)]:=0:
od:
 
for i from 1 to nops(MISTAKES) do
#we now initialize gu to be (s-1)*delta(I1,length(mistake)) 
#when word is a mistake
 
  mila:=op(i,MISTAKES):
 
  gu:=0:
 
  if nops(mila)=I1 then
   gu:=s-1:
  fi:
 
#we now use the recurrence to compute x[mistake]
 
  for r from 1 to nops(mila)-1 do
    pref:=[op(1..nops(mila)-r,mila)]:
 
     if member(pref,SUFFI) then
      gu:=expand(gu+(s-1)*op(LEN-r,Lt[op(pref)])):
     fi:
 
  od:
 
 
  for j from 2 to nops(mila) do
   suffi:=[op(j..nops(mila),mila)]:
   x[op(suffi)]:=x[op(suffi)]+gu:
  od:
 
 
tot:=tot+gu:
 
od:
 
 
#We now update LIS, and the Lt[]'s
 
LIS:=[op(LIS),tot]:
 
for i1 from 1 to nops(SUFFI) do
mila:=op(i1,SUFFI):
resh:=Lt[op(mila)]:
Lt[op(mila)]:=[op(2..nops(resh),resh),x[op(mila)]]:
od:
 
od:
 
LIS:
 
end:
 
 
#Lclust is exactly like Lclusts, but with s=0. See there for comments
 
Lclust:=proc(MISTAKES,NUTERMS)
local LEN,SUFFI,i,j,x,Lt,LIS,mila,EFES,I1,r,pref,tot,gu,resh,i1,suffi:
 
 
LIS:=[]:
 
SUFFI:={[]}:
 
for i from 1 to nops(MISTAKES) do
 mila:=op(i,MISTAKES):
 
 for j from 2 to nops(mila) do
  SUFFI:=SUFFI union {[op(j..nops(mila),mila)]}:
 od:
od:
 
LEN:=0:
 
for i from 1 to nops(MISTAKES) do
  mila:=op(i,MISTAKES):
  if nops(mila)>LEN then
    LEN:=nops(mila):
  fi:
od:
 
EFES:=[seq(0,j=1..LEN-1)]:
 
 
for i from 1 to nops(SUFFI) do
mila:=op(i,SUFFI):
Lt[op(mila)]:=EFES:
od:
 
 
for I1 from 0 to NUTERMS do
 
tot:=0:
 
for i from 1 to nops(SUFFI) do
mila:=op(i,SUFFI):
x[op(mila)]:=0:
od:
 
for i from 1 to nops(MISTAKES) do
 
 
  mila:=op(i,MISTAKES):
 
  gu:=0:
 
  if nops(mila)=I1 then
   gu:=-1:
  fi:
 
 
  for r from 1 to nops(mila)-1 do
    pref:=[op(1..nops(mila)-r,mila)]:
 
     if member(pref,SUFFI) then
      gu:=expand(gu-op(LEN-r,Lt[op(pref)])):
     fi:
 
  od:
 
 
  for j from 2 to nops(mila) do
   suffi:=[op(j..nops(mila),mila)]:
   x[op(suffi)]:=x[op(suffi)]+gu:
  od:
 
 
tot:=tot+gu:
 
od:
 
 
 
LIS:=[op(LIS),tot]:
 
for i1 from 1 to nops(SUFFI) do
mila:=op(i1,SUFFI):
resh:=Lt[op(mila)]:
Lt[op(mila)]:=[op(2..nops(resh),resh),x[op(mila)]]:
od:
 
od:
 
LIS:
 
end:
 
 
GJs:=proc(NUMLETTERS,MISTAKES,s,L)
local lu,resh,i,gu,t,resh1:
 
 
if bdok(MISTAKES)=0 then
 ERROR(` At least one mistake is a (proper) factor of another mistake`):
fi:
 
resh:=Lclusts(MISTAKES,L+2,s):
 
lu:=0:
 
for i from 0 to L+1 do
lu:=lu+op(i+1,resh)*t^i:
od:
 
 
gu:=1/(1-NUMLETTERS*t-lu):
 
gu:=taylor(gu,t=0,L+1):
 
resh1:=[]:
 
for i from 0 to L do
resh1:=[op(resh1),expand(coeff(gu,t,i))]:
od:
 
resh1:
end:
 
 
GJ:=proc(NUMLETTERS,MISTAKES,L)
local lu,resh,i,gu,t,resh1:
 
if bdok(MISTAKES)=0 then
 ERROR(` At least one mistake is a (proper) factor of another mistake`):
fi:
 
resh:=Lclust(MISTAKES,L+2):
 
lu:=0:
 
for i from 0 to L+1 do
lu:=lu+op(i+1,resh)*t^i:
od:
 
 
gu:=1/(1-NUMLETTERS*t-lu):
 
gu:=taylor(gu,t=0,L+1):
 
resh1:=[]:
 
for i from 0 to L do
resh1:=[op(resh1),expand(coeff(gu,t,i))]:
od:
 
resh1:
end: