######################################################################
##ENDREplus: Save this file as  ENDREplus                            #
##To use it, stay in the                                             #
##same directory, get into Maple (by typing: maple <Enter> )         #
##and then type:  read ENDREplus<Enter>                              #
##Then follow the instructions given there                           #
##                                                                   #
##Written by Doron Zeilberger, Rutgers University ,                  #
#zeilberg at math dot rutgers dot edu                                #
######################################################################

#This is an extension of ENDRE, created Aug. 2024 following a question by Giorgio Parisi
#Original version:Created: April 8, 2009
 
print(`Original package ENDRE Created: April 8, 2009`):
print(` This is EDNREplus `):
print(`This is an extension of the Maple packgae ENDRE Created: April 8, 2009`):
print(`Following some questions of Giorgio Parisi`):
print(`The original package that accompanied the article `):
print(` "Finite Analogs of Szemeredi's Theorem" `):
print(`by Paul Raff and Doron Zeilberger`):

print(`and also available from Zeilberger's website`):
print(``):
print(`Please report bugs to zeilberg at math dot rutgers dot edu`):
print(``):
 print(`The most current version of this  package and paper`):
 print(` are  available from`):
 print(`http://www.math.rutgers.edu/~zeilberg/  .`):
print(`*************************************`):
 print(`For a list of the MAIN procedures type ezra();, for help with`):
 print(`any specific procedure, type ezra(procedure_name);   .`):
 print(``):
print(`*************************************`):

 print(`For a list of the supporting procedures type ezra1();, for help with`):
print(`a speficic procedure, type, ezra(ProcedureName);`):


 print(`For a list of the Checking procedures type ezraC();, for help with`):
print(`a speficic procedure, type, ezra(ProcedureName);`):

 print(`For a list of the  procedures to do with creating schemes`):
print(`a speficic procedure, type, ezra(ProcedureName);`):


 print(`For a list of the Verbose procedures type ezraV();, for help with`):
print(`a speficic procedure, type, ezra(ProcedureName);`):

print(`*************************************`):
 print(`For a list of the MAIN procedures type ezra();, for help with`):
 print(`any specific procedure, type ezra(procedure_name);   .`):
 print(`For example, for help with procedure SeqC, type`):
 print(` ezra(SeqC); `):
 print(``):


 print(`For a list of the new procedures to answer a question of Giorgio Parisis type ezraP(); `):
print(`a speficic procedure, type, ezra(ProcedureName);`):

print(`*************************************`):



with(combinat):



ezraP:=proc()

if args=NULL then
 print(` The new procedures are: IsParisi, Pats, MGW, MaxiWords, ParisiWords, SeqCx, SeqCxx `):

else
ezra(args):
fi:

end:

ezraV:=proc()

if args=NULL then
 print(` The verbose procedures are: MakeSchemeV, SeqN1eV, SeqN1eAllV`):

else
ezra(args):
fi:

end:

ezraC:=proc()

if args=NULL then
 print(` The checking procedures are: GW, `):
 print(` IsBad, IsBad1, Max1, MaxN1, MaxN1A, SeqCd `):
 print(`  SeqCgf, SeqN1d, SeqN1d, SeqN1gf , SzeSeqCd, ,  SzeSeqD, vdwSeqCd `):



else
ezra(args):
fi:

end:

ezra1:=proc()

if args=NULL then
 print(` The supporting procedures are: B, Brep, Contest `):
 print(` GuessPeriod, GuessSeq, GWnk `):
 print(`ImpliedPs , Inflate, IsImpliedBy, IsSuperfluous, NotYetDone,`):
 print(` PutSpaces1, PutSpaces1Ad, PutSpacesAd, Tsamek1, Tsamek  `):

else
ezra(args):
fi:

end:

ezraScheme:=proc():

if args=NULL then
 print(` The procedures to do with creating a scheme are`):
print(` Bat, Ben , GFs, MakeScheme, ManySteps, OneStep,`):
 print(`ImpliedPs , Inflate, IsImpliedBy, IsSuperfluous, NotYetDone,`):
 print(` Tsamek1, Tsamek  `):

else
ezra(args):
fi:
end:

ezra:=proc()

if args=NULL then
 print(`The main procedures are: Akd, ContestAd, GFp, MakeScheme `):
 print(` SeqC, SeqN1, SeqN1e `):
 print(`SeqN1eAll, SeqN1eAllAndProve, `):
 print(` SipurSeqC, SipurSeqCgf, SipurSze,`):
 print(` SzeSeq, SzeSeqC  `):
print(` `):



elif nops([args])=1 and op(1,[args])=Akd then
print(`Akd(k,d,K): the asymptotic maximum relative size of a subset of [1,n]`):
print(`avoiding arith. prog. of length k with differences <=d`):
print(`with K terms to guess`):
print(`For example, try`):
print(`Akd(3,2,200);`):

elif nops([args])=1 and op(1,[args])=B then
print(`B(n): all the binary vectors of size n`):


elif nops([args])=1 and op(1,[args])=Bat then
print(`Bat(P,SP): inputs a set of global patterns and starting patterns`):
print(`which are lists in {0,1,2} (2 means a blank) and outputs`):
print(`all the starting patterns (in addition to the global patterns)`):
print(`that the chopped word, obtained by chopping the first letter,`):
print(` avoids, if it starts with 0.`):
print(`For example, try: `):
print(`Bat({[1,1,1]},{});`):

elif nops([args])=1 and op(1,[args])=Ben then
print(`Ben(P,SP): inputs a set of global patterns and starting patterns`):
print(`which are lists in {0,1,2} (2 means a blank) and outputs`):
print(`all the starting patterns (in addition to the global patterns)`):
print(`that the chopped word, obtained by chopping the first letter,`):
print(` avoids, if it starts with 1.`):
print(`For example, try: `):
print(`Ben({[1,1,1]},{});`):


elif nops([args])=1 and op(1,[args])=Brep then
print(`Brep(k): a set of representatives of`):
print(`k-lettered words in {0,1}`):
print(`For example, try:`):
print(`Brep(3);`):


elif nops([args])=1 and op(1,[args])=Contest then
print(`Contest(k,d,K,K1,t): the contest between all single patterns`):
print(`  of length k `):
print(` and spacing <=d, using K terms, displaying K1 terms and `):
print(` also giving the generating functions. `):
print(` For example, try: `):
print(` Contest(3,2,300,30,t); `):

elif nops([args])=1 and op(1,[args])=ContestAd then
print(`ContestAd(k,d,K,K1,t): the contest between all single patterns`):
print(`  of length k `):
print(` and spacing <=d1, for d1=0..d`):
print(` using K terms, displaying K1 terms and `):
print(` also giving the generating functions. `):
print(` For example, try: `):
print(` ContestAd(3,2,300,30,t); `):

elif nops([args])=1 and op(1,[args])=GFp then
print(`GFp(P,x,t): the weight-enumerator in x,t `):
print(`(wt. is x^(#1's)*t^(length))`):
print(`of the set of words in {0,1} avoiding the set`):
print(`of generalized patterns P, where 2 is a blank`):
print(`For example, try: `):
print(` GFp( {[1,1,1],[1,2,1,2,1]},x,t) ; `) :

elif nops([args])=1 and op(1,[args])=GFs then
print(`GFs(S,x,t): the generating function in x,t `):
print(`(wt. is x^(#1's)*t^(length))`):
print(`corresponding to the scheme S`):
print(`For example, try: `):
print(` GFs(MakeScheme({[1,1,1]}),x,t) ; `) :

elif nops([args])=1 and op(1,[args])=GuessPeriod then
print(`GuessPeriod(Lis): Given a list, guesses an ultimate period`):

elif nops([args])=1 and op(1,[args])=GuessSeq then
print(`GuessSeq(L): Given a sequence of increasing integers,`):
print(`tries to guess an expression of the form [N,M,L1]`):
print(`where L1 has N terms`):
print(`for example, try: `):
print(` GuessSeq([seq(i,i=1..100)]);`):

elif nops([args])=1 and op(1,[args])=GW then
print(`GW(n,P): the set of all words in {0,1} of length n, avoiding any of`):
print(`of the general patterns in the set P`):
print(`For example, try GW(3,{[1,1,1],[0,2,0]});`):

elif nops([args])=1 and op(1,[args])=GWnk then
print(`GWnk(n,k,P): the set of all words in {0,1} lf length n`):
print(`with k 1's avoiding any of`):
print(`of the general patterns in the set P.`):
print(`For example, try GWnk(3,2,{[1,1,1],[0,2,0]});`):

elif nops([args])=1 and op(1,[args])=ImpliedPs then
print(`ImpliedPs(p): all specific patterns implied by p`):
print(`For example, try:`):
print(`ImpliedPs([2,2]);`):


elif nops([args])=1 and op(1,[args])=Inflate then
print(`Inflate(M,N,resh,x): given a period f(Mk+i)=Nk+resh[i]`):
print(`blows it up by x, for example, try`):
print(`Inflate(3,2,[1,1,2],3);`):

