Help:=proc() if nargs=0 then print(`Welcome to mVATTER, a Maple package by Lara Pudwell`): print(`for the study of pattern-restricted words.`): print(): print(`The main functions in this package are:`): print(`mWilf(a,P), SchemeF(Patterns,Gvul), SipurF(L,Gvul,r,Nlist)`): print(`MiklosA(S,pre,a), MiklosTot(S,k,n), SeqS11(S,r,n), SeqSkn(S,k,n)`): print(): print(`To get help with a specific function, enter Help(function_name);`): elif nargs=1 and args[1]=AllPatternSets1 then print(`AllPatternSets1(L): Given a list of positive integers`): print(`finds the sets of permutations with the specified`): print(`lengths, for example, try:`): print(`AllPatternSets1([3,3]);`): elif nargs=1 and args[1]=AllPatternSets then print(`AllPatternSets(L): Given a list of positive integers`): print(`finds all the equilance classes (under trivial Wilf-equivalence)`): print(`of sets of permutations with the specified`): print(`lengths, for example, try:`): print(`AllPatternSets([3,3]);`): elif nargs=1 and args[1]=SipurF then print(`SipurF(L,Gvul,r,Nlist): Given a list L of pattern lengths,`): print(`a maximum scheme depth Gvul,`): print(`a positive integer r, and a list of length r of positive integers Nlist,`): print(`returns the following data for each equivalence class of permutations of lengths L`): print(`* an enumeration scheme of maximum depth Gvul and max gap vector length GvulGap `): print(`if it exists`): print(`* the r sequences of the number of words with i copies of each letter up to Nlist[i]`): print(`letters for i from 1 to r`): print(`for example, try:`): print(`SipurF([3],2,4,[10,8,6,6]);`): elif nargs=1 and args[1]=compl then print(`compl(perm): returns the complement of the word perm`): print(`for example, try:`): print(`compl([1,3,2,4,4,2]);`): elif nargs=1 and args[1]=COMPL then print(`COMPL(Perms): inputs a set of words Perms`): print(`and returns the set of complements of words in Perms`): print(`for example, try:`): print(`COMPL({[1,2,2,3,4],[4,1,3,2,4]});`): elif nargs=1 and args[1]=revers then print(`revers(perm): The reverse of the word perm`): print(`for example, try:`): print(`revers([1,3,2,4,4,2]);`): elif nargs=1 and args[1]=REVERS then print(`REVERS(Perms): inputs a set of words Perms`): print(`and returns the set of reverses of words in Perms`): print(`for example, try:`): print(`REVERS({[1,2,2,3,4],[4,1,3,2,4]});`): elif nargs=1 and args[1]=KHAVERIM then print(`KHAVERIM(Perms): Given a set of patterns Perms, outputs`): print(`all the images under the trivial-Wilf-equivalence group`): print(`For example, try:`): print(`KHAVERIM({[1,3,2]});`): elif nargs=1 and args[1]=SchemeImageF then print(`SchemeImageF(Patterns,Gvul): tries to find a scheme of max depth`): print(`Gvul for a Wilf-equivalent set of Patterns.`): print(`Returns a list of length 2. The first element is the equivalent set of`): print(`patterns, the second is the new scheme`): print(`for example, try:`): print(`SchemeImageF({[2,1,3]},2);`): elif nargs=1 and args[1]=GapVectorsF then print(`GapVectorsF(Patterns,pi,s): Given a set of patterns Patterns, a prefix permutation`): print(`pi, and a positive integer s finds all gap vectors of size <=s , in the Fast way.`): print(`For example, try: `): print(`GapVectorsF({[1,2,3]},[1,2],2);`): elif nargs=1 and args[1]=NewGapVectorsF then print(`NewGapVectorsF(Patterns,pi,s,G): Given a set of patterns Patterns and a prefix permutation`): print(`pi (of size k, say) and a positive integer s and a set of previously found gap vectors G`): print(`finds all gap vectors of size s not in G, in the Fast way.`): print(`For example, try: `): print(`NewGapVectorsF({[1,2,3]},[1,2],3,{[1,1,1]});`): elif nargs=1 and args[1]=isreallyv then print(`isreallyv(v,p): inputs a gap vector v and a prefix p`): print(`and decides whether v is a valid gap vector for p`): print(`for example try:`): print(`isreallyv([1,2,4],[1,2]);`): print(`versus`): print(`isreallyv([1,0,4],[1,2]);`): elif nargs=1 and args[1]=ImpliedGaps1 then print(`ImpliedGaps1(g,s): given a gap vector g, and a positive integer s, finds the set of all vectors of non-negative`): print(`integers of the same size as g and that add up to to s that are implied by g`): print(`For example, try:`): print(`ImpliedGaps1([1,1],4);`): elif nargs=1 and args[1]=ImpliedGaps then print(`ImpliedGaps(G,s): given a set of gap vectors G, and a positive integer s, finds the set of all vectors of non-negative`): print(`integers of the same size as g and that add up to to s that are implied by g in G`): print(`For example, try:`): print(`ImpliedGaps({[1,1],[0,2]},4);`): elif nargs=1 and args[1]=Comps then print(`Comps(a,n): the set of vectors of non-negative integers of length n that add up to a. `): print(`For example, try:`): print(`Comps(4,3);`): elif nargs=1 and args[1]=PGV then print(`PGV(g,pi,Patterns): proves or disproves that g is a gap vector for pi avoiding Patterns`): print(`for example, try:`): print(`PGV([0,1,1],[1,2],{[1,2,3]});`): elif nargs=1 and args[1]=Khaber then print(`Khaber(u,v); the sum of vectors u and v`): print(`for example, try:`): print(`Khaber([1,2,3],[-1,0,4]);`): elif nargs=1 and args[1]=isgoodvec then print(`isgoodvec(v): returns true if even positions of v are all 0 or 1`); elif nargs=1 and args[1]=PossVecs then print(`PossVecs(n,l): returns all possible vectors of length l with sum of entries n`): print(`which obey isgoodvec(v)`): print(`for example try:`): print(`PossVecs(3,3);`): elif nargs=1 and args[1]=SubScen then print(`SubScen(pi,p,s,Gaps): given prefix pi, permutation p, and scenario s, returns all possible ways the scenario s`): print(`can extend to pi while obeying Gaps`): print(`for example, try:`): print(`SubScen([1,4,3,2],[1,2,3],[1,4],{[0,1,1,1,1]});`): elif nargs=1 and args[1]=obeysG then print(`obeysG(v,Gaps): determines whether gap vector v obeys the vectors in Gaps`): elif nargs=1 and args[1]=Scenarios1 then print(`Scenarios1(pi,p,r,Gaps): Given a prefix permutation pi, a pattern p, a place r (1 between 1 and nops(pi)), and a set `): print(`of gap-vectors outputs all the subsets of {1, ..., nops(pi)} that contain r such that the subperm of pi in these`): print(`places reduces to the reduction of the appropriate prefix of p (of the same length)`): print(`For example, try:`): print(`Scenarios1([1,3,2],[1,2,3],2,{});`): elif nargs=1 and args[1]=SubScenarios1 then print(`SubScenarios1(pi,p,s1,Gaps): Given a prefix permutation pi, a pattern p, a list of positions of pi s1, and a set `): print(`of gap-vectors outputs all the subsets of {1, ..., nops(pi)} that contain r such that the subperm of pi in these`): print(`places reduces to the reduction of the appropriate prefix of p (of the same length)`): print(`SubScenarios1([1,3,2],[1,2,3],[1,3],{});`): elif nargs=1 and args[1]=roundv then print(`roundv(v): inputs a vector and rounds each non-integer entry to the next integer`): elif nargs=1 and args[1]=Scenarios then print(`Scenarios(pi,P,r,Gaps): Given a prefix permutation pi, a set of patterns P, and a place r (1 between 1 and nops(pi)) `): print(`and a set of gap-vectors Gaps, outputs all pairs [p,S] where p is in P and S is a set of assignements to the`): print(`pattern p relative to the elements of pi arising from scenarios that contain r such that the subperm of pi in these`): print(`places reduces to the reduction of the appropriate prefix of p (of the same length)`): print(`For example, try:`): print(`Scenarios([1,3,2],{[1,2,3]},2,{});`): elif nargs=1 and args[1]=redu then print(`redu(L): Given a word on a set of positive integers finds its reduced form`): elif nargs=1 and args[1]=IsBad1 then print(`IsBad1(perm1,pat1): does the word perm1 contain the pattern pat1?`): print(`For example, try:`): print(`IsBad1([4,1,3,2,6,5],[1,2,3]);`): elif nargs=1 and args[1]=IsBad then print(`IsBad(perm1,Patterns): Inputs a word perm1 and a set of Patterns, outputs true if perm1 contains`): print(`(at least one) pattern in Patterns and false otherwise`): print(`For example try:`): print(`IsBad([1,2,3,4],{[1,2,3],[1,3,2]});`): elif nargs=1 and args[1]=IsRevDel1GapF then print(`IsRevDel1GapF(Patterns,pi,r,G): Is the r^th entry of the prefix permutation pi reversely deletable`): print(`for the Wilf class of forbidden patterns Patterns?`): print(`For example, try:`): print(`IsRevDel1GapF({[1,2,3]},[2,1],1,{[0,1,1]});`): elif nargs=1 and args[1]=SetRevDelGapF then print(`SetRevDelGapF(Patterns,pi,G): Using the Fast way, finds the set of reversely deleteable`): print(`entries for the Wilf class avoiding Patterns for the prefix permutation pi and set of gap vectors G.`): print(`For example, try:`): print(`SetRevDelGapF({[1,2,3]},[1,2,2],{[0,0,0,1]});`): elif nargs=1 and args[1]=Yeladim then print(`Yeladim(pi): all the children of pi`): print(`for example, try Yeladim([1,2]);`): elif nargs=1 and args[1]=Append1 then print(`Append1(pi,i): appends i to the end of the word pi`): elif nargs=1 and args[1]=GaBchildrenF then print(`GaBchildrenF(Patterns,GvulGap,pi): the good and bad children`): print(`of a prefix permutation pi w.r.t. to the set of`): print(`patterns Patterns, with gap vectors of sum<=GvulGap`): print(`For example, try:`): print(`GaBchildrenF({[1,2,3]},1,[1]);`): elif nargs=1 and args[1]=Scheme1F then print(`Scheme1F(Gvul,Patterns): Tries to find a scheme`): print(`of depth<=Gvul `): print(`for the Wilf class avoiding`): print(`the patterns in Patterns using empirical investigations`): print(`if it fails it returns FAIL, followed by the partial`): print(`scheme and the leftovers. For example, try:`): print(`Scheme1F(2,{[1,2,3]});`): elif nargs=1 and args[1]=SchemeF then print(`SchemeF(Patterns,Gvul): Finds a scheme for the Wilf class`): print(`of restricted words avoiding the set of patterns`): print(`Patterns, of depth<=Gvul `): print(`by calling Scheme1F for different values of Gvul,`): print(`then checks the candidate scheme against empirical data. If it fails it returns`): print(`FAIL followed by the partial scheme of depth Gvul`): print(`followed by those prefix permutations that are not`): print(`reducible (that have yet to be explored).`): print(`For example, try:`): print(`SchemeF({[1,2,3]},2,2);`): elif nargs=1 and args[1]=testSF then print(`testSF(S,P): inputs a scheme S and a set of patterns P`): print(`and compares the sequence given by the scheme to empirical`): print(`data. returns true if the scheme agrees, and throws an ERROR`): print(`if the scheme and the data do not match`): print(`for example, try:`): print(`testSF(SchemeF({[1,2,3]},2,2),{[1,2,3]});`): elif nargs=1 and args[1]=MiklosA then print(`MiklosA(S,pre,a): Given a scheme S, a prefix pre`): print(`and an alphabet vector a, returns the number of words with alphabet`): print(`vector a, and prefix pre obeying scheme S`): print(`MiklosA(SchemeF({[1,2,3]},2,2),[],[1,1,1]);`): elif nargs=1 and args[1]=redusch then print(`redusch(pre,a): inputs a prefix pre and an alphabet vector a`): print(`and removes all possible 0s from a, reducing pre and a accordingly.`): print(`for example, try:`): print(`redusch([1,3],[2,0,1]);`): elif nargs=1 and args[1]=DeleteEntriesA then print(`DeleteEntriesA(pi,S): inputs a prefix pi, and a set S`): print(`and returns the prefix obtained by deleting max(S)`): print(`for example try DeleteEntriesA([1,3,2,2],{1,2});`): elif nargs=1 and args[1]=MiklosA2 then print(`MiklosA2(S,pi,v,a): Given a scheme S, and a prefix permutation`): print(`pi (that is part of the scheme) and a vector v of non-negative`): print(`integers v (of size nops(pi)+1) and an alphabet vector a, outputs the number`): print(`of words with alphabet vector a whose prefix reduces to pi and has`): print(`the gap-vector v. For example try:`): print(`MiklosA2(SchemeF({[1,2,3]},2,2),[],[2],[2,0,1]);`): elif nargs=1 and args[1]=DeleteEntriesGAl then print(`DeleteEntriesGAl(pi,v,pos,a): inputs a gap vector v and a set`): print(`of reversibly deleteable positions pos, and removes max(pos) from v`): print(`returns this new v along with a. (not used in SeqS11 or MiklosA)`): print(`for example, try: `): print(`DeleteEntriesGAl([1,1],[3,0,1],{1,2},[2,2,2]);`): elif nargs=1 and args[1]=chgapsAl then print(`chgapsAl(newpi, oldv,a): inputs a prefix newpi, and a gapvector old v for`): print(`the first n-1 entries of newpi, and an alphabet vector a.`): print(`returns an adjusted gap vector v, and a reduced alphabet vector a`): print(`(is not called by SeqS11 or Miklos A)`): print(`for example try:`): print(`chgapsAl([1,2,3],[1,1,1],[1,3,1,1]);`): elif nargs=1 and args[1]=isgoodvAl then print(`isgoodvAl(v1,newpi,a,i3): inputs a gap vector v1, a prefix permutation newpi,`): print(`an alphabet vector a, and a position i3`): print(`returns true if v1 implies a prefix that reduces to newpi and a[i3]>0, and false o.w.`): print(`for example, try isgoodv([0,2,1],[1,1],[1,1,1,1],3); or isgoodv([0,2,1],[1,2],[1,1,1,1],3);`): elif nargs=1 and args[1]=DeleteEntriesAl then print(`DeleteEntriesAl(pi,S): inputs a prefix pi, and a set S`): print(`and returns the reduced prefix obtained by deleting max(S)`): print(`for example try DeleteEntriesAl([1,3,2,2],{1,2});`): elif nargs=1 and args[1]=SeqS11 then print(`SeqS11(S,r,n): inputs a scheme S, and positive integers r and n.`): print(`returns a sequences following the scheme of the number of words with alphabet vectors`): print(`[r$i], i=1..n`): print(`for example try SeqS11(SchemeF({[1,2,3]},2,2),1,7);`): print(`or SeqS11(SchemeF({[1,2,3]},2,2),2,7);`): elif nargs=1 and args[1]=mWilf then print(`mWilf(a,P): the set of words avoiding P with alphabet vector a.`): print(`for example try:`): print(`mWilf([1,2,1],{[1,2,3]});`): elif nargs=1 and args[1]=isgood then print(`isgood(P,q): given permutations P, returns true if q avoids every permutation in P, otherwise returns false`): elif nargs=1 and args[1]=parts then print(`parts(k,n): the partitions of n into k parts`): elif nargs=1 and args[1]=MiklosTot then print(`MiklosTot(S,k,n): the total number of words obeying S in [k]^n`): elif nargs=1 and args[1]=SeqSkn then print(`SeqSkn(S,k,n): given an alphabet of size k, returns the number of`): print(`words obeying S of length i, for i=1..n`): else print(`Sorry, there is no help for `, args): fi: end: with(combinat): ############################## #functions for sipur ############################## #AllPatternSets1(L): Given a set of positive integers #finds the sets of permutations with the specified #lengths, for example, try: #AllPatternSets1([3,3]) AllPatternSets1:=proc(La) local L1,gu1,gu2,i1,i2,gu,Gu,i,L: L:=sort(La): if nops(L)=1 then gu1:=convert(permute(L[1]),set): gu1:={seq({gu1[i1]},i1=1..nops(gu1))}: RETURN(gu1): fi: L1:=[op(1..nops(L)-1,L)]: gu1:=AllPatternSets1(L1): gu2:=AllPatternSets1([L[nops(L)]]): gu:={}: for i1 from 1 to nops(gu1) do for i2 from 1 to nops(gu2) do if not IsBad(gu2[i2][1],gu1[i1]) then gu:=gu union {{op(gu1[i1]),op(gu2[i2])}}: fi: od: od: Gu:={}: for i from 1 to nops(gu) do if nops(gu[i])=nops(L) then Gu:=Gu union {gu[i]}: fi: od: Gu: end: #AllPatternSets(L): Given a set of positive integers #finds all the equilance classes (under trivial Wilf-equivalence) #of sets of permutations with the specified #lengths, for example, try: #AllPatternSets([3,3]) AllPatternSets:=proc(L) local gu,Gu,evar: gu:=AllPatternSets1(L): Gu:={}: while gu<>{} do evar:=gu[1]: Gu:=Gu union {KHAVERIM(evar)}: gu:=gu minus KHAVERIM(evar): od: Gu: end: SipurF:=proc(L,Gvul,r,Nlist) local gu,S,F,sch,i,ka,mu,mu1,j: if r<>nops(Nlist) then ERROR(`Nlist must have same length as r`): fi: gu:=AllPatternSets(L); print(`There all together`, nops(gu), `different equivalence classes `): S:={}: F:={}: for i from 1 to nops(gu) do sch:=SchemeImageF(gu[i][1],Gvul): if sch<>FAIL then print(`For the equivalence class of patterns`, gu[i]): mu:=sch[2]: ka:=max(seq(nops(mu[i][1]),i=1..nops(mu))): print(`the member `, sch[1], `has a scheme of depth `, ka): print(`here it is: `): print(mu): for j from 1 to r do print(`Using the scheme, the first, `, Nlist[j], `terms for `, j, ` copies of each letter are `): mu1:=SeqS11(mu,j,Nlist[j]): print(mu1): od: S:=S union {gu[i]}: else F:=F union {gu[i]}: fi: od: print(`Out of a total of `, nops(gu), `cases `): print(nops(S), `were successful and `, nops(F) , `failed `): print(`Success Rate: `, evalf(nops(S)/nops(gu),3) ): print(`Here are the failures `): print(F): F: end: compl:=proc(perm) local k,i: k:=max(op(perm))+1: [seq(k-perm[i],i=1..nops(perm))]: end: COMPL:=proc(Perms) local i,gu: gu:={}: for i from 1 to nops(Perms) do gu:=gu union{compl(op(i,Perms))}: od: gu: end: #revers(perm): The reverse of a permutation revers:=proc(perm) local i: [seq(perm[nops(perm)-i+1],i=1..nops(perm))]: end: #REVERS(Perms): The set of reverses of a set of permutations #Perms REVERS:=proc(Perms) local i,gu: gu:={}: for i from 1 to nops(Perms) do gu:=gu union{revers(op(i,Perms))}: od: gu: end: #KHAVERIM(Perms): Given a set of patterns Perms, outputs #all the images under the trivial-Wilf-equivalence group #For example, try: KHAVERIM({[1,2,3]}); KHAVERIM:=proc(Perms): {Perms, REVERS(Perms),COMPL(Perms), REVERS(COMPL(Perms)),COMPL(REVERS(Perms)), COMPL(REVERS(COMPL(Perms))), REVERS(COMPL(REVERS(Perms))), COMPL(REVERS(COMPL(REVERS(Perms))))}: end: #SchemeImageF(Patterns,Gvul): tries to find a scheme #for an equivalent set of patterns SchemeImageF:=proc(Patterns,GVUL) local mu,S,i: mu:=KHAVERIM(Patterns): for i from 1 to nops(mu) do S:=SchemeF(mu[i],GVUL): if S[1]<>FAIL then RETURN([mu[i],S]): fi: od: FAIL: end: ####################### # proc to find gaps ####################### #GapVectorsF(Patterns,pi,s): Given #a set of patterns Patterns and a prefix permutation #pi (of size k, say) and a positive integer s #finds all gap vectors of size <=s , in the Fast way. #For example, try: GapVectorsF({[1,2,3]},[1,2],1); GapVectorsF:=proc(Patterns,pi,s) local G,s1: G:={}: for s1 from 0 to s do G:=G union NewGapVectorsF(Patterns,pi,s1,G): od: G: end: #NewGapVectorsF(Patterns,pi,s,G): Given #a set of patterns Patterns and a prefix permutation #pi (of size k, say) and a positive integer s #and a set of previously found gap vectors G #finds all new gap vectors of size s , in the Fast way. #For example, try: NewGapVectorsF({[1,2,3]},[1,2],1,{}); NewGapVectorsF:=proc(Patterns,pi,s,G) local gu,mu,g,mu2,i: mu:=Comps(s,nops(pi)+1) minus ImpliedGaps(G,s): #print(mu): mu2:={}: for i from 1 to nops(mu) do if isreallyv(mu[i],pi) then mu2:=mu2 union {mu[i]}: fi: od: mu:=mu2: #print(mu): gu:={}: for g in mu do if PGV(g,pi,Patterns) then gu:=gu union {g}: fi: od: gu: end: isreallyv:=proc(v,p) local i,pvec,vvec,p2: if nops(p)=1 and nops(v)=2 then return true: fi: p2:=sort(p): pvec:=[seq(p2[i+1]-p2[i],i=1..nops(p2)-1)]: vvec:=[op(2..nops(v)-1,v)]: evalb({seq(evalb(vvec[i]>=pvec[i]),i=1..nops(vvec))}={true}): end: #ImpliedGaps1(g,s): given a gap vector g, and a positive #integer s, finds the set of all vectors of non-negative #integers of the same size as g and that add up to #to s that are implied by g #For example, try: #ImpliedGaps1([1,1],3); ImpliedGaps1:=proc(g,s) local gu,n,g1: n:=nops(g): gu:=Comps(s-convert(g,`+`) ,n): {seq(Khaber(g1,g), g1 in gu)}: end: #ImpliedGaps(G,s): given a set of gap vectors G, and a positive #integer s, finds the set of all vectors of non-negative #integers of the same size as g and that add up to #to s that are implied by g in G #For example, try: #ImpliedGaps({[1,1],[0,2]},4); ImpliedGaps:=proc(G,s) local g: {seq(op(ImpliedGaps1(g,s)),g in G)}: end: #Comps(a,n): the set of vectors of non-negative integers #of length n that add up to a. For example, try: #Comps(4,3); Comps:=proc(a,n) local gu,i,j,mu: option remember: if n=0 then if a=0 then RETURN({[]}): else RETURN({}): fi: fi: gu:={}: for i from 0 to a do mu:=Comps(a-i,n-1): gu:=gu union {seq([op(mu[j]),i],j=1..nops(mu))}: od: gu: end: #checks if PGV is a gap vector for pi avoiding Patterns PGV:=proc(g,pi,Patterns) local i,k,curr,lu,p2: k:=nops(pi): p2:=sort(pi): if nops(g)<>k+1 then ERROR(`bad input`): fi: #gap must be one longer than permutation lu:=[seq(j/(g[1]+1),j=1..g[1])]: curr:=1: #print(lu,curr): if nops(p2)>1 then p2:=[op(2..nops(p2),p2)]: else p2:=[]: fi: #correct number of things before the 1 #print(p2): for i from 2 to nops(g)-1 do #print(lu,curr,p2,i,g[i]): if g[i]=0 then lu:=[op(lu),curr]: elif g[i]=1 then lu:=[op(lu),curr+1]: curr:=curr+1: else lu:=[op(lu),seq(curr+j/(g[i]+1),j=1..g[i]-1),curr+1]: curr:=curr+1: fi: if nops(p2)>0 and lu[nops(lu)]=p2[1] then p2:=[op(2..nops(p2),p2)]: lu:=[op(1..nops(lu)-1,lu)]: fi: od: #if nops(p2)>0 and lu[nops(lu)]=p2[1] then p2:=[op(2..nops(p2),p2)]: lu:=[op(1..nops(lu)-1,lu)]: fi: lu:=[op(lu),seq(curr+j/(g[nops(g)]),j=1..g[nops(g)])]: #print(lu): lu:=permute(lu): #print(lu): lu:=[seq([op(pi),op(lu[i])],i=1..nops(lu))]: #print(lu): evalb({seq(IsBad(lu[i],Patterns),i=1..nops(lu))}={true}): end: #sum of vectors u and v Khaber:=proc(u,v) local i:[seq(u[i]+v[i],i=1..nops(u))]:end: ####################### # proc to find rd elts ####################### #returns true if even positions are all 0 or 1 isgoodvec:=proc(v) local i: for i from 1 to nops(v)/2 do if v[2*i]>1 then return false: fi: od: true: end: #returns all possible vectors of length l with sum of entries n PossVecs:=proc(n,l) local S,i,gu,T,S2: option remember: if l<0 then ERROR("bad input in PossVecs"): fi: S:={}: S2:={}: if l=1 then return {[n]}: fi: if l=0 then return {[]}: fi: for i from 0 to n do gu:=PossVecs(n-i,l-1): S:=S union {seq([op(T),i],T in gu)}: od: for i from 1 to nops(S) do if isgoodvec(S[i]) then S2:=S2 union {S[i]}: fi: od: S2: end: #given prefix pi, permutation p, and scenario s, returns all possible ways the scenario s #can extend to pi SubScen:=proc(pi,p,s,Gaps) local pi1,i,p1,v1,v2,p2,v,pv,poss2,co,pe,co1,j,gu,S,gu2,gu3,k,poss,L,cand,piend: pi1:=[seq(pi[i],i in {op(s)})]: p1:=sort([op(1..nops(s),p)]): #p2:=[op(nops(s)+1..nops(p),p)]: p2:=p: #print(p1,p2): co:=0: for i from 1 to nops(p2) do if p2[i]p1[i] and (i=nops(p1) or p2[j]k-1 then co:=co+1: fi: od: if v1[k]=0 and k>1 and k=g[j]),j=1..nops(v))}={true} then return false: fi: od: true: end: #Scenarios1(pi,p,r,Gaps): Given a prefix permutation pi, #a pattern p, and a place r (1 between 1 and nops(pi)) #and a set of gap-vectors #outputs all the subests of {1, ..., nops(pi)} #that contain r such that the subperm of pi in these #places reduces to the reduction of the appropriate #prefix of p (of the same length) #For example, try: #Scenarios1([2,1],[1,2,3],1,{}); Scenarios1:=proc(pi,p,r,Gaps) local s,S,i,k,s1,gu,T,mu,mu1,m: if r<1 or r>nops(pi) then ERROR(`Bad input`): fi: k:=nops(pi): T:={seq(i,i=1..k)} minus {r}: S:={seq(op(choose(T,i)),i=0..nops(p)-2)}: S:={seq(s union {r}, s in S)}: #S is all the ways that r can be in a sequence of length up to nops(p)-1. gu:={}: for s in S do s1:=sort(convert(s,list)): if redu([seq(pi[s1[i]],i=1..nops(s1))])= redu([op(1..nops(s1),p)]) then gu:=gu union {s1}: fi: od: gu: #print(gu): #gu is the list of positions of permutation prefixes that position r could be involved in mu:={}: for s1 in gu do mu1:=SubScenarios1(pi,p,s1,Gaps): mu:= mu union {seq([s1,m],m in mu1)}: od: mu: end: SubScenarios1:=proc(pi,p,s1,Gaps) local gu,i,poss: gu:=SubScen(pi,p,s1,Gaps): poss:={}: #print(gu,Gaps): for i from 1 to nops(gu) do #if obeysG(gu[i],Gaps) then poss:=poss union {gu[i]}: #fi: od: poss: end: roundv:=proc(v) local i: [seq(ceil(v[i]),i=1..nops(v))]: end: #Scenarios(pi,P,r,Gaps): Given a prefix permutation pi, #a set of patterns P, and a place r (1 between 1 and nops(pi)) #and a set of gap-vectors Gaps, #outputs all pairs [p,S] where p #is in P and S is a set of assignements to the #pattern p relative to the elements of pi arising #from secnarios that contain r such that the subperm of pi in these #places reduces to the reduction of the appropriate #prefix of p (of the same length) #For example, try: #Scenarios([2,1],{[1,2,3]},1,{}); Scenarios:=proc(pi,P,r,Gaps) local gu,mu,m,p: gu:={}: for p in P do mu:=Scenarios1(pi,p,r,Gaps): gu:=gu union {seq([p,m],m in mu)}: od: gu: end: #redu(L): Given a word on a set of positive integers #finds its reduced form redu:=proc(L) local sp,i,ra,L2: sp:=sort([op({op(L)})]): for i from 1 to nops(sp) do ra[sp[i]]:=i: od: L2:=[]: for i from 1 to nops(L) do L2:=[op(L2),ra[L[i]]]: od: L2: end: #IsBad1(perm1,pat1): does the permutation perm1 contain the #pattern pat1? #For example, try: #IsBad1([4,1,3,2,6,5],[1,2,3]); IsBad1:=proc(perm1,pat1) local gu,subperm,v,i1: gu:=choose(nops(perm1),nops(pat1)): for v in gu do subperm:=[seq(perm1[v[i1]],i1=1..nops(v))]: if redu(subperm)=pat1 then RETURN(true): fi: od: false: end: #IsBad(perm1,Patterns): Inputs a permutation perm1 and #a set of Patterns, outputs true if perm1 contains #(at least one) pattern in Patterns and false otherwise #For example try: #IsBad([1,2,3,4],{[1,2,3]}); IsBad:=proc(perm1,Patterns) local pat1: for pat1 in Patterns do if IsBad1(perm1,pat1) then RETURN(true): fi: od: false: end: #IsRevDel1GapF(Patterns,pi,r,G): Is the r^th entry of the #prefix permutation pi reversely deletable #for the Wilf class of forbidden patterns Patterns #For example, try: #IsRevDel1GapF({[1,2,3]},[2,1],1,{[0,1]}); IsRevDel1GapF:=proc(P,pi,r,G) local gu,i,p,gu1,mu1,j1, Overlap,beyakhad: gu:=Scenarios(pi,P,r,G): #print(gu): for i from 1 to nops(gu) do gu1:=gu[i]: p:=gu1[1]: Overlap:=nops(gu1[2][1]): mu1:=gu1[2][2]: #print(Overlap): beyakhad:=[op(1..r-1,pi),op(r+1..nops(pi),pi), seq(mu1[p[j1]],j1=Overlap+1..nops(p))]: #print(beyakhad): if not IsBad(beyakhad,P) then RETURN(false): fi: od: true: end: #SetRevDelGapF(Patterns,pi,G): #Using the Fast way, the set of reversely deleteable #entries for the Wilf class avooding Patterns for the #prefix permutation pi and set of gap vectors G. For example, try: #SetRevDelGapF({[1,2,3]},[1,2],{[0,0,1]}); SetRevDelGapF:=proc(Patterns,pi,G) local gu,r: gu:={}: for r from 1 to nops(pi) do if IsRevDel1GapF(Patterns,pi,r,G) then gu:=gu union {r}: fi: od: gu: end: ######################### # proc to find rd scheme ######################### #Yeladim(pi): all the children of pi Yeladim:=proc(pi) local i: [op({seq(redu(2*Append1(pi,i/2)),i=0..2*(nops(pi)+1))})]:end: Append1:=proc(pi,i): [op(pi),i] end: #GaBchildrenF(Patterns,GvulGap,pi): the good and bad children #of a prefix permutation pi w.r.t. to the set of #patterns Patterns, with gap vectors of sum<=GvulGap #For example, try: #GaBchildrenF({[1,2,3]},1,[1]): GaBchildrenF:=proc(Patterns,GvulGap,pi) local gu,G,B,pi1,Gaps1,rd1: gu:=Yeladim(pi): G:={}: B:={}: for pi1 in gu do Gaps1:=GapVectorsF(Patterns,pi1,GvulGap): rd1:=SetRevDelGapF(Patterns,pi1,Gaps1): if rd1<>{} then G:=G union {[pi1,Gaps1,rd1]}: else B:=B union {[pi1,Gaps1,rd1]}: fi: od: G,B: end: #Scheme1F(Gvul,Patterns): Tries to find a scheme #of depth<=Gvul and with gap-vectors of sum<=GvulGap #for the Wilf class avoiding #the patterns in Patterns using empirical investigations #if it fails it returns FAIL, followed by the partial #scheme and the leftovers. For example, try: #Scheme1F(2,1,{[1,2,3]}); Scheme1F:=proc(Gvul,Patterns) local LeftToDo,S,pi,j,i,gu,GvulGap: LeftToDo:={[]}: S:=[[[],{},{}]]: for i from 0 to Gvul while LeftToDo<>{} do for pi in LeftToDo do GvulGap:=max(0,seq(nops(Patterns[i]),i=1..nops(Patterns)))+nops(pi)-1: gu:=GaBchildrenF(Patterns,GvulGap,pi) : S:=[op(S), op(gu[1]),op(gu[2])]: LeftToDo:=LeftToDo minus {pi} union {seq(gu[2][j][1],j=1..nops(gu[2]))}: od: if LeftToDo={} then # S:=SimplifyScheme(S): # if Bdok(S) then RETURN(S): # else # print(`Not closed under deletion`): # RETURN(FAIL,S): # fi: fi: od: FAIL,S,LeftToDo: end: #SchemeF(Patterns,Gvul): Finds a scheme for the Wilf class #of restricted words avoiding the set of patterns #Patterns, of depth<=Gvul and with gap vectors #of sum <=GvulGap . If it fails it retunrs #FAIL followed by the partial scheme of depth Gvul #followed by those prefix permutations that are not #reducible (that have yet to be explored). #For example, try: #SchemeF({[1,2,3]},2,1); SchemeF:=proc(Patterns,Gvul) local gu,Gvul1,i: for i from 1 to nops(Patterns) do if nops({op(Patterns[i])})<>nops(Patterns[i]) then ERROR(`Patterns should not have repeated letters`): fi: od: for Gvul1 from 0 to Gvul-1 do gu:=Scheme1F(Gvul1,Patterns): # if nops([gu])=1 and testSF(gu,Patterns) then if nops([gu])=1 then RETURN(gu): fi: od: gu: end: testSF:=proc(S,P) local s1,s2,s3,s4: if S[1]=FAIL then return FAIL: fi: s1:=SeqS11(S,1,6): s2:=[seq(nops(mWilf([1$i],P)),i=1..6)]: if s1<>s2 then ERROR("The predicted sequence and the actual sequence do not agree"): fi: s3:=SeqS11(S,2,4): s4:=[seq(nops(mWilf([2$i],P)),i=1..4)]: if s3<>s4 then ERROR("The predicted sequence and the actual sequence do not agree"): false: fi: true: end: ################################################## # begin functions for computing alphabet sequence ################################################## #MiklosA(S,pre,a): Given a scheme S, a prefix pre #and an alphabet vector a, returns the number of words with alphabet #vector a, and prefix pre obeying scheme S #MiklosA(Scheme({[1,2,3]},2),[],a); MiklosA:=proc(S,pre,a) local pi, v, lu, i, GapVectors, g, su, pi1, pre2, ca: option remember: #print(pre,a): #if max(op(pre))[pre,a] then RETURN(MiklosA(S,ca[1],ca[2])): fi: fi: pi:=redu(pre): if nops(pre)>0 then pre2:=sort(pre): v:=[pre2[1]-1, seq(pre2[i+1]-pre2[i],i=1..nops(pre2)-1),nops(a)-pre2[nops(pre2)]]: else v:=[nops(a)-1]: fi: #print("input was ", pre,a,pi,v): lu:=isopre(S,pre): #print("lu is ", lu): #gap vectors is the forbidden gapvectors for prefix pi GapVectors:=lu[2]: #print(v): if nops(lu[1])=g[j]),j=1..nops(v))}={true} then RETURN(0): fi: od: #print("survived gap vectors"): if a=[0$nops(a)] then RETURN(1): fi: if lu[3]<>{} then pi1:=DeleteEntriesA(pre,lu[3]): #print("r.v. elts are ", lu[3], " so return MiklosA of ", pi1, a): RETURN(MiklosA(S,pi1,a)): fi: #print("no r.v.s so going to add"): su:=0: for i from 1 to nops(a) do if a[i]>0 then #print("in loop, add ", [op(pre),i],[op(1..i-1,a),a[i]-1,op(i+1..nops(a),a)]): su:=su+MiklosA(S,[op(pre),i],[op(1..i-1,a),a[i]-1,op(i+1..nops(a),a)]): fi: od: su: end: redusch:=proc(pre,a) local pre1, a1,i,j: option remember: pre1:=pre: a1:=a: for i from 1 to nops(a) do if a[i]=0 and not member(i,{op(pre1)}) then for j from 1 to nops(pre1) do if pre1[j]>i then pre1[j]:=pre1[j]-1: fi: od: RETURN(redusch(pre1,[op(1..i-1,a1),op(i+1..nops(a1),a1)])): fi: od: pre,a: end: #DeleteEntriesA(pi,S): inputs a prefix pi, and a set S #and returns the prefix obtained by deleting max(S) #for example try DeleteEntriesA([1,3,2,2],{1,2}); DeleteEntriesA:=proc(pi,S) local i, pi1, S1: if S={} then return(pi): fi: i:=max(op(S)): if i>nops(pi) then print("S has entries bigger than the size of pi"): return(FAIL): fi: pi1:=[op(1..i-1,pi),op(i+1..nops(pi),pi)]: end: isopre:=proc(S,pre) local pi, i, pre1: pi:=redu(pre): #isolate prefix pi in the scheme, call it lu for i from 1 to nops(S) do if S[i][1]=pi then RETURN(S[i]): fi: od: pre1:=[op(1..nops(pre)-1,pre)]: RETURN(isopre(S,pre1)): end: ############################### # an attempt at being quicker! ############################### #MiklosA2(S,pi,v): Given a scheme S, and a prefix permutation #pi (that is part of the scheme) and a vector v of non-negative #integers v (of size nops(pi)+1) outputs the number #of words of length n #with at least one copy of each letterwhose prefix reduces to pi and has #the gap-vector v. For example try: #MiklosA2(Scheme({[1,2,3]},2),[],[2],3); MiklosA2:=proc(S,pi,v,a) local i,lu,GapVectors,g,pi1,v1,su,j,L1,ch,vS, pi2, pos,L,a1: option remember: if a[nops(a)]=0 and v[nops(v)]>0 then v1:=[op(1..nops(v)-1,v),v[nops(v)]-1]: a1:=[op(1..nops(a)-1,a)]: RETURN(MiklosA2(S,pi,v1,a1)): fi: #print("input: ",pi,v,a): if convert(v, `+`)+1<>nops(a) then ERROR(`Bad input: v and a imply different alphabet sizes`): fi: if nops(pi)+1<>nops(v) then ERROR(`Bad input: the third argument should be one longer than the sec.`): fi: #isolate prefix pi in the scheme, call it lu for i from 1 to nops(S) do if S[i][1]=pi then lu:=S[i]: break: fi: od: #FAIL if prefix is not in scheme if i=nops(S)+1 then RETURN(FAIL): fi: #gap vectors is the forbidden gapvectors for prefix pi GapVectors:=lu[2]: #if v is bigger than one of the forbidden gaps, return 0 for g in GapVectors do if {seq(evalb(v[j]>=g[j]),j=1..nops(v))}={true} then RETURN(0): fi: od: #if v is all 0s, then only the empty word is good, return 1 if v=[0$nops(v)] or a=[0$nops(a)] then RETURN(1): fi: #if there are reversibly deletable entries, delete them if lu[3]<>{} then #print("option 1, delete"): pi1:=DeleteEntriesAl(pi,lu[3]): #pi1 is the reduced prefix permutation after deleting the rv elts pi2:=[op(sort(pi)),0]; L:=[op(lu[3])]: pos:={}: for i from 1 to nops(L) do for j from 1 to nops(pi2) do if pi2[j]=pi[L[i]] and pi2[j+1]<>pi[L[i]] then pos:=pos union {j}: fi: od: od: #print("input ", pi, v, pos, a): #pos is the positions of the gap to remove v1:=DeleteEntriesGAl(pi,v,pos,a): #print("returned from deleting entires, input", pi, v, pi2, pos, "output", pi1, v1): #print("enter ", pi1, v1): RETURN(add(MiklosA2(S,pi1,v1[i][1],a),i=1..nops(v1))): fi: su:=0: ch:=Yeladim(pi): #if there are not reversibly deletable entries, then expand for i from 1 to nops(ch) do #print("option 2, expand"): pi1:=ch[i]: vS:=chgapsAl(ch[i],v,a): for j from 1 to nops(vS) do su:=su+MiklosA2(S,pi1,vS[j][1],vS[j][2]): od: od: su: end: #DeleteEntriesGAl(pi,v,pos,a): inputs a gap vector v and a set #of reversibly deleteable positions, and removes max(pos) from v #for example try DeleteEntriesG([1,0,1],{1,2}); DeleteEntriesGAl:=proc(pi,v,pos,a) local i, v1, pos1, v2, S1, S2a,S2b,a1g,a2g,S,a1,a2: if pos={} then return {a}: fi: S1:={seq(1+add(v[i],i=1..j),j=1..nops(v)-1)}: i:=max(op(pos)): v1:=[op(1..i-1, v), v[i]+v[i+1], op(i+2..nops(v),v)]: if i<>1 and v[i]=0 then v2:=v1: else v2:=[op(1..i-1, v), v[i]+v[i+1]-1, op(i+2..nops(v),v)]: fi: S2a:={seq(1+add(v1[i],i=1..j),j=1..nops(v1)-1)}: S2b:={seq(1+add(v2[i],i=1..j),j=1..nops(v2)-1)}: a1g:=true: a2g:=true: S:={[v1,a]}: #if a[nops(a)]=0 then a2:=[op(1..nops(a)-1,a)]: #S:=S union {[v2,a2]}: #fi: S: end: chgapsAl:=proc(newpi, oldv,a) local S, oldpi, k,j, rep,L,i,i2,v1,a1,i3: #print("input ", newpi, oldv, a): oldpi:=redu([op(1..nops(newpi)-1, newpi)]): if member(newpi[nops(newpi)], {op(1..nops(newpi)-1,newpi)}) then rep:=true: else rep:=false: fi: #rep tells if the added letter is a repeated letter. if so, then we just add a 0 #in the vector S:={}: #print(rep): if rep then L:=sort(newpi): for i from 1 to nops(L) do if L[i]=newpi[nops(newpi)] then v1:=[op(1..i,oldv), 0, op(i+1..nops(oldv),oldv)]: i3:=1+convert(op(1..i,oldv),`+`): #print(v1,i3): if a[i3]>0 then a1:=a: #print(a1): a1[i3]:=a1[i3]-1: #print(a1): S:=S union {[v1,a1]}: fi: RETURN(S): fi: od: fi: #if not rep, then split v[i] into 2 smaller numbers L:=sort(newpi): for i from 1 to nops(L) do if L[i]=newpi[nops(newpi)] then i2:=i: i:=nops(L): fi: od: #print(L, i2): for j from 0 to oldv[i2] do v1:=[op(1..i2-1,oldv),j,oldv[i2]-j,op(i2+1..nops(oldv),oldv)]: #print(oldv, v1): i3:={seq(1+add(v1[i],i=1..j),j=1..nops(v1)-1)} minus {seq(1+add(oldv[i],i=1..j),j=1..nops(oldv)-1)}: #print(i3): if nops(i3)>0 and isgoodvAl(v1,newpi,a,i3[1]) then a1:=a: a1[i3[1]]:=a1[i3[1]]-1: S:=S union {[v1,a1]}: fi: od: S: end: #isgoodvAl(v1,newpi,a): inputs a gap vector v1, and a prefix permutation newpi #returns true if v1 implies a prefix that reduces to newpi, and false o.w. #for example, try isgoodv([0,2,1],[1,1]); or isgoodv([0,2,1],[1,2]); isgoodvAl:=proc(v1,newpi,a,i3) local i: if redu([seq(1+convert([op(1..i,v1)],`+`),i=1..nops(v1)-1)])=sort(newpi) and a[i3]>0 then return true: fi: false: end: #DeleteEntriesAl(pi,S): inputs a prefix pi, and a set S #and returns the reduced prefix obtained by deleting max(S) #for example try DeleteEntries([1,3,2,2],{1,2}); DeleteEntriesAl:=proc(pi,S) local i, pi1, S1: if S={} then return(pi): fi: i:=max(op(S)): if i>nops(pi) then print("S has entries bigger than the size of pi"): return(FAIL): fi: pi1:=[op(1..i-1,pi),op(i+1..nops(pi),pi)]: redu(pi1): end: SeqS11:=proc(S,r,n) local i: [seq(MiklosA(S,[],[r$i]),i=1..n)]: end: mWilf:=proc(a,P) local k,k2,i,rP,n,a2,S,S2,a3,j,m,S3: option remember: rP:={}: #the set of reduced patterns to avoid for i from 1 to nops(P) do rP:=rP union {redu(P[i])}: od: k:=nops(a): #the number of letters in alphabet a2:={}: # the set of letters than appear in the word k2:=0: #the number of distinct letters that appear in the word for i from 1 to k do if a[i]>0 then k2:=k2+1: a2:=a2 union {i}: fi: od: n:=convert(a,`+`); #the number of letters in word #print(rP,k,k2,n,a2): if n=0 then return {[]}: fi: S:={}: #the set of good words for i from 1 to nops(a2) do a3:=[]: for j from 1 to k do if j<>a2[i] then a3:=[op(a3),a[j]]: else a3:=[op(a3),a[j]-1]: fi: od: #now a3 is the list reduced by a2[i] S2:=mWilf(a3,P): S3:={}: for m from 1 to nops(S2) do S3:=S3 union {[op(S2[m]),a2[i]]}: od: for m from 1 to nops(S3) do if isgood(P,S3[m]) then S:=S union {S3[m]}: fi: od: od: S: end: #given permutations P, returns true if q avoids every permutation in P, otherwise returns false isgood:=proc(P,q) local pos, k, j, l,w,m,i,mP: k:=nops(q): mP:=min(seq(nops(P[i]),i=1..nops(P))): if mP>k then return(true): fi: for j from 1 to nops(P) do pos:=choose([seq(i,i=1..k-1)],nops(P[j])-1): for l from 1 to nops(pos) do #w is the word made up of q[pos[l]] w:=[]: for m from 1 to nops(pos[l]) do w:=[op(w),q[pos[l][m]]]: od: w:=[op(w),q[nops(q)]]: if evalb(redu(w)=redu(P[j])) then return false: fi: od: od: true: end: ######################################## # functions to count ALL words in [k]^n # obeying a scheme ######################################## #parts(k,n): the partitions of n into k parts parts:=proc(k,n) local i, S2, S: if k=1 then return {[n]}: fi: S:={}: for i from 0 to n do S2:=parts(k-1,n-i): S:=S union {seq([i,op(S2[j])],j=1..nops(S2))}: od: S: end: #MiklosTot(S,k,n): the total number of words obeying S #in [k]^n MiklosTot:=proc(S, k, n) local P,a: P:=parts(k,n): add(MiklosA(S,[],a),a in P): end: #SeqSkn(S,k,n): given an alphabet of size k, returns the number of #words obeying S of length i, for i=1..n SeqSkn:=proc(S,k,n) local i: [seq(MiklosTot(S,k,i),i=1..n)]: end: