###################################################################### ##VATTER: Save this file as VATTER. To use it, stay in the # ##same directory, get into Maple (by typing: maple ) # ##and then type: read VATTER : # ##Then follow the instructions given there # ## # ##Written by Doron Zeilberger, Rutgers University , # #zeilberg at math dot rutgers dot edu # ####################################################################### #Created: Aug. 2006-Dec. 2006 print(`Created: Aug. 2006. Revised: Dec. 2006.`): print(`This is VATTER, a Maple package`): print(`to enumerate Wilf classes of permutations,`): print(`using Zeilberger's version of Vince VATTER's brilliant extension`): print(`(used in Vatter's Maple WILFPLUS package)`): print(`of Zeilberger's original notion of Enumeration Schemes`): print(`(used in Zeilberger's Maple package WILF) . `): print(`It tries to discover Enumeration Schemes RIGOROUSLY and efficiently.`): print(`It accompanies Doron Zeilberger's article: `): print(`On Vince Vatter's Brilliant Extension of Doron Zeilberger's`): print(`Enumeration Schemes for Counting Pattern-Avoiding Permutations.`): print(`This Maple package, as well as the article, are `): print(`available from:`): print(` http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/vatter.html `): lprint(``): print(`Please report bugs to zeilberg at math dot rutgers dot edu`): lprint(``): print(`For a list of the procedures type ezra(), for help with`): print(`a specific procedure, type ezra(procedure_name)`): print(``): with(combinat): ezra1:=proc() if args=NULL then print(` The supporting procedurs are: AllPatternSets, Analyze1`): print(`Comps, CompsAd,GaBchildren, GapVectors, GapVectorsF `): print(` IsIBdeedScheme, IsRevDel1, IsRevDel1Gap, Miklos `): print(` PD1, PD1set, ProveGapVector, RestrictedComps, RestrictedCompsGaps`): print(` Scenarios, Scenarios1 `): print(`Scheme1, SchemeImage, SchemeSlow,SetRevDel, SetRevDelGap,SetRevDelGapF`): print(` Sipur, SubScenarios1, UnfortunateEvents, UpperSchemeF, Wilf, WilfPre `): else ezra(args): fi: end: ezra:=proc() if args=NULL then print(`The main procedures are: `): print(` SchemeFast, SeqS, SipurF, SchemeImageFast `): elif nops([args])=1 and op(1,[args])=AllPatternSets then print(`AllPatternSets(L): Given a set 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 nops([args])=1 and op(1,[args])=Analyze1 then print(`Analyze1(L,n,N,x,mekhir): `): print(`analyzes a sequence L that comes from enumeration`): print(`of permutations`): elif nops([args])=1 and op(1,[args])=Comps then print(`Comps(a,n): the set of vectors of non-negative integers`): print(`of length n that add up to a. For example, try:`): print(`Comps(4,3);`): elif nops([args])=1 and op(1,[args])=CompsAd then print(`CompsAd(a,n): the set of vectors of non-negative integers`): print(`of length n that add up to <=a. For example, try:`): print(`CompsAd(4,3);`): elif nops([args])=1 and op(1,[args])=Findrec then print(`Findrec(f,n,N,MaxC): Given a list f tries to `): print(`find a linear recurrence equation with`): print(` poly coffs. of maximum DEGREE+ORDER<=MaxC`): print(`e.g. try Findrec([1,1,2,3,5,8,13,21,34,55,89],n,N,2);`): elif nops([args])=1 and op(1,[args])=GaBchildren then print(`GaBchildren(n0,Patterns,pi): the good and bad children`): print(`of a prefix permutation pi w.r.t. to the set of`): print(`patterns Patterns, using empirical investigations of`): print(`permutations up to size n0. For example, try:`): print(`GaBchildren(7,{[1,2,3]},[1]):`): elif nops([args])=1 and op(1,[args])=GapVectors then print(`GapVectors(n0,Patterns,pi): Given an integer n0 and`): print(`a set of patterns Patterns and a prefix permutation`): print(`pi (of size k, say)`): print(`finds all the gap vectors by investigating permutation`): print(`up to length n0`): print(`For example, try: GapVectors(7,{[1,2,3]},[1,2]);`): elif nops([args])=1 and op(1,[args])=GapVectorsF then print(`GapVectorsF(Patterns,pi,s): Given `): print(` a set of patterns Patterns and a prefix permutation `): print(` pi (of size k, say) and a positive integer s `): print(`finds all the (minimal) gap vectors of size<=s , in the Fast way.`): print(`For example, try: GapVectorsF({[1,2,3]},[1,2],3);`): elif nops([args])=1 and op(1,[args])=IsIndeedScheme then print(`IsIndeedScheme(n0,Patterns,S):checks whether the scheme S`): print(`is OK for example, try:`): print(`IsIndeedScheme(7,{[1,2,3,4]},Scheme({[1,2,3,4]},4));`): elif nops([args])=1 and op(1,[args])=IsRevDel1 then print(`IsRevDel1(n0,Patterns,pi,r): Is the r^th entry of the`): print(`prefix permutation pi reversely deletable `): print(` for the Wilf class Wilf(i,Patterns)?, i<=n0 `): print(` For example, try: `): print(` IsRevDel1(6,{[1,2,3]},[2,1],1); `): elif nops([args])=1 and op(1,[args])=IsRevDel1Gap then print(`IsRevDel1Gap(n0,Patterns,pi,r,G): Is the r^th entry of the`): print(`prefix permutation pi reversely deletable`): print(`for the Wilf class Wilf(i,Patterns) , i<=n0 `): print(`satisying the gap condition`): print(`given by the set of gap vectors G?`): print(`For example, try:`): print(`IsRevDel1Gap(6,{[1,2,3]},[1,2],1,{[0,1,0]});`): elif nops([args])=1 and op(1,[args])=IsRevDel11GapSet then print(`IsRevDel11GapSet(n0,Patterns,pi,S,G): Are the entries of S`): print(`for the prefix permutation pi reversely deletable`): print(`for the Wilf class Wilf(n0,Patterns) satisying the gap condition`): print(`given by the set of gap vectors G? `): print(`For example, try:`): print(`IsRevDel11GapSet(6,{[1,2,3]},[1,2],{1},{[0,1,0]});`): elif nops([args])=1 and op(1,[args])=Miklos then print(`Miklos(S,pi,v): 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) outputs the number`): print(`of permutations whose prefix reduces to pi and has`): print(`the gap-vector v. For example try:`): print(`Miklos(SchemeFast({[1,2,3]},2,2),[],[5]);`): elif nops([args])=1 and op(1,[args])=PD1 then print(`PD1(n,Patterns,pi,v,r): The "partial derivative" of`): print(`WilfPre(n,Patterns,pi,v) w.r.t. to the r^th entry`): print(`of pi, i.e.`): print(`WilfPre(n-1,Patterns,redu(pi w/o pi[r]), redu(v,w/o v[pi[r]]))`): print(`minus the image of WilfPre(n,Patterns,pi,v) under the map`): print(`delete the r^th entry and reduce`): print(`For example, try:`): print(`PD1(5,{[1,2,3]},[2,1],[4,5],2);`): elif nops([args])=1 and op(1,[args])=PD1set then print(`PD1set(n,Patterns,pi,v,r): The "partial derivative" of`): print(`WilfPre(n,Patterns,pi,v) w.r.t. to the entries of S`): print(`For example, try:`): print(`PD1set(5,{[1,2,3]},[2,1],[4,5],{2});`): elif nops([args])=1 and op(1,[args])=ProveGapVector then print(`ProveGapVector(g,pi,Patterns):: Given a gap vector g`): print(`a prefix permutation pi, and a set of patterns Patterns`): print(`proves that it is indeed a gap vector`): print(`For example try: ProveGapVector([0,0,1],[1,2],{[1,2,3]});`): elif nops([args])=1 and op(1,[args])=RestrictedComps then print(`RestrictedComps(K,S,B): Given a positive integer K,`): print(`an increasing sequence of integers S from [1, ..., K]`): print(`and a vector B of non-negative integers of length`): print(`nops(S)+1, returns all vectors v of length K`): print(`with the property that if S=[i_1,i_2, ..., i_s]`): print(`then v[1]+...+v[i_1]=B[1]`): print(`v[i_1+1]+...+v[i2]=B[2]`): print(`...`): print(`v[i_s+1]+ ...+ v[K]=B[s+1]`): print(`For example, try:`): print(`RestrictedComps(4,[2],[3,3]);`): elif nops([args])=1 and op(1,[args])=RestrictedCompsGaps then print(`RestrictedCompsGaps(K,S,B,Gaps): Given a positive integer K,`): print(`an increasing sequence of integers S from [1, ..., K]`): print(`and a vector B of non-negative integers of length`): print(`nops(S)+1, and a set of gap-vectors Gaps`): print(`returns all vectors v of length K, that are not implied by Gaps`): print(`with the property that if S=[i_1,i_2, ..., i_s]`): print(`then v[1]+...+v[i_1]=B[1]`): print(`v[i_1+1]+...+v[i2]=B[2]`): print(`...`): print(`v[i_s+1]+ ...+ v[K]=B[s+1]`): print(`For example, try:`): print(`RestrictedCompsGaps(4,[2],[3,3],{});`): elif nops([args])=1 and op(1,[args])=Scenarios then print(`Scenarios(pi,P,r,Gaps): Given a prefix permutation pi,`): print(`a set of patterns P, and a place r (1 between 1 and nops(pi)) `): print(`and a set of gap vectors Gaps,`): print(`outputs all pairs [p,S] where p`): print(`is in P and S is a subest of {1, ..., nops(pi)}`): print(`that contain r such that the subperm of pi in these`): print(`places reduces to the reduction of the appropriate`): print(`prefix of p (of the same length)`): print(`For example, try:`): print(`Scenarios([2,1],{[1,2,3]},1,{});`): elif nops([args])=1 and op(1,[args])=Scenarios1 then print(`Scenarios1(pi,p,r,Gaps): Given a prefix permutation pi,`): print(`a pattern p, and a place r (1 between 1 and nops(pi)) `): print(`and a set of gap vectors, Gaps`): print(`outputs all relative placements of the memebers of p`): print(`relative to the members of pi consistent with a bad`): print(`event featuring p `): print(`that contain r such that the subperm of pi in these`): print(`places reduces to the reduction of the appropriate`): print(`prefix of p (of the same length)`): print(`For example, try:`): print(`Scenarios1([2,1],[1,2,3],1,{});`): elif nops([args])=1 and op(1,[args])=SchemeSlow then print(`SchemeSlow(Patterns,Gvul): Using the Empirical, Slow approach, finds a scheme for the Wilf class`): print(`of restricted permutations avoiding the set of patterns`): print(`Patterns, of depth<=Gvul. If it fails it retunrs`): 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(`SchemeSlow({[1,2,3]},2);`): elif nops([args])=1 and op(1,[args])=SchemeFast then print(`SchemeFast(Patterns,Gvul,GvulGap): Tries `): print(`to find an Enumeration Scheme for counting the Wilf class`): print(`of restricted permutations avoiding the set of patterns`): print(`Patterns, of depth<=Gvul, and size (some of entries) of`): print(`gap vectors <=GvulGap .`): print(`It uses the, fast version. If it fails it retunrs`): 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(`SchemeFast({[1,2,3]},2,1);`): elif nops([args])=1 and op(1,[args])=Scheme1 then print(`Scheme1(n0,Gvul,Patterns): Tries to find a scheme`): print(`of depth<=Gvul for the Wilf class avoiding`): print(`the patterns in Patterns using empirical investigations`): print(`of perms of length<=n0. `): print(`if it fails it returns FAIL, followed by the partial`): print(`scheme and the leftovers. For example, try:`): print(`Scheme1(6,2,{[1,2,3]});`): elif nops([args])=1 and op(1,[args])=SchemeImage then print(`SchemeImage(Patterns, GVUL): tries to find a scheme`): print(`for an equivalent set of patterns of Patterns`): print(`of depth <=GVUL `): print(`For example, try: SchemeImage({[1,2,3]},2);`); elif nops([args])=1 and op(1,[args])=SchemeImageFast then print(`SchemeImageFast(Patterns, GVUL,GvulGap): tries to find a scheme`): print(`for an equivalent set of patterns of Patterns`): print(`of depth <=GVUL and max. sum of gap-vectors GvulGap`): print(`using the fast way.`): print(`For example, try: SchemeImageFast({[1,2,3]},2,1);`); elif nops([args])=1 and op(1,[args])=SeqS then print(`SeqS(S,K): The first K+1 terms generated`): print(`by the enumeration scheme S.`): print(`For example try:`): print(`SeqS(SchemeFast({[1,2,3]},2,1),20);`): elif nops([args])=1 and op(1,[args])=SetRevDel then print(`SetRevDel(n0,Patterns,pi): the set of reversely deleteable`): print(`entries for the Wilf class Wilf(n0,Patterns) for the`): print(`prefix permutation pi. For example, try:`): print(`SetRevDel(6,{[1,2,3]},[1,2]);`): elif nops([args])=1 and op(1,[args])=SetRevDelGap then print(`SetRevDelGap(n0,Patterns,pi,S): the set of places`): print(`of the prefix permutation pi that are reversely deletable`): print(`for the Wilf class Wilf(n0,Patterns) satisying the gap condition`): print(`given by the set of gap vectors G`): print(`For example, try:`): print(`SetRevDelGap(6,{[1,2,3]},[1,2],{[0,0,1]});`): elif nops([args])=1 and op(1,[args])=SetRevDelGapF then print(`SetRevDelGapF(Patterns,pi,S): Using the fast way,`): print(`the set of places`): print(`of the prefix permutation pi that are reversely deletable`): print(`for the Wilf class avoiding Patterns satisying the gap condition`): print(`given by the set of gap vectors G`): print(`For example, try:`): print(`SetRevDelGapF({[1,2,3]},[1,2],{[0,0,1]});`): elif nops([args])=1 and op(1,[args])=Sipur then print(`Sipur(L,Gvul,K): Everything you ever wanted to know`): print(`about all patterns of type L, that schemes of depth <=Gvul`): print(`and printing out, in the successful cases, the first K+1`): print(`terms. For example, try:`): print(`Sipur([3],2,20);`): elif nops([args])=1 and op(1,[args])=SipurF then print(`SipurF(L,Gvul,GvulGap,K1,K2,n,N,x,Savlanut,mekhir): `): print(`Given a list of positive integers L, it tries to find`): print(`an enumeration scheme of depth<=Gvul and max. size (sum of entries)`): print(`of gap vectors <=GvulGap, for ALL sets of patterns with nops(L) `): print(`elements, of lengths L[1],L[2], ..., L[nops(L)].`): print(` It also prints out, if found, conjectured annihilting`): print(`operators (in terms of n and N), conjectured rational generating`): print(`funtions (in x) and conjectured`): print(`explciit expressions as a polynomial in n`): print(`for the enumerationg sequences.`): print(`Note: It uses the FAST way.`): print(`Also, in the successful cases, it prints out the first K1+1 terms`): print(`or K2+1 terms,`): print(`depending whether the depth of the scheme is <=Savlanut or`): print(`not , respectively.`): print(``): print(`mekhir is a parameter for the recurrence guessing. For now`): print(`just set it equal to 2, always. `): print(``): print(`For example, try:`): print(`SipurF([3],2,1,10,20,n,N,x,3,2);`): elif nops([args])=1 and op(1,[args])=SubScenarios1 then print(`SubScenarios1(pi,p,s1,Gaps): Given a prefix permutation pi,`): print(`a pattern p, and a scenario s1 `): print(`and a (possibly empty) set of gap-vectors, Gaps`): print(`such that the subperm of pi in these`): print(`places reduces to the reduction of the appropriate`): print(`prefix of p (of the same length)`): print(`outputs the possible ways ALL the members of p`): print(`can be placed relative to the members of the pi`): print(`subject to the conditions imposed by Gaps`): print(`For example, try:`): print(`SubScenarios1([2,1],[1,2,3],[1],{});`): elif nops([args])=1 and op(1,[args])=UnfortunateEvents then print(`UnfortunateEvents(pi,p,r): Given a prefix permutation pi,`): print(`a pattern p, and a place r (1 between 1 and nops(pi)) `): print(`outputs all the subests of {1, ..., nops(pi)}`): print(`that contain r such that the subperm of pi in these`): print(`places reduces to the reduction of the appropriate`): print(`prefix of p (of the same length)`): print(`For example, try:`): print(`UnfortunateEvents([2,1],[1,2,3],1);`): elif nops([args])=1 and op(1,[args])=UpperSchemeF then print(`UpperSchemeF(Patterns,Gvul,GvulGap): Finds a scheme for the`): print(` Wilf class` ): print(`of restricted permutations avoiding the set of patterns`): print(`Patterns, of depth<=Gvul and with gap vectors`): print(`of sum <=GvulGap . If it fails it retunrs`): 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(`UpperSchemeF({[1,2,3,4]},3,2);`): elif nops([args])=1 and op(1,[args])=Wilf then print(`Wilf(n,Patterns): all permutations of length n`): print(`that avoid the patterns in the set of patterns`): print(` Patterns. For example, try: `): print(`Wilf(5,{[1,2,3],[1,3,2]});` ): elif nops([args])=1 and op(1,[args])=WilfPre then print(`WilfPre(n,Patterns,pi,v): The set of members of Wilf(n,Patterns)`): print(`whose first nops(pi) members reduce to pi and whose elements are`): print(`v (v is increasing). For example, try:`): print(`WilfPre(5,{[1,2,3]},[2,1],[4,5]);`): else print(`There is no ezra for`,args): fi: end: ######################### #Append1(pi,i): Given a permutation pi, and an integer #i between 1 and nops(pi)+1, constructs the permutation #of length nops(pi)+1 whose last entry is i, and such that #reduced form of the first nops(pi) letters is pi #For example, try: Append1([2,1,3],2); Append1:=proc(pi,i): redu([op(pi),i-1/2]): end: #redu(perm): Given a permutation on a set of positive integers #finds its reduced form redu:=proc(perm) local gu,i,ra: gu:=sort(perm): for i from 1 to nops(gu) do ra[gu[i]]:=i: od: [seq(ra[perm[i]],i=1..nops(perm))]: end: #good11(pi,pattern1) #Given a permutation pi, and a pattern pattern1, decides whether #pattern1 occurs in pi with the first and last letter of pi coinciding #with the last letter of pattern1. It returns 0 if this is #the case, otherwise 1 (0 means bad) good11:=proc(pi,pattern1) local gu,k,n,j,subperm,vec: if pi=pattern1 then RETURN(false): fi: n:=nops(pi): k:=nops(pattern1): if k>n then RETURN(true): fi: gu:=IV1(n,k-2): for vec in gu do subperm:=[pi[1],seq(pi[vec[j]],j=1..k-2),pi[n]]: if redu(subperm)=pattern1 then RETURN(false): fi: od: true: end: #IV1(n,k) all increasing vectors of length #k of the form 1<=i_1< ...nops(v) or sort(v)<>v then print(`Bad output`): RETURN(FAIL): fi: T:=WilfTable(n,Patterns,nops(pi)) : T[pi,v]: end: #Delete1(v,r): deleting the r^th entry of the permutation v #and reducing #For example, try: Delete1([1,4,2,3],2); Delete1:=proc(v,r): redu([op(1..r-1,v),op(r+1..nops(v),v)]):end: #DeleteSet1(S,r): deletes the r^th entry and reduces from #each of the permutations in S #For example, try: DeleteSet1({[1,4,2,3]},2); DeleteSet1:=proc(S,r) local i: {seq(Delete1(S[i],r),i=1..nops(S))}: end: #PD1(n,Patterns,pi,v,r): The "partial derivative" of #WilfPre(n,Patterns,pi,v) w.r.t. to the r^th entry #of pi, i.e. #WilfPre(n-1,Patterns,redu(pi w/o pi[r]), redu(v,w/o v[pi[r]])) #minus the image of WilfPre(n,Patterns,pi,v) under the map #delete the r^th entry and reduce #For example, try: #PD1(5,{[1,2,3]},[2,1],[4,5],2); PD1:=proc(n,Patterns,pi,v,r) local gu,gu1,pi1,v1,i: gu:=WilfPre(n,Patterns,pi,v): gu:=DeleteSet1(gu,r): pi1:=redu([op(1..r-1,pi),op(r+1..nops(pi),pi)]): v1:=[op(1..pi[r]-1,v),seq(v[i]-1,i=pi[r]+1..nops(v))]: gu1:=WilfPre(n-1,Patterns,pi1,v1): gu1 minus gu: end: #IsRevDel11(n0,Patterns,pi,r): Is the r^th entry of the #prefix permutation pi reversely deletable #for the Wilf class Wilf(n0,Patterns)? #For example, try: #IsRevDel11(6,{[1,2,3]},[2,1],1); IsRevDel11:=proc(n0,Patterns,pi,r) local gu,v: gu:=IV1(n0,nops(pi)): evalb({seq(evalb(PD1(n0,Patterns,pi,v,r)={}),v in gu)}={true}): end: #IsRevDel1(n0,Patterns,pi,r): Is the r^th entry of the #prefix permutation pi reversely deletable #for the Wilf class Wilf(i,Patterns), i<=n0? #For example, try: #IsRevDel1(6,{[1,2,3]},[2,1],1); IsRevDel1:=proc(n0,Patterns,pi,r) local i: evalb({seq(IsRevDel11(i,Patterns,pi,r),i=nops(pi)..n0)}={true}): end: #IV1Gap(n,k,G): the subset of IV1(n,k) of vectors v #satisfying v[1]-0>=G[1]+1, v[2]-v[1]>=G[2]+1 , ... #v[k]-v[k-1]>=G[k]+1, n+1-v[k]>=G[k+1]+1 #For example, try:IV1Gap(5,3,[1,0,0]); IV1Gap:=proc(n,k,G) local mu,i,v: mu:=IV1(n-convert(G,`+`),k): {seq([seq(v[i]+convert([op(1..i,G)],`+`),i=1..nops(v))],v in mu)}: end: #IV1GapC(n,k,S): all the vectors v of IV1(n,k) that #do NOT satisfy v[1]-0>=G[1]+1, v[2]-v[1]>=G[2]+1 , ... #v[k]-v[k-1]>=G[k]+1, n+1-v[k]>=G[k+1]+1 #for each G in S IV1GapC:=proc(n,k,S) local G: IV1(n,k) minus {seq(op(IV1Gap(n,k,G)),G in S)}:end: #IsRevDel11Gap(n0,Patterns,pi,r,G): Is the r^th entry of the #prefix permutation pi reversely deletable #for the Wilf class Wilf(n0,Patterns) satisying the gap condition #given by the set of gap vectors G? #For example, try: #IsRevDel11Gap(6,{[1,2,3]},[1,2],1,{[0,1]}); IsRevDel11Gap:=proc(n0,Patterns,pi,r,G) local gu,v,i: if G<>{} and {seq(nops(G[i])-nops(pi),i=1..nops(G))}<>{1} then ERROR(`Bad input`): fi: gu:=IV1GapC(n0,nops(pi),G): if gu={} then RETURN(true): fi: evalb({seq(evalb(PD1(n0,Patterns,pi,v,r)={}),v in gu)}={true}): end: #IsRevDel1Gap(n0,Patterns,pi,r,G): Is the r^th entry of the #prefix permutation pi reversely deletable #for the Wilf class Wilf(i,Patterns), i<=n0? #For example, try: #IsRevDel1Gap(6,{[1,2,3]},[2,1],1,{[0,1]}); IsRevDel1Gap:=proc(n0,Patterns,pi,r,G) local i: evalb({seq(IsRevDel11Gap(i,Patterns,pi,r,G),i=nops(pi)..n0)}={true}): end: hofkhi:=proc(pi) local i, T: for i from 1 to nops(pi) do T[pi[i]]:=i: od: [seq(T[i],i=1..nops(pi))]: end: Hofkhi:=proc(S) local i: {seq(hofkhi(S[i]),i=1..nops(S))}: end: #SetRevDel(n0,Patterns,pi): the set of reversely deleteable #entries for the Wilf class Wilf(n0,Patterns) for the #prefix permutation pi. For example, try: #SetRevDel(6,{[1,2,3]},[1,2]); SetRevDel:=proc(n0,Patterns,pi) local gu,r: gu:={}: for r from 1 to nops(pi) do if IsRevDel1(n0,Patterns,pi,r) then gu:=gu union {r}: fi: od: gu: end: #SetRevDelGap(n0,Patterns,pi,G): the set of reversely deleteable #entries for the Wilf class Wilf(n0,Patterns) for the #prefix permutation pi and gap vector G. For example, try: #SetRevDelGap(6,{[1,2,3]},[1,2],{[0,0,1]); SetRevDelGap:=proc(n0,Patterns,pi,G) local gu,r: gu:={}: for r from 1 to nops(pi) do if IsRevDel1Gap(n0,Patterns,pi,r,G) then gu:=gu union {r}: fi: od: gu: end: #EmptiesD1(n0,Patterns,pi): Given an integer n0 and #a set of patterns Patterns and a prefix permutation #pi (of size k, say) #finds the differences #[v[1]-1,v[2]-v[1]-1, ..., v[k]-v[k-1]-1,n-v[k]] #for all vectors that for which WilfPre(n0,Patterns,pi,v) #is empty #For example, try: EmptiesD1(5,{[1,2,3]},[1,2]); EmptiesD1:=proc(n0,Patterns,pi) local mu,gu,k,v,i: option remember: if pi=[] then RETURN({}): fi: k:=nops(pi): mu:=IV1(n0,k): gu:={}: for v in mu do if WilfPre(n0,Patterns,pi,v)={} then gu:=gu union {[v[1]-1,seq(v[i]-v[i-1]-1,i=2..k),n0-v[k]]}: fi: od: gu: end: #NewEmptiesD(n0,Patterns,pi): Given an integer n0 and #a set of patterns Patterns and a prefix permutation #pi (of size k, say) #finds the differences #[v[1]-1,v[2]-v[1]-1, ..., v[k]-v[k-1]-1,n-v[k]] #for all vectors that for which WilfPre(n0,Patterns,pi,v) #is empty and that are not implied by gap vectors for smaller n #For example, try: NewEmptiesD(5,{[1,2,3]},[1,2]); NewEmptiesD:=proc(n0,Patterns,pi) local gu1,gu2,v,i: option remember: gu1:=EmptiesD1(n0-1,Patterns,pi): gu1:={seq(seq([op(1..i-1,v),v[i]+1,op(i+1..nops(v),v)], i=1..nops(v)),v in gu1)}: gu2:=EmptiesD1(n0,Patterns,pi): if gu1 minus gu2<>{} then print(`something may be wrong`): fi: gu2 minus gu1: end: #GapVectors(n0,Patterns,pi): Given an integer n0 and #a set of patterns Patterns and a prefix permutation #pi (of size k, say) #finds all the gap vectors by investigating permutation #up to length n0 #For example, try: GapVectors(7,{[1,2,3]},[1,2]); GapVectors:=proc(n0,Patterns,pi) local i: {seq(op(NewEmptiesD(i,Patterns,pi)),i=1..n0)}: end: #Yeladim(pi): all the children of pi Yeladim:=proc(pi) local i:[seq(Append1(pi,i),i=1..nops(pi)+1)]:end: #GaBchildren(n0,Patterns,pi): the good and bad children #of a prefix permutation pi w.r.t. to the set of #patterns Patterns, using empirical investigations of #permutations up to size n0. For example, try: #GaBchildren(7,{[1,2,3]},[1]): GaBchildren:=proc(n0,Patterns,pi) local gu,G,B,pi1,Gaps1,rd1: gu:=Yeladim(pi): G:={}: B:={}: for pi1 in gu do Gaps1:=GapVectors(n0,Patterns,pi1): rd1:=SetRevDelGap(n0,Patterns,pi1,Gaps1): if rd1<>{} then G:=G union {[pi1,Gaps1,rd1]}: else B:=B union {[pi1,Gaps1,rd1]}: fi: od: G,B: end: #DeleteEntries(pi,S): deletes all the entries of #pi[i] for i in S and reduces DeleteEntries:=proc(pi,S) local k,i,S1: k:=nops(pi): if S minus {seq(i,i=1..k)}<>{} then ERROR(`bad input`): fi: S1:= {seq(i,i=1..k)} minus S: S1:=sort(convert(S1,list)): redu([seq(pi[S1[i]],i=1..nops(S1))]): end: #Bdok(S): checks whether the tentative scheme S is OK Bdok:=proc(S) local Expa,Redu,i,pi,pi1: Expa:={}; Redu:={}: for i from 1 to nops(S) do if S[i][3]={} then Expa:=Expa union {S[i][1]}: else Redu:=Redu union {S[i][1]}: fi: od: for i from 1 to nops(S) do pi:=S[i][1]: if S[i][3]={} then if {op(Yeladim(pi))} minus (Redu union Expa)<>{} then print(pi, `does not have all its children in the scheme`): RETURN(false): fi: else pi1:=DeleteEntries(pi,S[i][3]): if not member(pi1, Expa union Redu) then print(`the reduction of`, pi, `which is`, pi1, `does not belong`): RETURN(false): fi: fi: od: true: end: #SimplifyScheme(S): simplifies the scheme S #to avoid, if necessary, the third component with cardinality larger #than 1 SimplifyScheme:=proc(S) local Prefs,i,S1,ku,j: Prefs:={seq(S[i][1],i=1..nops(S))}: S1:={}: for i from 1 to nops(S) do ku:=S[i][3]: if nops(ku)<2 then S1:=S1 union {S[i]}: else for j from 1 to nops(ku) do if member(DeleteEntries( S[i][1],{ku[j]}),Prefs) then S1:=S1 union {[S[i][1],S[i][2],{ku[j]}]} : break: fi: od: if j=nops(ku)+1 then S1:=S1 union {S[i]}: fi: fi: od: S1: end: #Scheme1(n0,Gvul,Patterns): Tries to find a scheme #of depth<=Gvul for the Wilf class avoiding #the patterns in Patterns using empirical investigations #of perms of length<=n0. #if it fails it returns FAIL, followed by the partial #scheme and the leftovers. For example, try: #Scheme1(6,2,{[1,2,3]}); Scheme1:=proc(n0,Gvul,Patterns) local LeftToDo,S,pi,j,i,gu: LeftToDo:={[]}: S:=[[[],{},{}]]: for i from 0 to Gvul while LeftToDo<>{} do for pi in LeftToDo do gu:=GaBchildren(n0,Patterns,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 IsIndeedScheme(n0,Patterns,S) then RETURN(S): else print(`Not closed under deletion`): RETURN(FAIL,S): fi: fi: od: FAIL,S,LeftToDo: end: Hex:=proc(): {[3,2,1],hofkhi([4,6,7,1,8,2,3,5]),hofkhi([4,6,7,8,1,2,3,5]), hofkhi([5,6,7,1,8,2,3,4]),hofkhi([5,6,7,8,1,2,3,4])}:end: ####Starts Sipur #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: #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: INVERSE:=proc(Perms) local i:{seq(hofkhi(Perms[i]),i=1..nops(Perms))}: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),INVERSE(Perms), REVERS(INVERSE(Perms)),INVERSE(REVERS(Perms)), INVERSE(REVERS(INVERSE(Perms))), REVERS(INVERSE(REVERS(Perms))), INVERSE(REVERS(INVERSE(REVERS(Perms))))}: end: #SchemeImage(Patterns,Gvul): tries to find a scheme #for an equivalent set of patterns SchemeImage:=proc(Patterns,GVUL) local mu,S,i: mu:=KHAVERIM(Patterns): for i from 1 to nops(mu) do S:=SchemeSlow(mu[i],GVUL): if S[1]<>FAIL then RETURN([mu[i],S]): fi: od: FAIL: end: #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: #Sipur(L,Gvul,K): Everything you ever wanted to know #about all patterns of type L, that schemes of depth <=Gvul #and printing out, in the successful cases, the first K+1 #terms. For example, try: #Sipur([3],2,20); Sipur:=proc(L,Gvul,K) local gu,S,F,sch,i,ka,mu: gu:=AllPatternSets(L); print(`There all together`, nops(gu), `different equivalence classes `): S:={}: F:={}: for i from 1 to nops(gu) do sch:=SchemeImage(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): print(`Using the scheme, the first, `, K+1, `terms are `): print(SeqS(mu,K)): 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: #SipurF(L,Gvul,GvulGap,K1,K2,n,N,x,Savlanut,mekhir): #Everything you ever wanted to know #about all patterns of type L, that schemes of depth <=Gvul #and max. sum of gap-vector GvulGap, #and printing out, in the successful cases, the first K1+1 #(or K2+1, depending whether the depth is <=Savlanut or not ) #terms. It also print out, if found, conjectured annihilting #operators (in terms of n and N), conjectured rational generating #funtions (in x) and explciit expressions as a polynomial in n #mekhir is a positive integer indicating how desperate you are to #sarcrifice degree for order # For example, try: #SipurF([3],2,1,20,n,N,x,3,3); SipurF:=proc(L,Gvul,GvulGap,K1,K2,n,N,x,Savlanut,mekhir) local gu,S,F,sch,i,ka,mu,mu1: gu:=AllPatternSets(L); print(`There all together`, nops(gu), `different equivalence classes `): S:={}: F:={}: for i from 1 to nops(gu) do sch:=SchemeImageFast(gu[i][1],Gvul,GvulGap): 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): if ka>Savlanut then print(`Using the scheme, the first, `, K1+1, `terms are `): mu1:=SeqS(mu,K1): print(mu1): S:=S union {gu[i]}: else print(`Using the scheme, the first, `, K2+1, `terms are `): mu1:=SeqS(mu,K2): print(mu1): Analyze1(mu1,n,N,x,mekhir): S:=S union {gu[i]}: fi: 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: ####Ends Sipur #Shrink1(v,S): Given a vector v and a list S from {1, ..., nops(v)-1} #returns the vector obtained by removing the barriers from the #fences of S #For example,try: Shrink1([4,1,5],[1]); Shrink1:=proc(v,S) local i,k,v1,S1,i1: k:=nops(v)-1: if not type(v,list) or not type(S,list) or convert(S,set) minus {seq(i,i=1..k)}<>{} then ERROR(`bad input`): fi: i:=S[1]: v1:=[op(1..i-1,v),v[i]+v[i+1],op(i+2..nops(v),v)]: if nops(S)=1 then v1: else S1:=[seq(S[i1]-1,i1=2..nops(S))]: Shrink1(v1,S1): fi: end: #KickOut(pi,S): given a permutation pi and a set of indices S #deletes the entries in the places of S and reduces KickOut:=proc(pi,S) local i,S1,k: k:=nops(pi): if convert(S, set) minus {seq(i,i=1..k)}<>{} then ERROR(`Bad input`): fi: S1:={seq(i,i=1..nops(pi))} minus convert(S,set): S1:=sort(convert(S1,list)): redu([seq(pi[S1[i]],i=1..nops(S1))]): end: #DeleteEntriesV(v,S): given an increasing vector v and #a set S of entries, deletes the entries indexed by S #and reduces DeleteEntriesV:=proc(v,S) local r,v1,i,S1: if nops(S)=0 then RETURN(v): fi: S1:=sort(convert(S,list)): r:=S1[nops(S1)]: S1:=[op(1..nops(S1)-1,S1)]: v1:=[op(1..r-1,v),seq(v[i]-1,i=r+1..nops(v))]: DeleteEntriesV(v1,S1): end: DeleteEntriesSet:=proc(Setpi,S) local pi: {seq(DeleteEntries(pi,S),pi in Setpi)}: end: #PD1set(n,Patterns,pi,v,S): The "partial derivative" of #WilfPre(n,Patterns,pi,v) w.r.t. to the entries #of S, i.e. #WilfPre(n-nops(S),Patterns,redu(pi w/o S), redu(v,w/o v[pi[S]])) #minus the image of WilfPre(n,Patterns,pi,v) under the map #delete the entries of S and reduce #For example, try: #PD1set(5,{[1,2,3]},[2,1],[4,5],{2}); PD1set:=proc(n,Patterns,pi,v,S) local gu,gu1,pi1,v1,i,S1: gu:=WilfPre(n,Patterns,pi,v): gu:=DeleteEntriesSet(gu,S): pi1:=DeleteEntries(pi,S): S1:=[seq(pi[S[i]],i=1..nops(S))]: S1:=sort(S1): v1:=DeleteEntriesV(v,S1): gu1:=WilfPre(n-nops(S),Patterns,pi1,v1): gu1 minus gu: end: #IsRevDel11set(n0,Patterns,pi,S): are the entries of S in the #prefix permutation pi reversely deletable #for the Wilf class Wilf(n0,Patterns)? #For example, try: #IsRevDel11set(6,{[1,2,3]},[2,1],{1}); IsRevDel11set:=proc(n0,Patterns,pi,S) local gu,v: gu:=IV1(n0,nops(pi)): evalb({seq(evalb(PD1set(n0,Patterns,pi,v,S)={}),v in gu)}={true}): end: #IsRevDel1set(n0,Patterns,pi,S): are the entries of S in the #prefix permutation pi reversely deletable #for the Wilf class Wilf(i,Patterns), i<=n0? #For example, try: #IsRevDel1set(6,{[1,2,3]},[2,1],{1}); IsRevDel1set:=proc(n0,Patterns,pi,S) local i: evalb({seq(IsRevDel11set(i,Patterns,pi,S),i=nops(pi)..n0)}={true}): end: #IsRevDel11GapSet(n0,Patterns,pi,S,G): Are the entries of S #for the prefix permutation pi reversely deletable #for the Wilf class Wilf(n0,Patterns) satisying the gap condition #given by the set of gap vectors G? #For example, try: #IsRevDel11GapSet(6,{[1,2,3]},[1,2],{1},{[0,1]}); IsRevDel11GapSet:=proc(n0,Patterns,pi,S,G) local gu,v,i: if {seq(nops(G[i])-nops(pi),i=1..nops(G))}<>{1} then ERROR(`Bad input`): fi: gu:=IV1GapC(n0,nops(pi),G): if gu={} then RETURN(true): fi: evalb({seq(evalb(PD1set(n0,Patterns,pi,v,S)={}),v in gu)}={true}): end: #IsRevDel1GapSet(n0,Patterns,pi,S,G): Is the r^th entry of the #prefix permutation pi reversely deletable #for the Wilf class Wilf(i,Patterns), i<=n0? #For example, try: #IsRevDel1GapSet(6,{[1,2,3]},[2,1],{1},{[0,1]}); IsRevDel1GapSet:=proc(n0,Patterns,pi,S,G) local i: evalb({seq(IsRevDel11GapSet(i,Patterns,pi,S,G),i=nops(pi)..n0)}={true}): end: hofkhi:=proc(pi) local i, T: for i from 1 to nops(pi) do T[pi[i]]:=i: od: [seq(T[i],i=1..nops(pi))]: end: Hofkhi:=proc(S) local i: {seq(hofkhi(S[i]),i=1..nops(S))}: end: #IsIndeedScheme(n0,Patterns,S):checks whether the scheme S #is OK for example, try: #IsIndeedScheme(7,{[1,2,3,4]},SchemeSlow({[1,2,3,4]},7,3)); IsIndeedScheme:=proc(n0,Patterns,S) local i,S1,pi,G,RevD,G1: if not Bdok(S) then print(S, `is not a genuine scheme`): RETURN(false): fi: for i from 1 to nops(S) do S1:=S[i]: pi:=S1[1]: G:=S1[2]: RevD:=S1[3]: G1:=GapVectors(n0,Patterns,pi): if G<>G1 then print(G , `is not the set of gap-vectors for`, pi): RETURN(false): fi: if G={} then if not IsRevDel1set(n0,Patterns,pi,RevD) then print(RevD, ` is not reversely deletable for `, pi): RETURN(false): fi: else if not IsRevDel1GapSet(n0,Patterns,pi,RevD,G) then print(RevD, ` is not reversely deletable for `, pi): RETURN(false): fi: fi: od: if SeqS(S,n0)<>[seq(nops(Wilf(i,Patterns)),i=0..n0)] then print(`The predicted sequence and the actual sequence do not agree`): RETURN(false): fi: true: end: #DeleteEntriesG(g,S): shrinks the vector g by removing the #barriers in the places indicated by S #For example, try: DeleteEntries([2,3,2],{2}); DeleteEntriesG:=proc(g,S) local r,S1,g1,i: if S={} then RETURN(g): fi: r:=min(op(S)): g1:=[op(1..r-1,g),g[r]+g[r+1],op(r+2..nops(g),g)]: if nops(S)=1 then RETURN(g1): else S1:=S minus {r}: S1:={seq(S1[i]-1,i=1..nops(S1))}: RETURN(DeleteEntriesG(g1,S1)): fi: end: #Miklos(S,pi,v): Given a scheme S, and a prefix permutatil #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 permutations whose prefix reduces to pi and has #the gap-vector v. For example try: #Miklos(SchemeFast(6,2,{[1,2,3]}),[],[5]); Miklos:=proc(S,pi,v) local i,lu,GapVectors,g,pi1,v1,su,j,L1: option remember: if nops(pi)+1<>nops(v) then ERROR(`Bad input: the third argument should be one longer than the sec.`): fi: for i from 1 to nops(S) do if S[i][1]=pi then lu:=S[i]: break: fi: od: if i=nops(S)+1 then RETURN(FAIL): fi: GapVectors:=lu[2]: for g in GapVectors do if {seq(evalb(v[j]>=g[j]),j=1..nops(v))}={true} then RETURN(0): fi: od: if v=[0$nops(v)] then RETURN(1): fi: if lu[3]<>{} then pi1:=DeleteEntries(pi,lu[3]): L1:=sort(convert(lu[3],list)): L1:={seq(pi[L1[i]],i=1..nops(L1))}: v1:=DeleteEntriesG(v,L1): RETURN(Miklos(S,pi1,v1)): fi: su:=0: for i from 1 to nops(pi)+1 do pi1:=Append1(pi,i): for j from 0 to v[i]-1 do v1:=[op(1..i-1,v),j,v[i]-1-j,op(i+1..nops(v),v)]: su:=su+Miklos(S,pi1,v1): od: od: su: end: #SeqS(S,K): the first K+1 terms computed by the #enumeration scheme S, for example try: #SeqS(SchemeFast(6,2,{[1,2,3]}),20); SeqS:=proc(S,K) local i: [seq(Miklos(S,[],[i]) ,i=0..K)]:end: #SchemeSlow(Patterns,Gvul): Finds a scheme for the Wilf class #of restricted permutations avoiding the set of patterns #Patterns, of depth<=Gvul. 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: #SchemeSlow({[1,2,3]},2); SchemeSlow:=proc(Patterns,Gvul) local gu,Gvul1,godel,i: if Patterns<>{} then godel:=max(seq(nops(Patterns[i]),i=1..nops(Patterns))): else godel:=3: fi: for Gvul1 from 0 to Gvul-1 do gu:=Scheme1(godel+Gvul1,Gvul1,Patterns): if nops([gu])=1 then RETURN(gu): fi: od: gu: end: #ProveGapVector(g,pi,Patterns):: Given a gap vector g #a prefix permutation pi, and a set of patterns Patterns #proves that it is indeed a gap vector #For example try: ProveGapVector([0,0,1],[1,2],{[1,2,3]}); ProveGapVector:=proc(g,pi,Patterns) local lu,k,i,j: k:=nops(pi): if nops(g)<>k+1 then ERROR(`bad input`): fi: lu:={seq(seq(i-1+j/(g[i]+1),j=1..g[i]),i=1..nops(g))}: lu:=permute(lu): lu:=[seq([op(pi),op(lu[i])],i=1..nops(lu))]: evalb({seq(IsBad(lu[i],Patterns),i=1..nops(lu))}={true}): 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: #CompsAd(a,n): the set of vectors of non-negative integers #of length n that add up to <=a. For example, try: #CompsAd(4,3); CompsAd:=proc(a,n) local i: {seq(op(Comps(i,n)),i=0..a)}: end: Khaber:=proc(u,v) local i:[seq(u[i]+v[i],i=1..nops(u))]: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: #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: mu:=Comps(s,nops(pi)+1) minus ImpliedGaps(G,s): gu:={}: for g in mu do if ProveGapVector(g,pi,Patterns) then gu:=gu union {g}: fi: od: gu: end: #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: #UnfortunateEvents(pi,p,r): Given a prefix permutation pi, #a pattern p, and a place r (1 between 1 and nops(pi)) #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: #UnfortunateEvents([2,1],[1,2,3],1); UnfortunateEvents:=proc(pi,p,r) local s,S,i,k,s1,gu,T: 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)}: 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: 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 s1,gu,mu,mu1,m: gu:=UnfortunateEvents(pi,p,r): mu:={}: for s1 in gu do mu1:=SubScenarios1(pi,p,s1,Gaps): mu:= mu union {seq([s1,m],m in mu1)}: od: mu: 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: #RestrictedComps(k,S,B): Given a positive integer k, #an increasing sequence of integers S from [1, ..., k] #and a vector B of non-negative integers of length #nops(S)+1, returns all vectors v of length k+1 #with the property that if S=[i_1,i_2, ..., i_s] #then v[1]+...+v[i_1]=B[1] #v[i_1+1]+...+v[i2]=B[2] #... #v[i_s+1]+ ...+ v[k]=B[s+1] #For example, try: #RestrictedComps(4,[2],[3,3]); RestrictedComps:=proc(K,S,B) local S1,B1,b,gu1,gu2,K1,i1,i2: if nops(B)-nops(S)<>1 then ERROR(`Bad input`): fi: if S<>[] and S[nops(S)]>K then ERROR(`Bad input`): fi: if nops(S)=0 then RETURN(Comps(B[1],K)): fi: K1:=S[nops(S)]: S1:=[op(1..nops(S)-1,S)]: B1:=[op(1..nops(B)-1,B)]: gu1:=RestrictedComps(K1,S1,B1): b:=B[nops(B)]: gu2:=Comps(b,K-K1): {seq(seq([op(gu1[i1]),op(gu2[i2])],i2=1..nops(gu2)),i1=1..nops(gu1))}: end: #IsBigger1(v,g): is vector v point-wise bigger than #vector g. For example, try: IsBigger1([1,2],[2,4]); IsBigger1:=proc(v,g) local i: if nops(v)<>nops(g) then ERROR(`Bad input`): fi: evalb({seq(evalb(v[i]-g[i]>=0),i=1..nops(v))}={true}); end: #IsBigger(v,G): is v bigger than at least one of the vectors in G? IsBigger:=proc(v,G) local g: evalb(G<>{} and {seq(IsBigger1(v,g),g in G)}<>{false}): end: #RestrictedCompsGaps(k,S,B,Gaps): Given a positive integer k, #an increasing sequence of integers S from [1, ..., k] #and a vector B of non-negative integers of length #nops(S)+1, and a set of vectors Gaps #returns all vectors v of length k+1 #not implied by any the vectors in Gaps, #with the property that if S=[i_1,i_2, ..., i_s] #then v[1]+...+v[i_1]=B[1] #v[i_1+1]+...+v[i2]=B[2] #... #v[i_s+1]+ ...+ v[k]=B[s+1] #For example, try: #RestrictedComps(4,[2],[3,3],{}); RestrictedCompsGaps:=proc(K,S,B,Gaps) local mu,gu,v: gu:=RestrictedComps(K,S,B): mu:={}: for v in gu do if not IsBigger(v,Gaps) then mu:=mu union {v}: fi: od: mu: end: #SubScenarios1(pi,p,s1,Gaps): Given a prefix permutation pi, #a pattern p, and a scenario s1, #such that the subperm of pi in these #places reduces to the reduction of the appropriate #prefix of p (of the same length) #and a set of gap vectors Gaps #outputs the possible ways ALL the members of p #can be placed relative to the members of the pi #subject to the gap-conditions #For example, try: #SubScenarios1([2,1],[1,2,3],1,[1],{}); SubScenarios1:=proc(pi,p,s1,Gaps) local gu,pi1,p1,i,L1,T,gu1,lu,co,a,Gu,j: pi1:=[seq(pi[s1[i]],i=1..nops(s1))]: p1:=[op(1..nops(s1),p)]: if redu(pi1)<>redu(p1) then print(`Bad input`): RETURN(FAIL): fi: pi1:=sort(pi1): p1:=sort(p1): L1:=[p1[1]-1,seq(p1[i]-p1[i-1]-1,i=2..nops(p1)),nops(p)-p1[nops(p1)]]: lu:=[]: for i from 1 to nops(pi) do if member(i,convert(pi1,set)) then lu:=[op(lu),1]: else lu:=[op(lu),0]: fi: od: gu:=RestrictedCompsGaps(nops(pi)+1,pi1,L1,Gaps): Gu:={}: for a from 1 to nops(gu) do gu1:=gu[a]: co:=0: for i from 1 to nops(gu1) do for j from 1 to gu1[i] do co:=co+1: T[co]:=i-1+j/(gu1[i]+1): od: if i<=nops(lu) and lu[i]=1 then co:=co+1: T[co]:=i: fi: od: Gu:=Gu union {[seq(T[j],j=1..nops(p))]}: od: Gu: 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: #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): for i from 1 to nops(gu) do gu1:=gu[i]: p:=gu1[1]: Overlap:=nops(gu1[2][1]): mu1:=gu1[2][2]: beyakhad:=[op(1..r-1,pi),op(r+1..nops(pi),pi), seq(mu1[p[j1]],j1=Overlap+1..nops(p))]: if not IsBad(beyakhad,P) then RETURN(false): fi: od: true: 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,GvulGap,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,GvulGap,Patterns) local LeftToDo,S,pi,j,i,gu: LeftToDo:={[]}: S:=[[[],{},{}]]: for i from 0 to Gvul while LeftToDo<>{} do for pi in LeftToDo do 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: #SchemeFast(Patterns,Gvul,GvulGap): Finds a scheme for the Wilf class #of restricted permutations 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: #SchemeFast({[1,2,3]},2,1); SchemeFast:=proc(Patterns,Gvul,GvulGap) local gu,Gvul1,i: for Gvul1 from 0 to Gvul-1 do gu:=Scheme1F(Gvul1,GvulGap,Patterns): if nops([gu])=1 then RETURN(gu): fi: od: gu: end: #SchemeImageFast(Patterns,Gvul,GvulGap): tries to find a scheme #for an equivalent set of patterns SchemeImageFast:=proc(Patterns,GVUL,GvulGap) local mu,S,i: mu:=KHAVERIM(Patterns): for i from 1 to nops(mu) do S:=SchemeFast(mu[i],GVUL,GvulGap): if S[1]<>FAIL then RETURN([mu[i],S]): fi: od: FAIL: end: ####Begin stuff for Analyze########## #Findrec1(f,n,N,MaxC): Given a list f tries to find a linear recurrence equation with #poly coffs. #of maximum DEGREE+ORDER<=MaxC #e.g. try Findrec1([1,1,2,3,5,8,13,21,34,55,89],n,N,2); Findrec1:=proc(f,n,N,MaxC) local DEGREE, ORDER,ope,L: for L from 0 to MaxC do for ORDER from 1 to L do DEGREE:=L-ORDER: if (2+DEGREE)*(1+ORDER)+4>=nops(f) then RETURN(FAIL): fi: ope:=findrec([op(1..(2+DEGREE)*(1+ORDER)+4,f)],DEGREE,ORDER,n,N): if ope<>FAIL then RETURN(ope): fi: od: od: FAIL: end: #findrec(f,DEGREE,ORDER,n,N): guesses a recurrence operator annihilating #the sequence f of degree DEGREE and order ORDER #For example, try: findrec([seq(i,i=1..10)],0,2,n,N); findrec:=proc(f,DEGREE,ORDER,n,N) local ope,var,eq,i,j,n0,kv,var1,eq1,mu,a: option remember: if (1+DEGREE)*(1+ORDER)+5+ORDER>nops(f) then ERROR(`Insufficient data for a recurrence of order`,ORDER, `degree`,DEGREE): fi: ope:=0: var:={}: for i from 0 to ORDER do for j from 0 to DEGREE do ope:=ope+a[i,j]*n^j*N^i: var:=var union {a[i,j]}: od: od: eq:={}: for n0 from 1 to (1+DEGREE)*(1+ORDER)+4 do eq1:=0: for i from 0 to ORDER do eq1:=eq1+subs(n=n0,coeff(ope,N,i))*op(n0+i,f): od: eq:= eq union {eq1}: od: var1:=solve(eq,var): kv:={}: for i from 1 to nops(var1) do mu:=op(i,var1): if op(1,mu)=op(2,mu) then kv:= kv union {op(1,mu)}: fi: od: ope:=subs(var1,ope): if ope=0 then RETURN(FAIL): fi: ope:={seq(coeff(expand(ope),kv[i],1),i=1..nops(kv))} minus {0}: if nops(ope)>1 then RETURN(Yafe(ope[1],N)[2]): elif nops(ope)=1 then RETURN(Yafe(ope[1],N)[2]): else RETURN(FAIL): fi: end: Yafe:=proc(ope,N) local i,ope1,coe1,L: if ope=0 then RETURN(1,0): fi: ope1:=expand(ope): L:=degree(ope1,N): coe1:=coeff(ope1,N,L): ope1:=normal(ope1/coe1): ope1:=normal(ope1): ope1:= convert( [seq(factor(coeff(ope1,N,i))*N^i,i=ldegree(ope1,N)..degree(ope1,N))],`+`): factor(coe1),ope1: end: #SeqFromRec(ope,n,N,Ini,K): Given the first L-1 #terms of the sequence Ini=[f(1), ..., f(L-1)] #satisfied by the recurrence ope(n,N)f(n)=0 #extends it to the first K values SeqFromRec:=proc(ope,n,N,Ini,K) local ope1,gu,L,n1,j1: ope1:=Yafe(ope,N)[2]: L:=degree(ope1,N): if nops(Ini)<>L then ERROR(`Ini should be of length`, L): fi: ope1:=expand(subs(n=n-L,ope1)/N^L): gu:=Ini: for n1 from nops(Ini)+1 to K do gu:=[op(gu), -add(gu[nops(gu)+1-j1]*subs(n=n1,coeff(ope1,N,-j1)), j1=1..L)]: od: gu: end: ###end findrec #Findrec(f,n,N,MaxC,mekhir): Given a sequence f and #a maximum complexity MaxC finds the recurrence of #the smallest possible Degree with complexity<=MaxC+mekhir #e.g. try Findrec([1,1,2,3,5,8,13,21,34,55,89],n,N,2,2); Findrec:=proc(f,n,N,MaxC,mekhir) local ope,ope1,DEGREE,ORDER: option remember: ope:=Findrec1(f,n,N,MaxC): if ope=FAIL then RETURN(FAIL): fi: for DEGREE from 0 to degree(numer(normal(ope)),n)-1 do for ORDER from degree(ope,N)+1 to degree(numer(normal(ope)),N)+mekhir do ope1:=findrec(f,DEGREE,ORDER,n,N): if ope1<>FAIL then RETURN(ope1): fi: od: od: ope: end: #GuessRatGF1(L,x,d1,d2): guesses a rational generating function #(in x) (with degree d1 on top and #and d2 at bottom) for the sequence L (starting at 0) GuessRatGF1:=proc(L,x,d1,d2) local f,a,b,P,Q,i,eq,var: if nops(L)-(d1+d2+2)<3 then ERROR(`Insuffucient data`): fi: P:=add(a[i]*x^i,i=0..d1): Q:=add(b[i]*x^i,i=0..d2): f:=add(L[i+1]*x^i,i=0..nops(L)-1): f:=expand(Q*f-P): eq:={seq(coeff(f,x,i),i=0..nops(L)-1)}: var:={seq(a[i],i=0..d1),seq(b[i],i=0..d2)}: var:=solve(eq,var): P:=subs(var,P): Q:=subs(var,Q): if P=0 then RETURN(FAIL): fi: normal(P/Q): end: GuessRatGF:=proc(L,x) local d1,d2,d,gu: for d from 0 to nops(L)-6 do for d2 from 0 to d do d1:=d-d2: gu:=GuessRatGF1(L,x,d1,d2): if gu<>FAIL then RETURN(gu): fi: od: od: FAIL: end: #GuessPol1(L,d,n,s0): guesses a polynomial of degree d in n for # the list L, such that L[i]=P[i] for i>=s0 for example, try: #GuessPol1([(seq(i,i=1..10),1,n,1); GuessPol1:=proc(L,d,n,s0) local P,i,a,eq,var: if d>=nops(L)-s0-2 then ERROR(`the list is too small`): fi: P:=add(a[i]*n^i,i=0..d): var:={seq(a[i],i=0..d)}: eq:={seq(subs(n=i,P)-L[i],i=s0..s0+d+3)}: var:=solve(eq,var): if var=NULL then RETURN(FAIL): fi: subs(var,P): end: #GuessPol(L,n,s0): guesses a polynomial of degree d in n for # the list L, such that L[i]=P[i] for i>=s0 for example, try: #GuessPol([(seq(i,i=1..10),n,1); GuessPol:=proc(L,n,s0) local d,gu: for d from 0 to nops(L)-s0-3 do gu:=GuessPol1(L,d,n,s0): if gu<>FAIL then RETURN(gu): fi: od: FAIL: end: #Analyze1(L,n,N,x): analyzes a sequence L that comes from enumeration #of permutations Analyze1:=proc(L,n,N,x,mekhir) local ope,MaxC,gu,mu,L1,s0,GU,ope1: GU:=[L]: if L[nops(L)]=0 then print(`the sequence is finite`): RETURN(GU): fi: mu:=GuessPol(L,n,10): if mu<>FAIL then print(`the sequence seems to be polynomial`): print(mu): RETURN([L,mu]): fi: MaxC:=2*trunc(sqrt(nops(L)-4)-3/2)-1; L1:=[op(2..nops(L),L)]: ope:=Findrec(L1,n,N,MaxC,1): if ope<>FAIL then if degree(numer(normal(ope)),n)>0 then L1:=SeqFromRecG(ope,n,N,L1,3*nops(L1),4): fi: ope1:=Findrec(L1,n,N,MaxC+2,mekhir): if degree(numer(normal(ope1)),n)< degree(numer(normal(ope)),n) then ope:=ope1: fi: GU:=[op(GU),ope]: if degree(ope,n)=0 then gu:=GuessRatGF(L,x): GU:=[op(GU),gu]: if {solve(denom(gu),x)}={1} then s0:=max(degree(numer(gu),x)-degree(denom(gu),x)+1,1): mu:=GuessPol(L1,n,s0): if mu<>FAIL then GU:=[op(GU),gu,mu]: print(`This enumerating sequence seems to be a polynoymial`): print(mu, `for n >=`, s0): RETURN(GU): fi: fi: print(`This enumerating sequence seems to have the `): print(` rational generating function`, gu): RETURN(GU): fi: print(`This enumerating sequence seems to have the `): print(`annihilating operator `, ope): RETURN(GU): fi: GU: end: ####End stuff for Analyze########## #SeqFromRecG(ope,n,N,Ini,K,s): Given a list #of size >=s+L-2 #finds the first K terms of the sequence #satisfied by the recurrence ope(n,N)f(n)=0 #starting from the s-th term SeqFromRecG:=proc(ope,n,N,Ini,K,s) local ope1,gu,L,n1,j1: ope1:=Yafe(ope,N)[2]: L:=degree(ope1,N): if nops(Ini)<=L+s then ERROR(`Ini should be of length >=`, L+s): fi: ope1:=expand(subs(n=n-L,ope1)/N^L): gu:=[op(1..s+L-1,Ini)]: for n1 from s+L to K do gu:=[op(gu), -add(gu[nops(gu)+1-j1]*subs(n=n1,coeff(ope1,N,-j1)), j1=1..L)]: od: gu: end: #UpperSchemeF(Patterns,Gvul,GvulGap): Finds a scheme for the Wilf class #of restricted permutations 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: #UpperSchemeF({[1,2,3,4]},3,2); UpperSchemeF:=proc(Patterns,Gvul,GvulGap) local mu,gu,i: mu:=SchemeF(Patterns,Gvul,GvulGap): if nops([mu])=1 then print(`It has a scheme`): RETURN(mu): fi: mu:=mu[2]: gu:=[]: for i from 1 to nops(mu) do if mu[i][3]<>{} or nops(mu[i][1])