elif nops([args])=1 and op(1,[args])=IsBad then
print(`IsBad(w,P): given a word w in {0,1}, and a set of patterns`):
print(`P returns true`):
print(`if w ends with some pattern p of P and false otherwise`):
print(`For example, try:`):
print(`IsBad([1,0,0,1],{[0,2,1]});`):

elif nops([args])=1 and op(1,[args])=IsBad1 then
print(`IsBad1(w,p): given a word w in {0,1}, and a pattern p, returns true`):
print(`if w ends with the pattern p and false otherwise`):
print(`For example, try:`):
print(`IsBad1([1,0,0,1],[0,2,1]);`):

elif nops([args])=1 and op(1,[args])=IsImpliedBy then
print(`IsImpliedBy(p,q) is not having pattern p implied by `):
print(`not having pattern q?`):
print(`For example, try:`):
print(`IsImpliedBy([1,1,1],[1,2,1]);`):


elif nops([args])=1 and op(1,[args])=IsParisi then
print(`IsParisi(w,P): Inputs a finite word w in {0,1} decideds whether w^infinity avoids the all the patterns in P. Try:`):
print(`IsParisi([1,1,0],{[1,1,1],[1,2,1,2,1]});`):
print(`IsParisi([1,1,0,0],{[1,1,1],[1,2,1,2,1],[1,2,2,1,2,2,1]});`):

elif nops([args])=1 and op(1,[args])=IsSuperfluous then
print(`IsSuperfluous(P,SP,p): is pattern p in SP superflous?`):


elif nops([args])=1 and op(1,[args])=MakeScheme then
print(`MakeScheme(P): given a set of patterns P finds a scheme.`):
print(`also returns, as second argument, the dictionary`):
print(`For example, try: `):
print(`MakeScheme({[1,1,1]});`):

elif nops([args])=1 and op(1,[args])=MakeSchemeV then
print(`MakeSchemeV(P,F,n): Verbose version of`):
print(`MakeScheme(P), phrased in terms of F and n`):
print(`For example, try: `):
print(`MakeSchemeV({[1,1,1]},F,n);`):

elif nops([args])=1 and op(1,[args])=ManySteps then
print(`ManySteps(S,n): n  iterations in the scheme S applied to the list L`):


elif nops([args])=1 and op(1,[args])=Max1 then
print(`Max1(n,P): the maximal number of 1's in an n-letter word in {0,1}`):
print(`avoiding P`):
print(`For example, try:`):
print(`Max1(5,{[1,1,1],[1,2,1,2,1]}); `):

elif nops([args])=1 and op(1,[args])=MaxN1 then
print(`MaxN1(S): given a set of words S in the alphabet S`):
print(`finds the maximum number of 1's amongsts all words`):
print(`For example, try:`):
print(`MaxN1({[1,0,1],[0,0,1]});`):

elif nops([args])=1 and op(1,[args])=MaxN1A then
print(`MaxN1A(S): given a set of words S in the alphabet S`):
print(`finds the maximum number of 1's amongsts all words`):
print(`followed by the champions`):
print(`For example, try:`):
print(`MaxN1A({[1,0,1],[0,0,1]});`):

elif nops([args])=1 and op(1,[args])=MGW then
print(`MGW(n,P): maximally good word: the set of good words in {0,1} avoiding P with a maximal number of 1s. Try:`):
print(`MGW(7,{[1,1,1]});`):

elif nops([args])=1 and op(1,[args])=NotYetDone then
print(`NotYetDone(S): given a partial scheme, finds all those`):
print(`not yet done`):

elif nops([args])=1 and op(1,[args])=OneStep then
print(`OneStep(S,L): one iteration in the scheme S applied to the list L`):


elif nops([args])=1 and op(1,[args])=MaxiWords then
print(`MaxiWords(P,K): all the Parisi words (words avoiding the generalized patten P that have maximal size for their length and that are unique, Try`):
print(`MaxiWords({[1,1,1],[1,2,1,2,1]},10);`):

elif nops([args])=1 and op(1,[args])=ParisiWords then
print(`ParisWords(n,k,P): Given a set of patterns P finds all Parisi words of length n with k 1's. Try:`):
print(`ParisiWords(9,4,Pats(3,3)):`):

elif nops([args])=1 and op(1,[args])=Pats then
print(`Pats(k,d): the set of patterns of AP up to spacing d. Try:`):
print(`Pats(3,4);`):

elif nops([args])=1 and op(1,[args])=PutSpaces1 then
print(`PutSpaces1(w,i): Given a word w in {0,1} puts i spaces (2)`):
print(`between each letter. For example, try:`):
print(`PutSpaces1([1,0,1],2);`):

elif nops([args])=1 and op(1,[args])=PutSpacesAd then
print(`PutSpacesAd(S,i): Given a set of words S in {0,1} puts i1 spaces (2)`):
print(` 1<=i1<=i `):
print(`between each letter, for each word. For example, try:`):
print(`PutSpacesAd({[1,1,1],[0,0,0]}, 2);`):

elif nops([args])=1 and op(1,[args])=PutSpaces1Ad then
print(`PutSpaces1Ad(w,i): Given a word w in {0,1} puts i1 spaces (2)`):
print(` 1<=i1<=i `):
print(`between each letter. For example, try:`):
print(`PutSpaces1Ad([1,0,1],2);`):

elif nops([args])=1 and op(1,[args])=SeqC then
print(`SeqC(P,K): the first K terms of the counting sequence for words`):
print(`avoiding the generalized patterns in P, using the clever`):
print(`approach. For example, try:`):
print(`SeqC({[1,1,1],[1,2,1,2,1]},10);`):


elif nops([args])=1 and op(1,[args])=SeqCx then
print(`SeqCx(P,K,x): the first K terms of the x-counting sequence for words`):
print(`avoiding the generalized patterns in P, using the clever`):
print(`approach. by x#1's, For example, try:`):
print(`SeqCx({[1,1,1],[1,2,1,2,1]},10,x);`):


elif nops([args])=1 and op(1,[args])=SeqCxx then
print(`SeqCxx(P,K,x): the first K terms of the x-counting sequence for words`):
print(`avoiding the generalized patterns in P, using the clever`):
print(`approach. by x#1's, and locations of the 1's. For example, try:`):
print(`SeqCxx({[1,1,1],[1,2,1,2,1]},10,x);`):

elif nops([args])=1 and op(1,[args])=SeqCd then
print(`SeqCd(P,K): the first K terms of the counting sequence for words`):
print(`avoiding the generalized patterns in P, using the brute-force`):
print(`direct approach. For example, try:`):
print(`SeqCd({[1,1,1],[1,2,1,2,1]},10);`):

elif nops([args])=1 and op(1,[args])=SeqCgf then
print(`SeqCgf(P,K): the first K terms of the counting sequence for words`):
print(`avoiding the generalized patterns in P, using generating functions`):
print(`For example, try:`):
print(`SeqCgf({[1,1,1],[1,2,1,2,1]},10);`):

elif nops([args])=1 and op(1,[args])=SeqN1 then
print(`SeqN1(P,K): the first K terms of the  sequence `):
print(`"maximum number of 1's for words in {0,1}`):
print(`avoiding the generalized patterns in P, using the clever way.`):
print(`For example, try:`):
print(`SeqN1({[1,1,1],[1,2,1,2,1]},10);`):

elif nops([args])=1 and op(1,[args])=SeqN1e then
print(`SeqN1e(P,K): the explicit expression for the sequence `):
print(`"maximum number of 1's for words in {0,1}`):
print(`avoiding the generalized patterns in P, using the clever way.`):
print(`For example, try:`):
print(`SeqN1e({[1,1,1],[1,2,1,2,1]},100);`):


elif nops([args])=1 and op(1,[args])=SeqN1eAll then
print(`SeqN1eAll(P,K): the explicit expressions for the terms of`):
print(` the  sequence maximum number of 1's for words in {0,1}`):
print(`avoiding the generalized patterns in P, using the clever`):
print(`approach, with K terms to guess. also lists all the`):
print(`auxiliary ones of the scheme.`):
print(`it also returns the scheme as the second argument of the output.`):
print(`and the third argument is the dictionary, describing the`):
print(`prefix forbidden sets.`):
print(`For example, try:`):
print(`SeqN1eAll({[1,1,1],[1,2,1,2,1]},100);`):

elif nops([args])=1 and op(1,[args])=SeqN1eAllV then
print(`SeqN1eAllV(P,K,n,F,m): verbose form of SeqN1eAll(P,K)`):
print(`phrased in terms of F[i](n) `):
print(`For example, try:`):
print(`SeqN1eAllV({[1,1,1],[1,2,1,2,1]},100,n,F,m);`):

elif nops([args])=1 and op(1,[args])=SeqN1eAllAndProve then
print(`SeqN1eAllAndProve(P,K): the explicit expressions for the terms of`):
print(` the  sequence maximum number of 1's for words in {0,1}`):
print(`avoiding the generalized patterns in P, using the clever`):
print(`approach, with K terms to guess. also lists all the`):
print(`auxiliary ones of the scheme`):
print(`it also proves its own conjecture rigorously`):
print(`the first argument is true or false`):
print(`For example, try:`):
print(`SeqN1eAllAndProve({[1,1,1],[1,2,1,2,1]},100);`):

