###################################################################### ##ENDRE: Save this file as ENDRE # ##To use it, stay in the # ##same directory, get into Maple (by typing: maple ) # ##and then type: read ENDRE # ##Then follow the instructions given there # ## # ##Written by Doron Zeilberger, Rutgers University , # #zeilberg at math dot rutgers dot edu # ###################################################################### #Created: April 8, 2009 print(`Created: April 8, 2009`): print(` This is EDNRE `): print(`It is one of the packages that accompany 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(`*************************************`): with(combinat): 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])=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])=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])=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])=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)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)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: #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 csi2 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: