print(` Version of April 2, 1997.`): print(`This is JODO, A Maple package,`): print(`written by J. Noonan, noonan@math.temple.edu .`): print(` and D. Zeilberger, zeilberg@math.temple.edu .`): print(`It implements JOhn noonan and DOron zeilberger's extension of `): print(` the Goulden-Jackson Cluster method.`): 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(``): lprint(``): print(`In this extension, one counts words according to their number`): print(`of mistakes, but NOW minimality is not assumed, so both`): print(`DONKEY and DONKEYHOLE can occur, and the weight of ADONKEYHOLES`): print(`is t^2, one because of DONKEY and one because of DONKEYHOLE.`): lprint(``): print(`For general help, and a list of the available functions,`): print(` type "ezra();". For specific help type "ezra(procedure_name)" `): lprint(``): lprint(`Warning: t,s,C,x are global variables, do not use them!`): ezra:=proc() if args=NULL then print(`JODO`): print(`A Maple package that implementsthe Noonan-Zeilberger extension of`): print(` the Goulden-Jacskon Cluster method`): print(` for finding generating functions and series exapansions`): print(`for the number of words avoiding a prescribed, finite, set of`): print(`"mistakes", that may not be minimal. Contains Procedures `): print(`GJNZ,GJNZxt, GJNZst, Runs, AvRuns `): print(` For specific help type "ezra(procedure_name)" `): fi: if nops([args])=1 and op(1,[args])=`AvRuns` then print(`AvRuns(alphabet,MISTAKES): Given a set of letters, alphabet, and `): print(`a set of words MISTAKES, finds the constant C`): print(`such that the average number of runs in an n-letter word`): print(`in the alphabet containing no factors from MISTAKES,is`): print(`asymptotically C*n`): fi: if nops([args])=1 and op(1,[args])=`Runs` then print(`Runs(alphabet,MISTAKES): Given a set of letters, alphabet, and `): print(`a set of words MISTAKES, finds the generating function`): print(`\sum_{n=0,m=0}^{\infty} a(n,m) s^n t^m , where the a(n,m) is`): print(`the number of words, in the alphabet that do not have any of`): print(`the words of MISTAKES as factors, and that have exactly m runs`): fi: if nops([args])=1 and op(1,[args])=`GJNZ` then print(`GJNZ(alphabet,MISTAKES):Given a set of letters alphabet, and a set`): print(`of words labelled MISTAKES (with no restriction of minimality`): print(`finds the generating function, i.e. weight enumerator, of all`): print(`words in the alphabet according to the weight`): print(`Product x[letter] Product [mistake], where the first product extends`): print(`over all the letters of the word and the second product extends over`): print(`all factors of the word that belongs to MISTAKES`): print(`For example GJNZ({1,2},{[1,2,1],[2,1,2],[2,1],[1,2]}), after it is`): print(`taylored, should be 1+x[1]+x[2]+x[1]*x[2]*(t[1,2]+t[2,1]) +...`): fi: if nops([args])=1 and op(1,[args])=`GJNZxt` then print(`GJNZxt(alphabet,MISTAKES):Given a set of letters alphabet, and a set`): print(`of words labelled MISTAKES (with no restriction of minimality),`): print(`finds the generating function, i.e. weight enumerator, of all`): print(`words in the alphabet according to the weight, weight(word)`): print(`Product x[letter] *t^(#mistakes) where the product extends`): print(`over all the letters and #mistkes is the number of`): print(` factors of the word that belongs to MISTAKES`): print(`For example GJNZxt({1,2},{[1,2,1],[2,1,2],[2,1],[1,2]}), after it is`): print(`taylored, should be 1+x[1]+x[2]+2*t*x[1]*x[2] +...`): fi: if nops([args])=1 and op(1,[args])=`GJNZst` then print(`GJNZst(alphabet,MISTAKES):Given a set of letters,alphabet,and a set`): print(`of words labelled MISTAKES (with no restriction of minimality),`): print(`finds the generating function, i.e. weight enumerator, of all`): print(`words in the alphabet according to the weight, weight(word)`): print(`Product s^(#letters) *t^(#mistakes) where the product extends`): print(`over all the letters and #mistkes is the number of`): print(` factors of the word that belongs to MISTAKES`): print(`For example GJNZst({1,2},{[1,2,1],[2,1,2],[2,1],[1,2]}), after it is`): print(`taylored, should be 1+2*s+(2+2*t)*s^2 +...`): fi: end: #Equi(u,v,i): Given a genuine mistake v, and another mistake under it #such that the 1'st letter of u coincides with the i-th letter of v #finds the term that corresponds to this situation in the Equation #for C[v] Equi:=proc(u,v,i): if i<1 or i>nops(v) then ERROR(`1<=i<=nops(v)`): fi: if nops(v)=i then if nops(u)<=nops(v) then RETURN(0): fi: if [op(nops(u)-i+1..nops(u),u)]<>v then RETURN(0): else RETURN((t[op(v)]-1)*C[op(u)]): fi: fi: if nops(u)u then RETURN(0): else RETURN((t[op(v)]-1)*weight([op(i+1..nops(v),v)])*C[[op(1..i-nops(u),v)],u]): fi: fi: if nops(u)>=i then if [op(1..i,v)]<>[op(nops(u)-i+1..nops(u),u)] then RETURN(0): else RETURN((t[op(v)]-1)*weight([op(i+1..nops(v),v)])*C[op(u)]): fi: fi: end: #Equi1(u,v,i): Given a generalized mistake v=[v1,v2], #and another genuine mistake u under it #such that the last letter of u coincides with the i-th letter of v #finds the term that corresponds to this situation in the Equation #for C[v] Equi1:=proc(u,v,i) local v1,v2,vt: v1:=op(1,v): v2:=op(2,v): vt:=[op(v1),op(v2)]: if i<1 or i>nops(vt) then ERROR(`1<=i<=nops(v1)+nops(v2)`): fi: if nops(vt)=i then if nops(u)<=nops(v2) then RETURN(0): fi: if nops(u)>nops(v2) and nops(u)u then RETURN(0): else RETURN((t[op(v2)]-1)*C[[op(1..nops(vt)-nops(u),vt)],[op(u)]]): fi: fi: if nops(u)>=nops(vt) then if [op(nops(u)-i+1..nops(u),u)]<>vt then RETURN(0): else RETURN((t[op(v2)]-1)*C[op(u)]): fi: fi: fi: if nops(u)u then RETURN(0): else RETURN((t[op(v2)]-1)*weight([op(i+1..nops(vt),vt)])* C[[op(1..i-nops(u),vt)],u]): fi: fi: if nops(u)>=i then if [op(1..i,vt)]<>[op(nops(u)-i+1..nops(u),u)] then RETURN(0): else RETURN((t[op(v2)]-1)*weight([op(i+1..nops(vt),vt)])*C[op(u)]): fi: fi: end: #Equ(v): gives the equation corresponding to the genuine mistake #v being at the top Equ:=proc(v,MISTAKES) local u,i,j,gu: gu:=C[op(v)]-weight(v)*(t[op(v)]-1): for j from 1 to nops(MISTAKES) do u:=op(j,MISTAKES): for i from 1 to nops(v) do gu:=gu-Equi(u,v,i): od: od: gu: end: #Equ1(v): gives the equation corresponding to the generalized mistake #v being at the top Equ1:=proc(v,MISTAKES) local v1,v2,vt,u,i,j,gu: v1:=op(1,v): v2:=op(2,v): vt:=[op(v1),op(v2)]: gu:=C[op(v)]-weight(vt)*(t[op(v2)]-1): for j from 1 to nops(MISTAKES) do u:=op(j,MISTAKES): for i from 1 to nops(vt) do gu:=gu-Equi1(u,v,i): od: od: gu: end: #issub(u,v) decides whether u is a proper subword of v which #is not a suffix. In the affirmative case, it returns the list of places where #it starts issub:=proc(u,v) local i,gu: gu:=[]: for i from 2 to nops(v)-nops(u) do if [op(i..i+nops(u)-1,v)]=u then gu:=[op(gu),i]: fi: od: gu: end: #genmis(u,v) forms the list of `generalized mistakes' from u and v whenever #u is a proper, non-suffix,non=prefix, subword of v genmis:=proc(u,v) local mu,gu,i: gu:=issub(u,v): if gu=[] then ERROR(u,`is not a proper non-suffix, non-prefix, subword of`,v): fi: mu:={}: for i from 1 to nops(gu) do mu:=mu union {[[op(1..op(i,gu)-1,v)],u]}: od: mu: end: genvar:=proc(MISTAKES) local i,j,u,v,kv: kv:={}: for i from 1 to nops(MISTAKES) do v:=op(i,MISTAKES): for j from 1 to nops(MISTAKES) do u:=op(j,MISTAKES): if issub(u,v)<>[] then kv:=kv union genmis(u,v): fi: od: od: kv: end: #weight(u) gives the weight of a word u weight:=proc(u) local gu,i: gu:=1: for i from 1 to nops(u) do gu:=gu*x[op(i,u)]: od: gu: end: GJNZ:=proc(alphabet,MISTAKES1) local gu,i,v,eq,var,GENMIS,MISTAKES: MISTAKES:=convert(convert(MISTAKES1,set),list): GENMIS:=genvar(MISTAKES): var:={}: for i from 1 to nops(MISTAKES) do v:=op(i,MISTAKES): var:=var union {C[op(v)]}: od: for i from 1 to nops(GENMIS) do v:=op(i,GENMIS): var:=var union {C[op(v)]}: od: eq:={}: for i from 1 to nops(MISTAKES) do v:=op(i,MISTAKES): eq:=eq union {Equ(v,MISTAKES)}: od: for i from 1 to nops(GENMIS) do v:=op(i,GENMIS): eq:=eq union {Equ1(v,MISTAKES)}: od: var:=solve(eq,var): gu:=1: for i from 1 to nops(alphabet) do gu:=gu-x[op(i,alphabet)]: od: for i from 1 to nops(MISTAKES) do v:=op(i,MISTAKES): gu:=gu-subs(var,C[op(v)]): od: normal(1/gu): end: #mishkal finds the weight of a word w according to the set MISTAKES mishkal:=proc(w,MISTAKES) local gu,i,j: gu:=weight(w): for i from 1 to nops(w) do for j from i to nops(w) do if member([op(i..j,w)],MISTAKES) then gu:=gu*t[op(i..j,w)]: fi: od: od: gu: end: #MILIM(n) finds all the words of length n in the alphabet MILIM:=proc(alphabet,n) local lu,gu,i,j,v: option remember: if n=0 then RETURN({[]}): fi: gu:={}: lu:=MILIM(alphabet,n-1): for i from 1 to nops(lu) do v:=op(i,lu): for j from 1 to nops(alphabet) do gu:=gu union {[op(v),op(j,alphabet)]}: od: od: gu: end: #MISHKAL(MISTAKES,n) finds the sum of the weights of all words #of length n in the alphabet alphabet according to MISTAKES MISHKAL:=proc(alphabet,MISTAKES,n) local i,gu,lu: lu:=MILIM(alphabet,n): gu:=0: for i from 1 to nops(lu) do gu:=gu+mishkal(op(i,lu),MISTAKES): od: gu: end: #bdok(alphabet,MISTAKES,L) checks empirically, up to the Lth term #the validity of GJNZ(alphabet,MISTAKES) bdok:=proc(alphabet,MISTAKES,L) local i,gu,s,mu: gu:=GJNZ(alphabet,MISTAKES): for i from 1 to nops(alphabet) do gu:=subs(x[op(i,alphabet)]=s*x[op(i,alphabet)],gu): od: gu:=taylor(gu,s=0,L+1): mu:=[]: for i from 0 to L do mu:=[op(mu),expand(coeff(gu,s,i)-MISHKAL(alphabet,MISTAKES,i))]: od: mu: end: GJNZxtslow:=proc(alphabet,MISTAKES1) local i,gu: gu:=GJNZ(alphabet,MISTAKES1): for i from 1 to nops(MISTAKES1) do gu:=subs(t[op(op(i,MISTAKES1))]=t,gu): od: normal(gu): end: GJNZstslow:=proc(alphabet,MISTAKES1) local i,gu: gu:=GJNZ(alphabet,MISTAKES1): for i from 1 to nops(MISTAKES1) do gu:=subs(t[op(op(i,MISTAKES1))]=t,gu): od: for i from 1 to nops(alphabet) do gu:=subs(x[op(i,alphabet)]=s,gu): od: normal(gu): end: #Equixt(u,v,i): Given a genuine mistake v, and another mistake under it #such that the 1'st letter of u coincides with the i-th letter of v #finds the term that corresponds to this situation in the Equation #for C[v] in GJNZxt i.e. where all mistakes get the same weight Equixt:=proc(u,v,i): if i<1 or i>nops(v) then ERROR(`1<=i<=nops(v)`): fi: if nops(v)=i then if nops(u)<=nops(v) then RETURN(0): fi: if [op(nops(u)-i+1..nops(u),u)]<>v then RETURN(0): else RETURN((t-1)*C[op(u)]): fi: fi: if nops(u)u then RETURN(0): else RETURN((t-1)*weight([op(i+1..nops(v),v)])*C[[op(1..i-nops(u),v)],u]): fi: fi: if nops(u)>=i then if [op(1..i,v)]<>[op(nops(u)-i+1..nops(u),u)] then RETURN(0): else RETURN((t-1)*weight([op(i+1..nops(v),v)])*C[op(u)]): fi: fi: end: #Equi1xt(u,v,i): Given a generalized mistake v=[v1,v2], #and another genuine mistake u under it #such that the last letter of u coincides with the i-th letter of v #finds the term that corresponds to this situation in the Equation #for C[v] for GJNZxt, i.e. where every mistake carries weight t Equi1xt:=proc(u,v,i) local v1,v2,vt: v1:=op(1,v): v2:=op(2,v): vt:=[op(v1),op(v2)]: if i<1 or i>nops(vt) then ERROR(`1<=i<=nops(v1)+nops(v2)`): fi: if nops(vt)=i then if nops(u)<=nops(v2) then RETURN(0): fi: if nops(u)>nops(v2) and nops(u)u then RETURN(0): else RETURN((t-1)*C[[op(1..nops(vt)-nops(u),vt)],[op(u)]]): fi: fi: if nops(u)>=nops(vt) then if [op(nops(u)-i+1..nops(u),u)]<>vt then RETURN(0): else RETURN((t-1)*C[op(u)]): fi: fi: fi: if nops(u)u then RETURN(0): else RETURN((t-1)*weight([op(i+1..nops(vt),vt)])* C[[op(1..i-nops(u),vt)],u]): fi: fi: if nops(u)>=i then if [op(1..i,vt)]<>[op(nops(u)-i+1..nops(u),u)] then RETURN(0): else RETURN((t-1)*weight([op(i+1..nops(vt),vt)])*C[op(u)]): fi: fi: end: #Equxt(v): gives the equation corresponding to the genuine mistake #v being at the top, to help GJNZxt i.e. where all the mistakes have #the same weight Equxt:=proc(v,MISTAKES) local u,i,j,gu: gu:=C[op(v)]-weight(v)*(t-1): for j from 1 to nops(MISTAKES) do u:=op(j,MISTAKES): for i from 1 to nops(v) do gu:=gu-Equixt(u,v,i): od: od: gu: end: #Equ1xt(v): gives the equation corresponding to the generalized mistake #v being at the top, for GJNZxt, i.e. where all mistakes carry the #same weight t Equ1xt:=proc(v,MISTAKES) local v1,v2,vt,u,i,j,gu: v1:=op(1,v): v2:=op(2,v): vt:=[op(v1),op(v2)]: gu:=C[op(v)]-weight(vt)*(t-1): for j from 1 to nops(MISTAKES) do u:=op(j,MISTAKES): for i from 1 to nops(vt) do gu:=gu-Equi1xt(u,v,i): od: od: gu: end: GJNZxt:=proc(alphabet,MISTAKES1) local gu,i,v,eq,var,GENMIS,MISTAKES: MISTAKES:=convert(convert(MISTAKES1,set),list): GENMIS:=genvar(MISTAKES): var:={}: for i from 1 to nops(MISTAKES) do v:=op(i,MISTAKES): var:=var union {C[op(v)]}: od: for i from 1 to nops(GENMIS) do v:=op(i,GENMIS): var:=var union {C[op(v)]}: od: eq:={}: for i from 1 to nops(MISTAKES) do v:=op(i,MISTAKES): eq:=eq union {Equxt(v,MISTAKES)}: od: for i from 1 to nops(GENMIS) do v:=op(i,GENMIS): eq:=eq union {Equ1xt(v,MISTAKES)}: od: var:=solve(eq,var): gu:=1: for i from 1 to nops(alphabet) do gu:=gu-x[op(i,alphabet)]: od: for i from 1 to nops(MISTAKES) do v:=op(i,MISTAKES): gu:=gu-subs(var,C[op(v)]): od: normal(1/gu): end: #mishkalxt finds the weight of a word w according to the set MISTAKES mishkalxt:=proc(w,MISTAKES) local gu,i,j: gu:=weight(w): for i from 1 to nops(w) do for j from i to nops(w) do if member([op(i..j,w)],MISTAKES) then gu:=gu*t: fi: od: od: gu: end: #MISHKALxt(MISTAKES,n) finds the sum of the weights of all words #of length n in the alphabet alphabet according to MISTAKES, for GJNZxt #i.e. where all mistakes get weight t MISHKALxt:=proc(alphabet,MISTAKES,n) local i,gu,lu: lu:=MILIM(alphabet,n): gu:=0: for i from 1 to nops(lu) do gu:=gu+mishkalxt(op(i,lu),MISTAKES): od: gu: end: #bdokxt(alphabet,MISTAKES,L) checks empirically, up to the Lth term #the validity of GJNZxt(alphabet,MISTAKES) bdokxt:=proc(alphabet,MISTAKES,L) local i,gu,s,mu: gu:=GJNZxt(alphabet,MISTAKES): for i from 1 to nops(alphabet) do gu:=subs(x[op(i,alphabet)]=s*x[op(i,alphabet)],gu): od: gu:=taylor(gu,s=0,L+1): mu:=[]: for i from 0 to L do mu:=[op(mu),expand(coeff(gu,s,i)-MISHKALxt(alphabet,MISTAKES,i))]: od: mu: end: #Equist(u,v,i): Given a genuine mistake v, and another mistake under it #such that the 1'st letter of u coincides with the i-th letter of v #finds the term that corresponds to this situation in the Equation #for C[v] in GJNZst i.e. where all mistakes get the same weight #and all letters recieve the weight s Equist:=proc(u,v,i): if i<1 or i>nops(v) then ERROR(`1<=i<=nops(v)`): fi: if nops(v)=i then if nops(u)<=nops(v) then RETURN(0): fi: if [op(nops(u)-i+1..nops(u),u)]<>v then RETURN(0): else RETURN((t-1)*C[op(u)]): fi: fi: if nops(u)u then RETURN(0): else RETURN((t-1)*weightst([op(i+1..nops(v),v)])*C[[op(1..i-nops(u),v)],u]): fi: fi: if nops(u)>=i then if [op(1..i,v)]<>[op(nops(u)-i+1..nops(u),u)] then RETURN(0): else RETURN((t-1)*weightst([op(i+1..nops(v),v)])*C[op(u)]): fi: fi: end: #Equi1st(u,v,i): Given a generalized mistake v=[v1,v2], #and another genuine mistake u under it #such that the last letter of u coincides with the i-th letter of v #finds the term that corresponds to this situation in the Equation #for C[v] for GJNZst, i.e. where every mistake carries weight t #and every letter gets the weight s Equi1st:=proc(u,v,i) local v1,v2,vt: v1:=op(1,v): v2:=op(2,v): vt:=[op(v1),op(v2)]: if i<1 or i>nops(vt) then ERROR(`1<=i<=nops(v1)+nops(v2)`): fi: if nops(vt)=i then if nops(u)<=nops(v2) then RETURN(0): fi: if nops(u)>nops(v2) and nops(u)u then RETURN(0): else RETURN((t-1)*C[[op(1..nops(vt)-nops(u),vt)],[op(u)]]): fi: fi: if nops(u)>=nops(vt) then if [op(nops(u)-i+1..nops(u),u)]<>vt then RETURN(0): else RETURN((t-1)*C[op(u)]): fi: fi: fi: if nops(u)u then RETURN(0): else RETURN((t-1)*weightst([op(i+1..nops(vt),vt)])* C[[op(1..i-nops(u),vt)],u]): fi: fi: if nops(u)>=i then if [op(1..i,vt)]<>[op(nops(u)-i+1..nops(u),u)] then RETURN(0): else RETURN((t-1)*weightst([op(i+1..nops(vt),vt)])*C[op(u)]): fi: fi: end: #Equst(v): gives the equation corresponding to the genuine mistake #v being at the top, to help GJNZst i.e. where all the mistakes have #the same weight t, and every letter gets the weight s Equst:=proc(v,MISTAKES) local u,i,j,gu: gu:=C[op(v)]-weightst(v)*(t-1): for j from 1 to nops(MISTAKES) do u:=op(j,MISTAKES): for i from 1 to nops(v) do gu:=gu-Equist(u,v,i): od: od: gu: end: #Equ1st(v): gives the equation corresponding to the generalized mistake #v being at the top, for GJNZst, i.e. where all mistakes carry the #same weight t, and every letter carries the same weight s Equ1st:=proc(v,MISTAKES) local v1,v2,vt,u,i,j,gu: v1:=op(1,v): v2:=op(2,v): vt:=[op(v1),op(v2)]: gu:=C[op(v)]-weightst(vt)*(t-1): for j from 1 to nops(MISTAKES) do u:=op(j,MISTAKES): for i from 1 to nops(vt) do gu:=gu-Equi1st(u,v,i): od: od: gu: end: #weightst(u) gives the weight of a word u where every letter has #weight s weightst:=proc(u) local gu,i: gu:=1: for i from 1 to nops(u) do gu:=gu*s: od: gu: end: GJNZst:=proc(alphabet,MISTAKES1) local gu,i,v,eq,var,GENMIS,MISTAKES: MISTAKES:=convert(convert(MISTAKES1,set),list): GENMIS:=genvar(MISTAKES): var:={}: for i from 1 to nops(MISTAKES) do v:=op(i,MISTAKES): var:=var union {C[op(v)]}: od: for i from 1 to nops(GENMIS) do v:=op(i,GENMIS): var:=var union {C[op(v)]}: od: eq:={}: for i from 1 to nops(MISTAKES) do v:=op(i,MISTAKES): eq:=eq union {Equst(v,MISTAKES)}: od: for i from 1 to nops(GENMIS) do v:=op(i,GENMIS): eq:=eq union {Equ1st(v,MISTAKES)}: od: var:=solve(eq,var): gu:=1: for i from 1 to nops(alphabet) do gu:=gu-s: od: for i from 1 to nops(MISTAKES) do v:=op(i,MISTAKES): gu:=gu-subs(var,C[op(v)]): od: normal(1/gu): end: #mishkalst finds the weight of a word w according to the set MISTAKES mishkalst:=proc(w,MISTAKES) local gu,i,j: gu:=weightst(w): for i from 1 to nops(w) do for j from i to nops(w) do if member([op(i..j,w)],MISTAKES) then gu:=gu*t: fi: od: od: gu: end: #MISHKALst(MISTAKES,n) finds the sum of the weights of all words #of length n in the alphabet alphabet according to MISTAKES, for GJNZst #i.e. where all mistakes get weight t, and all letters receive weight s MISHKALst:=proc(alphabet,MISTAKES,n) local i,gu,lu: lu:=MILIM(alphabet,n): gu:=0: for i from 1 to nops(lu) do gu:=gu+mishkalst(op(i,lu),MISTAKES): od: gu: end: #bdokst(alphabet,MISTAKES,L) checks empirically, up to the Lth term #the validity of GJNZst(alphabet,MISTAKES) bdokst:=proc(alphabet,MISTAKES,L) local i,gu,mu: gu:=GJNZst(alphabet,MISTAKES): gu:=taylor(gu,s=0,L+1): mu:=[]: for i from 0 to L do mu:=[op(mu),expand(s^i*coeff(gu,s,i)-MISHKALst(alphabet,MISTAKES,i))]: od: mu: end: #Runs(alphabet,MISTAKES): Given a set of letters, alphabet, and #a set of words MISTAKES, finds the generating function #\sum_{n=0,m=0}^{\infty} a(n,m) s^n t^m , where the a(n,m) is #the number of words, in the alphabet that do not have any of #the words of MISTAKES as factors, and that have exactly m runs Runs:=proc(alphabet,MISTAKES1) local MISTAKES,gu,i,j,PAIRS: PAIRS:={}: for i from 1 to nops(alphabet) do for j from 1 to nops(alphabet) do if i<>j then PAIRS:=PAIRS union {[op(i,alphabet),op(j,alphabet)]}: fi: od: od: MISTAKES:=MISTAKES1 union PAIRS: gu:=GJNZ(alphabet,MISTAKES): for i from 1 to nops(MISTAKES1) do gu:=subs(t[op(op(i,MISTAKES1))]=0,gu): od: for i from 1 to nops(PAIRS) do gu:=subs(t[op(op(i,PAIRS))]=t,gu): od: for i from 1 to nops(alphabet) do gu:=subs(x[op(i,alphabet)]=s,gu): od: gu: end: AvRuns:=proc(alphabet,MISTAKES1) local gu,gu1,mu,P1,P2,Q1,i,katan: gu:=Runs(alphabet,MISTAKES1): gu1:=diff(gu,t): gu:=subs(t=1,gu): gu1:=subs(t=1,gu1): P1:=numer(gu): P2:=numer(gu1): Q1:=denom(gu): mu:=[fsolve(Q1,s)]: if nops(mu)=0 then ERROR(`Denominator has no real roots`): fi: katan:=op(1,mu): for i from 2 to nops(mu) do if abs(op(i,mu))