elif nops([args])=1 and op(1,[args])=SeqN1d then
print(`SeqN1d(P,K): the first K terms of the  sequence `):
print(`"maximum number of 1's for words in {0,1}`):
print(`avoiding the generalized patterns in P, using the brute-force`):
print(`direct approach. For example, try:`):
print(`SeqN1d({[1,1,1],[1,2,1,2,1]},10);`):

elif nops([args])=1 and op(1,[args])=SeqN1dF then
print(`SeqN1dF(P,K):  like SeqN1d(P,K), but hopefully faster`):
print(`For example, try:`):
print(`SeqN1dF({[1,1,1],[1,2,1,2,1]},10);`):


elif nops([args])=1 and op(1,[args])=SeqN1eV then
print(`SeqN1eV(P,K,n,F): verbose version of SeqN1e(P,K): `):
print(`phrased in terms of discrete variable n and the symbol F`):
print(`for F(n)`):
print(`For example, try:`):
print(`SeqN1eV({[1,1,1],[1,2,1,2,1]},100,n,F);`):

elif nops([args])=1 and op(1,[args])=SeqN1gf then
print(`SeqN1gf(P,K): the first K terms of the  sequence `):
print(`"maximum number of 1's for words in {0,1}`):
print(`avoiding the generalized patterns in P, using generating`):
print(`functions. For example, try:`):
print(`SeqN1gf({[1,1,1],[1,2,1,2,1]},10);`):


elif nops([args])=1 and op(1,[args])=SipurSeqC then
print(`SipurSeqC(S,d,K,K1,n): the story of counting sequences for`):
print(`binary words avoiding the set of patterns`):
print(`S with spacings up to <=d,  using K terms`):
print(`but only displaying K1 terms `):
print(`For example, try:`):
print(`SipurSeqC({[0,0,0],[1,1,1]},2,200,30,n);`):

elif nops([args])=1 and op(1,[args])=SipurSeqCgf then
print(`SipurSeqCgf(S,d,K,K1,t,n): the story of counting sequences for`):
print(`binary words avoiding the set of patterns`):
print(`S with spacings up to <=d,  using K terms`):
print(`but only displaying K1 terms `):
print(`it also gives the generating functions in the variable t .`):
print(`For example, try:`):
print(`SipurSeqCgf({[0,0,0],[1,1,1]},2,200,30,t,n);`):

elif nops([args])=1 and op(1,[args])=SipurSze then
print(`SipurSze(k,d,K,m,F): the story of the finite version of`):
print(` Szemeredi's theorem `):
print(`with spaces of size<=d. `):
print(` It uses K data points. For example, try: `):
print(` SipurSze(3,2,200,m,F); `):

elif nops([args])=1 and op(1,[args])=SzeSeq then
print(`SzeSeq(k,N): the first N terms of the Szemeredi k-sequence`):
print(`the maximum possible size of a subset of {1,2,...,n}`):
print(`avoiding a k-term arithmetical progression, via the clever approach.`):
print(`For example, try:`):
print(`SzeSeq(3,10);`):

elif nops([args])=1 and op(1,[args])=SzeSeqC then
print(`SzeSeqC(k,N): the first N terms of the sequence`):
print(`the number of subsets of {1,2,...,n}`):
print(`avoiding a k-term arithmetical progression`):
print(`using the clever approach`):
print(`For example, try:`):
print(`SzeSeqC(3,10);`):

elif nops([args])=1 and op(1,[args])=SzeSeqCd then
print(`SzeSeqCd(k,N): the first N terms of the sequence`):
print(`the number of subsets of {1,2,...,n}`):
print(`avoiding a k-term arithmetical progression`):
print(`using the brute-force approach`):
print(`For example, try:`):
print(`SzeSeqCd(3,10);`):

elif nops([args])=1 and op(1,[args])=SzeSeqD then
print(`SzeSeqD(k,N): the first N terms of the Szemeredi k-sequence`):
print(`the maximum possible size of a subset of {1,2,...,n}`):
print(`avoiding a k-term arithmetical progression`):
print(`using the brute-force approach`):
print(`For example, try:`):
print(`SzeSeqD(3,10);`):

elif nops([args])=1 and op(1,[args])=Tsamek then
print(`Tsamek(P,SP): given a set of patterns P, SP, tries to shrink it`):
print(`as much as possible. For example, try:`):
print(`Tsamek({[1,1,1,1]},{[1,1,1],[1,1],[1]});`):

elif nops([args])=1 and op(1,[args])=Tsamek1 then
print(`Tsamek1(P,SP): given a set of patterns P, SP, tries to get rid of one`):
print(`For example, do`):
print(`Tsamek1({[1,1,1]},{[1,1],[1]});`):


elif nops([args])=1 and op(1,[args])=vdwSeqCd then
print(`vdwSeqCd(k,N): the first N terms of the sequence`):
print(`the number of subsets of {1,2,...,n}`):
print(`avoiding a k-term arithmetical progression`):
print(`and their complement as well `):
print(`using the brute-force approach`):
print(`For example, try:`):
print(`vdwSeqCd(3,10);`):

else
print(`There is no ezra for`,args):
fi:
 
end:




#ImpliedPs(p): all specific patterns implied by p
#For example, try:
#ImpliedPs([2,2]);
ImpliedPs:=proc(p) local p1,gu,g:
if not member(2,p) then
 RETURN({p}):
fi:

p1:=[op(2..nops(p),p)]:

 gu:=ImpliedPs(p1):

if p[1]<>2 then
 RETURN({seq([p[1],op(g)], g in gu)}):
else
 RETURN({seq([0,op(g)], g in gu), seq([1,op(g)], g in gu)}):
fi:

end:

#IsImpliedBy(p,q) is pattern p implied by pattern q?
#For example, try:
#IsImpliedBy([1,1,1],[1,2,1]);
IsImpliedBy:=proc(p,q)

if evalb(ImpliedPs(p) minus ImpliedPs(q)={}) then
 RETURN(true):
fi:

if nops(q)<nops(p) and [op(1..nops(q),p)]=q then
 RETURN(true):
fi:
false:


end:

#IsSuperfluous(P,SP,p): is pattern p in SP superflous?
IsSuperfluous:=proc(P,SP,p) local gu,g:

gu:=P union SP minus {p}:

for g in gu do
 if IsImpliedBy(p,g) then
    RETURN(true):
 fi:
od:
false:
end:





#Ben(P,SP): inputs a set of global patterns and starting patterns
#which are lists in {0,1,2} (2 means a blank) and outputs
#all the starting patterns (in addition to the global patterns)
#that the chopped word, obtained by chopping the first letter,
# avoids, if it starts with 1
#For example, try: 
#Ben({[1,1,1]},{});
Ben:=proc(P,SP) local gu,p,p1:

if member([],SP) then
 RETURN(FAIL):
fi:

gu:={}:

for p in P union SP do
if p[1]=1 or p[1]=2 then
p1:=[op(2..nops(p),p)]:
 gu:=gu union {p1}:
fi:
od:

Tsamek(P,gu):

end:


#Bat(P,SP): inputs a set of global patterns and starting patterns
#which are lists in {0,1,2} (2 means a blank) and outputs
#all the starting patterns (in addition to the global patterns)
#that the chopped word, obtained by chopping the first letter,
# avoids, if it starts with 0
#For example, try: 
#Bat({[1,1,1]},{});
Bat:=proc(P,SP) local gu,p,p1:

if member([],SP) then
 RETURN(FAIL):
fi:


gu:={}:

for p in P union SP do
if p[1]=0 or p[1]=2 then
 p1:=[op(2..nops(p),p)]:
 gu:=gu union {p1}:
fi:
od:


Tsamek(P,gu):
end:


#NotYetDone(S): given a partial scheme, finds all those
#not yet done
NotYetDone:=proc(S) local s:
{seq(s[2], s in S), seq(s[3], s in S)} minus {seq(s[1],s in S)}
minus {[]} minus {FAIL} :
end:



#Tsamek1(P,SP): given a set of patterns P, SP, tries to get rid of one
#For example, do
#Tsamek1({[1,1,1]},{[1,1],[1]});
Tsamek1:=proc(P,SP) local p,SP1:

for p in SP do
 SP1:=SP minus {p}:

  if IsSuperfluous(P,SP1,p) then
    RETURN(SP1):
  fi:
od:

FAIL:

end:


#Tsamek(P,SP): given a set of patterns P, SP, tries reduce SP
#as much as possible. For example, do
#Tsamek({[1,1,1]},{[1,1],[1]});
Tsamek:=proc(P,SP) local gu,gu1:

gu:=SP:
gu1:=Tsamek1(P,gu):

while gu1<>FAIL do
gu:=gu1:
gu1:=Tsamek1(P,gu1):
od:
gu:
end:


#Yafe(S): makes the scheme nice, also returns dictionary
Yafe:=proc(S) local S1,s,T1,i,L,L1,R1,mu:
S1:={seq(s[1], s in S)} minus {{}}:

mu:=[{}]:
T1[{}]:=1:
for i from 1 to nops(S1) do
T1[S1[i]]:=i+1:
mu:=[op(mu),S1[i]]:
od:

L:=subs({{[]}=0,{}=1,seq(s=T1[s],s in S1)},S):
L:=convert(L,list):
for i from 1 to nops(L) do
L1[L[i][1]]:=L[i][2]:
R1[L[i][1]]:=L[i][3]:
od:

[seq([L1[i],R1[i]],i=1..nops(L))],mu:

end:

#MakeScheme(P): given a set of patterns P finds a scheme
#in terms of a binary tree
#MakeScheme({[1,1,1]});
MakeScheme:=proc(P) local gu,lu1,lu2,gu1:
option remember:
lu1:=Ben(P,{}):
lu2:=Bat(P,{}):
gu:={[{},lu1,lu2]}:

while NotYetDone(gu)<>{} do
gu1:=NotYetDone(gu)[1]:
gu:=gu union {[gu1,Ben(P,gu1),Bat(P,gu1)]}:
od:

Yafe(gu minus {[{[]},FAIL,FAIL]} ) :

end:




#OneStep(S,L): one iteration in the scheme S applied to the list L
OneStep:=proc(S,L) local i,gu:

gu:=[]:

for i from 1 to nops(L) do
 if S[i][1]<>0 and S[i][2]<>0 then
 gu:=[op(gu), max(L[S[i][1]]+1,L[S[i][2]])]:
 elif S[i][1]<>0 and S[i][2]=0 then
 gu:=[op(gu), max(L[S[i][1]]+1,-infinity)]:
 elif S[i][1]=0 and S[i][2]<>0 then
 gu:=[op(gu), max(-infinity,L[S[i][2]])]:
 else
 gu:=[op(gu), -infinity]:
 fi:
od:
 
gu:
end:





#ManySteps(S,n): n  iterations in the scheme S applied to the list L
ManySteps:=proc(S,n) local L,gu,i:
L:=[0$nops(S)]:

gu:=[]:

for i from 1 to n do
L:=OneStep(S,L):
gu:=[op(gu),L]:
od:
gu:
end:



######Naive approach (for checking)

#IsBad1(w,p): given a word w in {0,1}, and a pattern p, returns true
#if w ends with the pattern p and false otherwise
#For example, try:
#IsBad1([1,0,0,1],[0,2,1]);
IsBad1:=proc(w,p) local i,w1,w2,p2:

if nops(w)<nops(p) then
 RETURN(false):
fi:
w1:=[op(nops(w)-nops(p)+1..nops(w),w)]:
w2:=[]:
p2:=[]:
for i from 1 to nops(p) do
if p[i]<>2 then
w2:=[op(w2),w1[i]]:
p2:=[op(p2),p[i]]:
fi:
od:
evalb(w2=p2):
end:

#IsBad(w,P): given a word w in {0,1}, and a set of patterns P, returns true
#if w ends with some pattern p of P, and false otherwise
#For example, try:
#IsBad([1,0,0,1],{[0,2,1]});
IsBad:=proc(w,P) local p:

for p in P do
 if IsBad1(w,p) then
    RETURN(true):
 fi:
od:
false:
end:


#GW(n,P): the set of all words in {0,1}, or length n, avoiding any of
#of the general patterns in the set P.
#For example, try GW(3,{[1,1,1],[0,2,0]});

GW:=proc(n,P) local mu,gu,m,w:
option remember:

if n=0 then
 RETURN({[]}):
fi:

mu:=GW(n-1,P):
gu:={}:
for m in mu do
w:=[op(m),0]:
if not IsBad(w,P) then
 gu:=gu union {w}:
fi:
w:=[op(m),1]:
if not IsBad(w,P) then
 gu:=gu union {w}:
fi:
od:
gu:
end:



#SeqCd(P,K): the first K terms of the counting sequence for words
#avoiding the generalized patterns in P, using the brute-force
#direct approach. For example, try:
#SeqCd({[1,1,1],[1,2,1,2,1]},10);
SeqCd:=proc(P,K) local k:
[seq(nops(GW(k,P)),k=1..K)]:
end:

#MaxN1(S): given a set of words S in the alphabet S
#finds the maximum number of 1's amongsts all words
#For example, try:
#MaxN1({[1,0,1],[0,0,1]});
MaxN1:=proc(S) local s:
max(seq(convert(s,`+`), s in S)):
end:

#SeqN1d(P,K): the first K terms of the  sequence 
#"maximum number of 1's for words in {0,1}
#avoiding the generalized patterns in P, using the brute-force
#direct approach. For example, try:
#SeqN1d({[1,1,1],[1,2,1,2,1]},10);
SeqN1d:=proc(P,K) local k:
[seq(MaxN1(GW(k,P)),k=1..K)]:
end:



#SeqN1(P,K): the first K terms of the  sequence 
#"maximum number of 1's for words in {0,1}
#avoiding the generalized patterns in P, using the clever
#approach. For example, try:
#SeqN1({[1,1,1],[1,2,1,2,1]},10);
SeqN1:=proc(P,K) local i,S,lu:
S:=MakeScheme(P)[1]:
lu:=ManySteps(S,K):
[seq(lu[i][1],i=1..nops(lu))]:
end:



######End Naive approach (for checking)




#OneStepC(S,L): one iteration in the scheme S applied to the list L
#for counting
OneStepC:=proc(S,L) local i,gu:

gu:=[]:

for i from 1 to nops(L) do
 if S[i][1]<>0 and S[i][2]<>0 then
 gu:=[op(gu), L[S[i][1]]+L[S[i][2]] ]:
 elif S[i][1]<>0 and S[i][2]=0 then
 gu:=[op(gu), L[S[i][1]]]:
 elif S[i][1]=0 and S[i][2]<>0 then
 gu:=[op(gu), L[S[i][2]]]:
 else
 gu:=[op(gu), 0]:
 fi:
od:
 
gu:
end:


#ManyStepsC(S,n): n  iterations in the scheme S applied to the list L
#with counting
ManyStepsC:=proc(S,n) local L,gu,i:
L:=[1$nops(S)]:

gu:=[]:

for i from 1 to n do
L:=OneStepC(S,L):
gu:=[op(gu),L]:
od:
gu:
end:


#SeqC(P,K): the first K terms of the  sequence 
#"maximum number of 1's for words in {0,1}
#avoiding the generalized patterns in P, 
#clever approach. For example, try:
#SeqC({[1,1,1],[1,2,1,2,1]},10);
SeqC:=proc(P,K) local i,S,lu:
S:=MakeScheme(P)[1]:
lu:=ManyStepsC(S,K):
[seq(lu[i][1],i=1..nops(lu))]:
end:

#GuessPeriod(Lis): Given a list, guesses an ultimate period
GuessPeriod:=proc(Lis)
local s0,p,n,i,j,gu:
n:=nops(Lis)-4:
for s0 from 1 to trunc(n/3) do
for p from 1 to trunc((n-s0)/3) do
 if {seq(nops({seq(Lis[s0+p*i+j],i=0..trunc((n-j-s0)/p))}),j=1..p)}={1} 
   then
 gu:=[[op(1..s0,Lis)],[op(s0+1..s0+p,Lis)]]:
  if nops(gu[1])=1 and nops(gu[2])>=1 and gu[1][1]=gu[2][1] then
    gu:=[[],gu[2]]:
  fi:
     RETURN(gu):
fi:
od:
od:
FAIL:
end:





#GuessSeq(L): Given a sequence of increasing integers,
#tries to guess an expression of the form [N,M,L1]
#where L1 has N terms
#GuessSeq(L): for example, try: GuessSeq([seq(i,i=1..100)]);

GuessSeq:=proc(L) local L1,gu,mu,N,M,hatkhel,i,k,lu:

L1:=[seq(L[i]-L[i-1],i=2..nops(L))]:
gu:=GuessPeriod(L1):

if gu=FAIL then
 RETURN(FAIL):
fi:

hatkhel:=nops(gu[1])+2:
mu:=gu[2]:

N:=nops(mu):
M:=convert(mu,`+`):


lu:={seq([seq(L[N*k+i]-M*k,i=1..N)],
k=trunc(hatkhel/N)+2..trunc(nops(L)/N)-1) }:

if nops(lu)<>1 then
 RETURN(FAIL):
fi:

[N,M,lu[1]]:

end:





#SeqN1e(P,K): the explicit expression for the terms of the  sequence 
#"maximum number of 1's for words in {0,1}
#avoiding the generalized patterns in P, using the clever
#approach, with K terms to guess. For example, try:
#SeqN1e({[1,1,1],[1,2,1,2,1]},100);
SeqN1e:=proc(P,K):
GuessSeq(SeqN1(P,K)):
end:




#####with the champions


#MaxN1A(S): given a set of words S in the alphabet S
#finds the maximum number of 1's amongsts all words
#followed by the champion
#For example, try:
#MaxN1A({[1,0,1],[0,0,1]});
MaxN1A:=proc(S) local s,alufim,si,hal:

si:=0:
alufim:={}:

for s in S do
 hal:=convert(s,`+`):
  if hal>si then
    si:=hal:
    alufim:={s}:
  elif hal=si then
   alufim:=alufim union {s}:
 fi:
od:
[si,alufim]:
end:

#SeqN1dA(P,K): the first K terms of the  sequence 
#"maximum number of 1's for words in {0,1}
#avoiding the generalized patterns in P, followed by the
#set of champtions
#using the brute-force
#direct approach. For example, try:
#SeqN1dA({[1,1,1],[1,2,1,2,1]},10);
SeqN1dA:=proc(P,K) local k:
[seq(MaxN1A(GW(k,P)),k=1..K)]:
end:







#SeqN1eAll(P,K): the explicit expressions for the terms of the  sequence 
#"maximum number of 1's for words in {0,1}
#avoiding the generalized patterns in P, using the clever
#approach, with K terms to guess. also lists all the
#auxiliary ones of the scheme
#For example, try:
#SeqN1eAll({[1,1,1],[1,2,1,2,1]},100);
SeqN1eAll:=proc(P,K) local S,lu,i,j,mu,M,N,x,y,mu1,ku:
S:=MakeScheme(P)[1]:
ku:=MakeScheme(P)[2]:
lu:=ManySteps(S,K):

mu:=[seq( GuessSeq([seq(lu[i][j],i=1..nops(lu))]),j=1..nops(S))]:

if member(FAIL,{op(mu)}) then
 RETURN(FAIL):
fi:

M:=max(seq(mu[i][1],i=1..nops(mu))):
N:=max(seq(mu[i][2],i=1..nops(mu))):


mu1:=[]:

for i from 1 to nops(mu) do
 if mu[i][1]=M and mu[i][2]=N then
 mu1:=[op(mu1),mu[i]]:
 else
  x:=M/mu[i][1]: y:=N/mu[i][2]:
   if not (x=y and type(x,integer) ) then
    RETURN(FAIL):
   fi:
  mu1:=[op(mu1),[Inflate(op(mu[i]),x)] ]:
 fi:
od:

mu1,S,ku:
end:


#SeqN1eAllAndProve(P,K): 
#the explicit expressions for the terms of the  sequence 
#"maximum number of 1's for words in {0,1}
#avoiding the generalized patterns in P, using the clever
#approach, with K terms to guess. also lists all the
#auxiliary ones of the scheme. And then proves it (rigorously).
#For example, try:
#SeqN1eAllAndProve({[1,1,1],[1,2,1,2,1]},100);
SeqN1eAllAndProve:=proc(P,K) local i,j,mu,c,ka,S:



S:=MakeScheme(P)[1]:

mu:=SeqN1eAll(P,K):

if mu=FAIL then
 RETURN(FAIL):
fi:

mu:=mu[1]:


ka:={seq([mu[i][1],mu[i][2]],i=1..nops(mu))}:

if nops(ka)<>1 then
 RETURN(FAIL):
fi:

ka:=ka[1]:

c:=[seq(mu[i][3],i=1..nops(mu))]:



for i from 1 to nops(S) do

 if S[i][1]<>0 and S[i][2]<>0 then

  for j from 2 to ka[1] do
   
   if not max(c[S[i][1]][j-1]+1,c[S[i][2]][j-1])=c[i][j] then
          RETURN(false,FAIL,FAIL):
   fi:
  
  od:


if not max(c[S[i][1]][ka[1]]+1,c[S[i][2]][ka[1]])=c[i][1]+ka[2] then
          RETURN(false,FAIL,FAIL):
fi:


 elif S[i][1]<>0 and S[i][2]=0 then

  for j from 2 to ka[1] do
   
  if not c[S[i][1]][j-1]+1=c[i][j] then
          RETURN(false,FAIL,FAIL):
  fi:
  
  od:

   if not c[S[i][1]][ka[1]]+1=c[i][1]+ka[2] then
          RETURN(false,FAIL,FAIL):
   fi:

 elif S[i][1]=0 and S[i][2]<>0 then


  for j from 2 to ka[1] do
   
   if not c[S[i][2]][j-1]=c[i][j] then
          RETURN(false,FAIL,FAIL):
   fi:
  
  od:

   if not c[S[i][2]][ka[1]]=c[i][1]+ka[2] then
          RETURN(false,FAIL,FAIL):
   fi:

 fi:

od:



true,ka,c:
end:





#Pats(k,d): the set of patterns of AP up to spacing d-1. Try:
#Pats(3,4);
Pats:=proc(k,d) local i,j:
{seq( [seq(op([1,2$i]),j=1..k-1),1],i=0..d-1)}:
end:


#SzeSeq(k,N): the first N terms of the Szemeredi k-sequence
#the maximum possible size of a subset of {1,2,...,n}
#avoiding a k-term arithmetical progression
#For example, try:
#SzeSeq(3,10);
SzeSeq:=proc(k,N) local d,i,P,j:
d:=trunc((N-k)/(k-1)):
P:={seq( [seq(op([1,2$i]),j=1..k-1),1],i=0..d)}:
SeqN1(P,N):
end:

#SzeSeqD(k,N): the first N terms of the Szemeredi k-sequence
#by the direct (brute-force) approach
#the maximum possible size of a subset of {1,2,...,n}
#avoiding a k-term arithmetical progression
#For example, try:
#SzeSeqD(3,10);
SzeSeqD:=proc(k,N) local d,i,P,j:
d:=trunc((N-k)/(k-1)):
P:={seq( [seq(op([1,2$i]),j=1..k-1),1],i=0..d)}:
print(`P is`, P):
SeqN1d(P,N):
end:




#SzeSeqC(k,N): the first N terms of the
#the number of subsets of {1,2,...,n}
#avoiding a k-term arithmetical progression
#For example, try:
#SzeSeqC(3,10);
SzeSeqC:=proc(k,N) local d,i,P,j:
d:=trunc((N-k)/(k-1)):
P:={seq( [seq(op([1,2$i]),j=1..k-1),1],i=0..d)}:
SeqC(P,N):
end:


#SzeSeqCd(k,N): the first N terms of the
#the number of subsets of {1,2,...,n}
#avoiding a k-term arithmetical progression
#For example, try:
#SzeSeqCd(3,10);
SzeSeqCd:=proc(k,N) local d,i,P,j:
d:=trunc((N-k)/(k-1)):
P:={seq( [seq(op([1,2$i]),j=1..k-1),1],i=0..d)}:
SeqCd(P,N):
end:


#vdwSeqCd(k,N): the first N terms of the
#the number of subsets of {1,2,...,n}
#avoiding a k-term arithmetical progression
#and their compleent
#For example, try:
#vdwSeqCd(3,10);
vdwSeqCd:=proc(k,N) local d,i,P,j:
d:=trunc((N-k)/(k-1)):
P:={seq( [seq(op([1,2$i]),j=1..k-1),1],i=0..d),
seq( [seq(op([0,2$i]),j=1..k-1),0],i=0..d)
}:
SeqCd(P,N):
end:



#Inflate(M,N,resh,x): given a period f(Mk+i)=Nk+resh[i]
#blows it up by x, for example, try
#Inflate(3,2,[1,1,2],3);
Inflate:=proc(M,N,resh,x) local i,j:
M*x,N*x,[seq(seq(resh[i]+j*N,i=1..nops(resh)),j=0..x-1)]:
end:




#GWnk(n,k,P): the set of all words in {0,1} lf length n
#with k 1's avoiding any of
#of the general patterns in the set P.
#For example, try GWnk(3,2,{[1,1,1],[0,2,0]});

GWnk:=proc(n,k,P) local mu,gu,m,w:
option remember:

if n=0 then
 if k=0 then
 RETURN({[]}):
 else
  RETURN({}):
 fi:
fi:

gu:={}:
mu:=GWnk(n-1,k,P):
for m in mu do
w:=[op(m),0]:
if not IsBad(w,P) then
 gu:=gu union {w}:
fi:
od:

mu:=GWnk(n-1,k-1,P):

for m in mu do
w:=[op(m),1]:
if not IsBad(w,P) then
 gu:=gu union {w}:
fi:
od:

gu:
end:




#Max1(n,P): the maximal number of 1's in an n-letter word in {0,1}
#avoiding P
#For example, try:
#Max1(n,P) 
Max1:=proc(n,P) local k:
for k from n by -1 to 1 while GWnk(n,k,P)={} do od:
[k, GWnk(n,k,P)]:
end:



#SeqN1dF(P,K):  like SeqN1d(P,K), but (hopefully) faster
#also returns the champions
#For example, try:
#SeqN1dF({[1,1,1],[1,2,1,2,1]},10);
SeqN1dF:=proc(P,K) local gu,i,n:
gu:=[seq(Max1(n,P),n=1..K)]:
[seq(gu[i][1],i=1..nops(gu))],[seq(gu[i][2],i=1..nops(gu))]:
end:



#SzeSeqDf(k,N): the first N terms of the Szemeredi k-sequence
#by the direct (brute-force) approach
#the maximum possible size of a subset of {1,2,...,n}
#avoiding a k-term arithmetical progression
#For example, try:
#SzeSeqD(3,10);
SzeSeqDf:=proc(k,N) local d,i,P,j:
d:=trunc((N-k)/(k-1)):
P:={seq( [seq(op([1,2$i]),j=1..k-1),1],i=0..d)}:
SeqN1dF(P,N):
end:

#B(n): all the binary vectors of size n
B:=proc(n) local gu,g:
option remember:

if n=0 then
 RETURN({[]}):
else
 gu:=B(n-1):
 RETURN({seq([op(g),0],g in gu), seq([op(g),1],g in gu)}):
fi:


end:



 




#GFs(S,x,t): the generating function in x,t (wt. is x^(#1's)*t^(length))
#corresponding to the scheme S

GFs:=proc(S,x,t) local eq,var,f,n,i:
n:=nops(S):
var:={seq(f[i],i=1..n)}:

eq:={}:

for i from 1 to n do
 if S[i][1]<>0 and S[i][2]<>0 then
  eq:=eq union {f[i]-1-x*t*f[S[i][1]]-t*f[S[i][2]]}:
 elif S[i][1]=0 and S[i][2]<>0 then
  eq:=eq union {f[i]-1-t*f[S[i][2]]}:
 elif S[i][1]<>0 and S[i][2]=0 then
  eq:=eq union {f[i]-1-x*t*f[S[i][1]]}:

 elif S[i][1]=0 and S[i][2]=0 then
  eq:=eq union {f[i]-1}:

 fi:
od:


var:=solve(eq,var):

normal(subs(var,f[1])):

end:


#GFp(P,x,t): the weight-enumerator of all words in {0,1}
#avoiding the set of generalized patterns P
#where the weight of a word is x^(#1's)*t^(#length)
GFp:=proc(P,x,t): GFs(MakeScheme(P)[1],x,t): end:


#SeqCgf(P,K): the first K terms of the counting sequence for words
#avoiding the generalized patterns in P, using generating functions
#For example, try:
#SeqCgf({[1,1,1],[1,2,1,2,1]},10);
SeqCgf:=proc(P,K) local f,i,t:
f:=GFp(P,1,t):
f:=taylor(f,t=0,K+1):
[seq(coeff(f,t,i),i=1..K)]:
end:


#SeqN1gf(P,K): Computing SeqN1 using generating functions
#For example, try:
#SeqN1gf({[1,1,1],[1,2,1,2,1]},10);
SeqN1gf:=proc(P,K) local f,i,x,t:
f:=GFp(P,x,t):
f:=taylor(f,t=0,K+1):
[seq(degree(coeff(f,t,i),x),i=1..K)]:
end:




#Akd(k,d,K): the asymptotic maximum relative size of a subset of [1,n]
#avoiding arith. prog. of length k with differences <=d
#with K terms to guess
#For example, try
#Akd(3,2,200);
Akd:=proc(k,d,K) local P,i,j,lu:
P:={seq( [seq(op([1,2$i]),j=1..k-1),1],i=0..d)}:
lu:=GuessSeq(SeqN1(P,K)):
lu[2]/lu[1]:
end:





#SeqN1eV(P,K,n,F): verbose version of SeqN1e(P,K): 
#For example, try:
#SeqN1eV({[1,1,1],[1,2,1,2,1]},100),n,F);
SeqN1eV:=proc(P,K,n,F) local gu,i:
gu:=SeqN1e(P,K):

if gu=FAIL then
 RETURN(FAIL):
fi:


print(`Theorem: Let F(n) be the maximum number of 1's in the alphabet {0,1}`):
print(`that an n-letter word avoiding the generalized patterns`):
print(P):
print(`may have , i.e. any n-letter word with F(n)+1 1's MUST`):
print(`contain at least one of these patterns`):
print(`Here 2 denotes either 0 or 1 `):
print(``):
print(`We have the following explicit expression for F(n) as a `):
print(`piece-wise linear discrete function`):

if gu[1]<>nops(gu[3]) then
ERROR(`Something is wrong`):
fi:

for i from 1 to gu[1] do
print(F(gu[1]*n+i)=gu[2]*n+gu[3][i]):
od:

end:




#MakeSchemeV(P,F,n): Verbose version of MakeScheme(P).
#For example, try:
#MakeSchemeV({[1,1,1]},F,n);
MakeSchemeV:=proc(P,F,n) local gu,mu,i:
gu:=MakeScheme(P):
mu:=gu[2]:
gu:=gu[1]:
print(`Let F[1](n) be the largest number of ones that an n-letter`):
print(`word in the alphabet {0,1} that avoids the generalized patterns`):
print(P):
print(`can have.`):
print(``):
print(`In order to compute F[1](n) we need the following auxiliary`):
print(`discrete functions.`):

for i from 2 to nops(mu) do
 print(`Let `, F[i](n),  `be the largest number of ones that an n-letter`):
 print(`word in the alphabet {0,1} that avoids the above-mentioned`):
 print(`generalized patterns, and IN ADDITION, avoids, at the beginning`):
 print(mu[i]):
od:

print(`We have the following recursive scheme `):

 for i from 1 to nops(gu) do
  if gu[i][1]<>0 and gu[i][2]<>0 then
   print(F[i][n]=max(F[gu[i][1]](n-1)+1,F[gu[i][2]](n-1))):
  elif gu[i][1]=0 and gu[i][2]<>0 then
   print(F[i][n]=max(-infinity,F[gu[i][2]](n-1))):
  elif gu[i][1]<>0 and gu[i][2]=0 then
   print(F[i][n]=max(F[gu[i][1]](n-1)+1,-infinity)):
  else
   ERROR(`Something is wrong`):
 fi:
od:

end:



#SeqN1eAllV(P,K,n,F,m): verbose version of SeqN1eAll(P,K): 
#For example, try:
#SeqN1eAllV({[1,1,1],[1,2,1,2,1]},100),n,F);
SeqN1eAllV:=proc(P,K,n,F,m) local mu,gu,i,j,ku,ku1,K1:
mu:=SeqN1eAll(P,K):

if mu=FAIL then
 RETURN(FAIL):
fi:



print(`Theorem: Let F(n) be the maximum number of 1's that an n-letter`):
print(`word in the alphabet {0,1}`):
print(`avoiding the generalized patterns`):
print(P):
print(`may have , i.e. any n-letter word in {0,1} with F(n)+1 1's MUST`):
print(`contain at least one of these patterns.`):
print(`[Here 2 denotes either 0 or 1]. `):
print(``):
print(`We have the following explicit expression for F(n) as a `):
print(`piece-wise linear discrete function`):


gu:=mu[1][1]:
if gu[1]<>nops(gu[3]) then
ERROR(`Something is wrong`):
fi:
ku1:=[]:
for j from 1 to gu[1] do
print(F(gu[1]*m+j)=gu[2]*m+gu[3][j]):
ku1:=[op(ku1), [gu[1]*m+j,gu[2]*m+gu[3][j]]]:
od:

ku:=[ku1]:
print(`Proof:`):
print(`In order to prove this, by induction, we need `, nops(mu[1])-1):
print(`additional statments, regarding the following discrete functions`):

for i from 2 to nops(mu[3]) do

print(`------------------`):
print(`Definition `,i,`:`, `Let `,  F[i](n), `be the maximum number of `):
print(` possible 1's `):
print(`that an n-letter word in {0,1}, avoiding the above-mentioned `):
print(`generalized patterns`):
print(`and IN ADDITION, avoiding at the VERY BEGINNING, the generalized`):
print(` patterns `):
print(mu[3][i]):
print(``):
od:
print(`-----------------------------`):
print(`In order to faciliate the inductive proof we need a`):
print(`more General Statement:`):
print(` We have the following explicit expressions for them as`):
print(`piece-wise linear discrete functions.`):
print(`[For the sake of readability we restate the formulas for`):
print(`F[1](n)=F(n) already given above]`):



for i from 2 to nops(mu[1]) do
print(`---------------------`):
gu:=mu[1][i]:
if gu[1]<>nops(gu[3]) then
ERROR(`Something is wrong`):
fi:

ku1:=[]:
for j from 1 to gu[1] do
print(F[i](gu[1]*m+j)=gu[2]*m+gu[3][j]):
ku1:=[op(ku1),[gu[1]*m+j,gu[2]*m+gu[3][j]]]:
od:
ku:=[op(ku),ku1]:
od:


print(`Proof: Let F[1](n)=F(n). By considering whether the first letter`):
print(`is a 1 or a 0, chopping it, and figuring out the set `):
print(`of forbidden prefix patterns for the two kinds of chopped words`):

gu:=mu[2]:

print(`We have the following recursive scheme `):

 for i from 1 to nops(gu) do
  if gu[i][1]<>0 and gu[i][2]<>0 then
   print(F[i][n]=max(F[gu[i][1]](n-1)+1,F[gu[i][2]](n-1))):
  elif gu[i][1]=0 and gu[i][2]<>0 then
   print(F[i][n]=max(-infinity,F[gu[i][2]](n-1))):
  elif gu[i][1]<>0 and gu[i][2]=0 then
   print(F[i][n]=max(F[gu[i][1]](n-1)+1,-infinity)):
  else
   ERROR(`Something is wrong`):
 fi:
od:

print(`We have to prove, by induction,`):
print(` that the above explicit expressions for `):
print(`F[i](n) do indeed satisfy this recursive scheme.`):
print(`But this is indeed `, SeqN1eAllAndProve(P,K)[1], ` . ` ):

if not SeqN1eAllAndProve(P,K)[1] then
RETURN(FAIL):
fi:

print(`Let's see why.`):

 for i from 1 to nops(gu) do
K1:=nops(ku[i]):
 print(`Case `, i):
  if gu[i][1]<>0 and gu[i][2]<>0 then
  print(`We have to prove that `):
   print(F[i](n)=max(F[gu[i][1]](n-1)+1,F[gu[i][2]](n-1))):
   print(`spelling-out according to cases, we have to prove`):
 
  for j from 1 to 1 do
   print(` Subcase `, [i,j] ):    
      print(F[i](ku[i][j][1])=ku[i][j][2]):
   print(`Now `, F[gu[i][1]](subs(m=m-1,ku[gu[i][1]][K1][1]))+1=
subs(m=m-1,ku[gu[i][1]][K1][2])+1):
   print(`and `, F[gu[i][2]](
subs(m=m-1,ku[gu[i][2]][K1][1]))=subs(m=m-1,ku[gu[i][2]][K1][2])):
 print(`and of course`):
 print(ku[i][1][2]=Max(
subs(m=m-1,ku[gu[i][1]][K1][2])+1,subs(m=m-1,ku[gu[i][2]][K1][2]))):
    od:
 
   for j from 2 to nops(ku[i]) do
   print(`Subcase `, [i,j] ):    
      print(F[i](ku[i][j][1])=ku[i][j][2]):
   print(`Now `, F[gu[i][1]](ku[gu[i][1]][j-1][1])+1=ku[gu[i][1]][j-1][2]+1):
   print(`and `, F[gu[i][2]](ku[gu[i][2]][j-1][1])=ku[gu[i][2]][j-1][2]):
 print(`and of course`):
 print(ku[i][j][2]=Max(ku[gu[i][1]][j-1][2]+1,ku[gu[i][2]][j-1][2])):
    od:
 
     
  elif gu[i][1]=0 and gu[i][2]<>0 then

  print(`We have to prove that `):
   print(F[i][n]=max(-infinity,F[gu[i][2]](n-1))):
   print(`spelling-out according to cases, we have to prove`):
    for j from 1 to nops(ku[i]) do
      print(F[i](ku[i][j][1])=ku[i][j][2]):
    od:
  print(`but this is immediate`):

  elif gu[i][1]<>0 and gu[i][2]=0 then

  print(`We have to prove that `):
   print(F[i][n]=max(F[gu[i][1]](n-1)+1,-infinity)):
   print(`spelling-out according to cases, we have to prove`):
    for j from 1 to nops(ku[i]) do
      print(F[i](ku[i][j][1])=ku[i][j][2]):
    od:
  print(`but this is immediate`):





  else
   ERROR(`Something is wrong`):
 fi:
od:



print(`QED. `):

ku:

end:




#PutSpaces1(w,i): Given a word w in {0,1} puts i spaces (2)
#between each letter. For example, try:
#PutSpaces1([1,0,1],2);
PutSpaces1:=proc(w,i) local j:
[seq(op([w[j],2$i]),j=1..nops(w)-1),w[nops(w)]]:
end:

#PutSpaces1Ad(w,i): Given a word w in {0,1} puts i1 spaces (2)
#between each letter i1<=i. For example, try:
#PutSpaces1Ad([1,0,1],2);
PutSpaces1Ad:=proc(w,i) local j:
{seq(PutSpaces1(w,j),j=0..i)}:
end:

#PutSpacesAd(S,i): Given a set of words S in {0,1} puts i1 spaces (2)
#between each letter i1<=i for all the words.
# For example, try:
#PutSpacesAd({[1,1,1],[0,0,0]},2);
PutSpacesAd:=proc(S,i) local w:
{seq(op(PutSpaces1Ad(w,i)),w in S)}:
end:



#Images1(w): all the images of the word w under
#0->1,1->0 and reverse
Images1:=proc(w) local i,w1:
w1:=[seq(w[nops(w)+1-i],i=1..nops(w))]:
{w,subs({0=1,1=0},w), w1 ,subs({0=1,1=0},w1)}:
end:



#Brep(k): a set of representatives of 
#k-lettered words in {0,1}
#For example, try:
#Brep(k)
Brep:=proc(k) local gu,mu,lu:
gu:=B(k):
mu:={}:
while gu<>{} do
lu:=Images1(gu[1]):
mu:=mu union {lu}:
gu:=gu minus lu:
od:
mu:
end:





#SipurSze(k,d,K,m,F): the story of the finite version of Szemeredi's theorem
#with spaces of size<=d. 
#It uses K data points. For example, try:
#SipurSze(3,2,200,m,N);
SipurSze:=proc(k,d,K,m,F) local d1,mu,P,i:
print(`This is the story for the maximum size of a subset of [1,N]`):
print(`avoiding arithmetical progressions of size`, k, `with gaps`):
print(`less-than-or-equal to`, d+1 , ` . ` ):

for d1 from 0 to d do
print(`----------------------------`):
P:=PutSpacesAd({[1$k]},d1):
mu:=SeqN1e(P,K):
print(`Let F(N) be the largest size of a subset of [1,N] `):
print(`avoiding arithmetical progressions of size `, k, `with spacings <=`, d1+1 , ` .  Then: `):
for i from 1 to nops(mu[3]) do
print(F(m*mu[2]+i)= mu[1]*m+mu[3][i] ):
od:

print(`The asymptotic density is`, mu[2]/mu[1], ` . `):
od:

end:




#SipurSeqCgf(S,d,K,K1,t,n): the story of counting sequences for
#binary words avoiding the set of patterns
#S with spacings up to <=d,  using K terms
#but only displaying K1 terms
#it also gives the generating functions in the variable t .
#For example, try:
#SipurSeqCgf({[0,0,0],[1,1,1]},2,200,30,t,n);
SipurSeqCgf:=proc(S,d,K,K1,t,n) local d1,P,gu,c,C,mu,c1,c2:

for d1 from 0 to d do
 P:=PutSpacesAd(S,d1):
  gu:=GFp(P,1,t): 
  mu:=SeqC(P,K):
 print(`The first `, K1, `terms of the counting sequence for binary words`):
 print(`avoiding the set of patterns`, S, `with spacings <= `, d1, `are `):
 print([op(1..K1,mu)]):
 print(`The generating function is`, gu):

 c1:=evalf(mu[K]/mu[K-1]); 
 c2:=evalf(mu[K-1]/mu[K-2]); 
 if abs(c1-c2)<10^(-6) then
  c:=evalf(c1,5):
C:=evalf(mu[K]/c^K,5):
 print(`the asymptotics seems to be roughly`, C*c^n ):
fi:


od:
end:


#SipurSeqC(S,d,K,K1,n): the story of counting sequences for
#binary words avoiding the set of patterns
#S with spacings up to <=d,  using K terms
#but only displaying K1 terms
#For example, try:
#SipurSeqC({[0,0,0],[1,1,1]},2,200,30,t,n);
SipurSeqC:=proc(S,d,K,K1,n) local d1,P,c,C,mu,c1,c2:

for d1 from 0 to d do
 P:=PutSpacesAd(S,d1):
  mu:=SeqC(P,K):
 print(`The first `, K1, `terms of the counting sequence for binary words`):
 print(`avoiding the set of patterns`, S, `with spacings <= `, d1, `are `):
 print([op(1..K1,mu)]):
 c1:=evalf(mu[K]/mu[K-1]); 
 c2:=evalf(mu[K-1]/mu[K-2]); 
 if abs(c1-c2)<10^(-6) then
  c:=evalf(c1,5):
C:=evalf(mu[K]/c^K,5):
 print(`the asymptotics seems to be roughly`, C*c^n ):
fi:

od:
end:



#Contest(k,d,K,K1,t): the contest between all single patterns  of length k
#and spacing <=d, using K terms, displaying K1 terms and
#also giving the generating functions.
#For example, try:
#Contest(3,2,300,30,t);
Contest:=proc(k,d,K,K1,t) local P,si1,aluf1,si2, aluf2, gu,g,lu,mu,c:
gu:=Brep(k):

aluf1:=0:
aluf2:=0:
si1:=2:
si2:=0:

for g in gu do
 P:=PutSpacesAd({g[1]},d):
 lu:=SeqC(P,K):
 c:=evalf(lu[K]/lu[K-1]):
 mu:=GFp(P,1,t): 
 print(`For words avoiding the pattern`, g[1], `with spacings <=`, d):
 print(`the generating function is`, mu):
 print(`the first `, K1, `terms are `, [op(1..K1,lu)] ):
 print(`the asympt. constant is`, c):
  if c<si1 then
     si1:=c:
     aluf1:=g[1]:
  fi:
  
if c>si2 then
     si2:=c:
     aluf2:=g[1]:
  fi:
  
od:
 print(`The low champion is`, aluf1, `with asympt. constant`, si1):
 print(`The high champion is`, aluf2, `with asympt. constant`, si2):

end:



#ContestAd(k,d,K,K1,t): the contest between all single patterns  of length k
#and spacing <=d1, for d1=1..d ,using K terms, displaying K1 terms and
#also giving the generating functions.
#For example, try:
#ContestAd(3,2,300,30,t);
ContestAd:=proc(k,d,K,K1,t) local d1:
for d1 from 0 to d do
 Contest(k,d1,K,K1,t):
od:
end:




#OneStepCx(S,L,x): one iteration in the scheme S applied to the list L
#for x-counting
OneStepCx:=proc(S,L,x) local i,gu:

gu:=[]:

for i from 1 to nops(L) do
 if S[i][1]<>0 and S[i][2]<>0 then
 gu:=[op(gu), expand(x*L[S[i][1]]+L[S[i][2]]) ]:

 elif S[i][1]<>0 and S[i][2]=0 then
 gu:=[op(gu), expand(x*L[S[i][1]])]:

 elif S[i][1]=0 and S[i][2]<>0 then
 gu:=[op(gu), L[S[i][2]]]:

 else
 gu:=[op(gu), 0]:
 fi:
od:
 
gu:
end:


#ManyStepsCx(S,n,x): n  iterations in the scheme S applied to the list L
#with counting
ManyStepsCx:=proc(S,n,x) local L,gu,i:
L:=[1$nops(S)]:

gu:=[]:

for i from 1 to n do
L:=OneStepCx(S,L,x):
gu:=[op(gu),L]:
od:
gu:
end:





#SeqCx(P,K,x): the first K terms of the  sequence 
#"maximum number of 1's for words in {0,1}
#avoiding the generalized patterns in P, 
#clever approach. For example, try:
#SeqCc({[1,1,1],[1,2,1,2,1]},10,x);
SeqCx:=proc(P,K,x) local i,S,lu:
S:=MakeScheme(P)[1]:
lu:=ManyStepsCx(S,K,x):
[seq(lu[i][1],i=1..nops(lu))]:
end:

#OneStepCx(S,L,x): one iteration in the scheme S applied to the list L
#for x-counting
OneStepCx:=proc(S,L,x) local i,gu:

gu:=[]:

for i from 1 to nops(L) do
 if S[i][1]<>0 and S[i][2]<>0 then
 gu:=[op(gu), expand(x*L[S[i][1]]+L[S[i][2]]) ]:

 elif S[i][1]<>0 and S[i][2]=0 then
 gu:=[op(gu), expand(x*L[S[i][1]])]:

 elif S[i][1]=0 and S[i][2]<>0 then
 gu:=[op(gu), L[S[i][2]]]:

 else
 gu:=[op(gu), 0]:
 fi:
od:
 
gu:
end:


#ManyStepsCx(S,n,x): n  iterations in the scheme S applied to the list L
#with counting
ManyStepsCx:=proc(S,n,x) local L,gu,i:
L:=[1$nops(S)]:

gu:=[]:

for i from 1 to n do
L:=OneStepCx(S,L,x):
gu:=[op(gu),L]:
od:
gu:
end:





#SeqCx(P,K,x): the first K terms of the  sequence 
#"maximum number of 1's for words in {0,1}
#avoiding the generalized patterns in P, 
#clever approach. For example, try:
#SeqCc({[1,1,1],[1,2,1,2,1]},10,x);
SeqCx:=proc(P,K,x) local i,S,lu:
S:=MakeScheme(P)[1]:
lu:=ManyStepsCx(S,K,x):
[seq(lu[i][1],i=1..nops(lu))]:
end:





#OneStepCxx(S,L,x,n): one iteration in the scheme S applied to the list L
#for x-counting
OneStepCxx:=proc(S,L,x,n) local i,gu:

gu:=[]:

for i from 1 to nops(L) do
 if S[i][1]<>0 and S[i][2]<>0 then
 gu:=[op(gu), expand(x[n]*x*L[S[i][1]]+L[S[i][2]]) ]:

 elif S[i][1]<>0 and S[i][2]=0 then
 gu:=[op(gu), expand(x[n]*x*L[S[i][1]])]:

 elif S[i][1]=0 and S[i][2]<>0 then
 gu:=[op(gu), L[S[i][2]]]:

 else
 gu:=[op(gu), 0]:
 fi:
od:
 
gu:
end:



#ManyStepsCxx(S,x): n  iterations in the scheme S applied to the list L
#with counting
ManyStepsCxx:=proc(S,n,x) local L,gu,i:
L:=[1$nops(S)]:

gu:=[]:

for i from 1 to n do
L:=OneStepCxx(S,L,x,i):
gu:=[op(gu),L]:
od:
gu:
end:



#SeqCxx(P,K,x): the first K terms of the  sequence 
#"maximum number of 1's for words in {0,1}
#avoiding the generalized patterns in P, 
#clever approach. For example, try:
#SeqCxx({[1,1,1],[1,2,1,2,1]},10,x);
SeqCxx:=proc(P,K,x) local i,S,lu:
S:=MakeScheme(P)[1]:
lu:=ManyStepsCxx(S,K,x):
[seq(lu[i][1],i=1..nops(lu))]:
end:


#MtoW(W,x,n): Given a factor of x[1]*...*x[n] finds the word w such that it is x[1]^w[1]*...*x[n]^w[n]. Try:
#MtoW(x[1]*x[3],x,3):
MtoW:=proc(W,x,n) local i,w:
w:=[]:
for i from 1 to n do
 if degree(W,x[i])=1 then
  w:=[op(w),1]:
 else
  w:=[op(w),0]:
 fi:
od:
w:
end:


#MaxiWords(P,K): all the Parisi words (words avoiding the generalized patten P that have maximal size for their length and that are unique, Try
#MaxiWords({[1,1,1],[1,2,1,2,1]},10,x);
MaxiWords:=proc(P,K) local x,L1,L2,L,i:
L1:=SeqCx(P,K,x):
L2:=SeqCxx(P,K,x):

L:=[]:

for i from 1 to nops(L1) do
 if lcoeff(L1[i],x)=1 then
  L:=[op(L),[i,  MtoW(lcoeff(L2[i],x),x,i)]]:
 fi:
od:

L:

end:

#MGW(n,P): maximally good word: the set of good words in {0,1} avoiding P with a maximal number of 1's
MGW:=proc(n,P) local gu,gu1,m,lu:
 gu:=GW(n,P):
 m:=max(seq(convert(gu1,`+`),gu1 in gu)):
lu:={}:
for gu1 in gu do
 if convert(gu1,`+`)=m then
  lu:=lu union {gu1}:
 fi:
od:
lu:
end:





#IsTbad1(w,p): given a word w in {0,1}, and a pattern p, returns true
#if w contains the  pattern p and false otherwise
#For example, try:
#IsTbad1([1,0,0,1],[0,2,1]);
IsTbad1:=proc(w,p) local w1,i:

for i from 1 to nops(w)-nops(p)+1 do
 w1:=[op(i..i+nops(p)-1,w)]:
 if IsBad1(w1,p) then
   RETURN(true):
 fi:
od:
false:
end:



#IsTbad(w,P): given a word w in {0,1}, and a set of patterns P, returns true
#if w contains some pattern p of P, and false otherwise
#For example, try:
#IsTbad([1,0,0,1],{[0,2,1]});
IsTbad:=proc(w,P) local p:

for p in P do
 if IsTbad1(w,p) then
    RETURN(true):
 fi:
od:
false:
end:

#IsParisi(w,P): Inputs a finite word w in {0,1} decideds whether w^infinity avoids the all the patterns in P. Try:
#IsParisi([1,1,0],{[1,1,1],[1,2,1,2,1]});
#IsParisi([1,1,0,0],{[1,1,1],[1,2,1,2,1],[1,2,2,1,2,2,1]});

IsParisi:=proc(w,P) local p,m,W,i1:
m:=max(seq(nops(p), p in P)):
W:=[]:
for i1 from 1 to 5*m do
 W:=[op(W),op(w)]:
od:

not IsTbad(W,P):

end:



#Milim(n,k): all the words in {0,1} of length n with k 1's
Milim:=proc(n,k) local gu1,gu2,w:
option remember:
if n=0 then
if k=0 then
 RETURN({[]}):
else
 RETURN({}):
fi:
fi:
gu1:=Milim(n-1,k-1):
gu2:=Milim(n-1,k):
{seq([op(w),0],w in gu2),seq([op(w),1],w in gu1)}:

end:



#Cir(w): all the circular shifts of w
Cir:=proc(w) local i:
{seq([op(i..nops(w),w),op(1..i-1,w)],i=1..nops(w))}:
end:

#ParisiWords(n,k,P): Given a set of patterns P finds all Parisi words of length n with k 1's. Try:
#ParisiWords(9,4, Pats(3,3)):
ParisiWords:=proc(n,k,P) local lu,lu1,gu,w:
lu:=Milim(n,k):
gu:={}:
for lu1 in lu  do
 if IsParisi(lu1,P) then
  gu:=gu union {lu1}:
 fi:
od:



lu:={}:
while gu<>{} do
 lu:=lu union {gu[1]}:
 gu:=gu minus Cir(gu[1]):
od:
lu:

end: