print(`Created: Oct.30, 2017` ): print(` This is PW123`): print(`It is a Maple package that implements Doron Zeilberger's schemes in papers:`): print(``): print(`"Enumeration Schemes and, More Importantly, their Automatic Generation"`): print(``): print(`and "A Snappy Proof that 123 Avoiding Words are Equinumerous with 132 Avoiding Words"`): print(`both available from Zeilberger's website`): print(``): print(`and Mingjia Yang's scheme for enumerating words asscociated with list L that contain exactly one pattern 123`): print(``); print(`which is described in her paper "Enumerating of Words that Contain Exactly One Pattern 123"`): print(`available from Yang's website`): print(`---------------------------------------`): print(`For a list of the MAIN procedures type Help();, for help with`): print(`a specific procedure, type Help(procedure_name); .`): print(``): print(`---------------------------------------`): print(`Definition: we say a word is associated with a list L if it has L[i] many letter i`): print(`---------------------------------------`): with(combinat): Help:=proc(): if args=NULL then print(`The main procedures are: Av,Avw,AW,WOne,WOneb `): elif nops([args])=1 and op(1,[args])=Av then print(`Av(n): inputs a positive integer n and outputs the number of permutations of [n] that avoids pattern 123`): print(`using the prefix scheme in Dr. Zeilberger's paper "Enumeration Schemes and, More Importantly, their Automatic Generation"`): elif nops([args])=1 and op(1,[args])=Avw then print(`Avw(L): inputs a list L and outputs the number of words associated with L that avoid pattern 123`): print(`extending the prefix scheme in Dr. Zeilberger's paper "Enumeration Schemes and, More Importantly, their Automatic Generation" to words`): print(`Example: Avw([3,2,4])=326, meaning there are 326 many words associated with [3,2,4] that avoid pattern 123`): elif nops([args])=1 and op(1,[args])=AW then print(`AW(L) inputs a list L and outputs the number of 123-avoiding words associated with list L`): print(`It implements the scheme in Zeilberger's paper:`): print(`"A Snappy Proof that 123 Avoiding Words are Equinumerous with 132 Avoiding Words"`): print(`Example: AW([2,2,3]) outputs 83, meaning there are 83 words associated with [2,2,3] that avoid pattern 123`): elif nops([args])=1 and op(1,[args])=WOne then print(`WOne(L): inputs a list L and outputs the number of words associated with L that contains exactly one pattern 123.`): print(`It implements the scheme in Theorem 1 of Yang's paper "Enumerating of Words that Contain Exactly One Pattern 123"`): print(`Example: WOne([7,3,4]) outputs 756, meaning there are 756 words associated with [7,3,4] that contains exactly one pattern 123`): elif nops([args])=1 and op(1,[args])=WOneb then print(`WOneb(L): inputs a list L and outputs the number of words associated with L that contains exactly one pattern 123,using brute force`): else print(`There is no help for`,arg): fi: end: ##########Enumerating the number of 123-avoiding permutations, using the prefix scheme in Dr. Zeilberger's paper "Enumeration Schemes and, More Importantly, their Automatic Generation"############ #Av(n) inputs a positive integer n and outputs the number of permutations of [n] that avoids pattern 123 Av:=proc(n) local i: option remember: add(Av1(i,n),i=1..n): end: Av1:=proc(i,n) local j: option remember: if i>n then RETURN(0): fi: if n<3 then RETURN(1): fi: add(Av1(j,n-1),j=1..i): end: #################Enumerating the number of 123-avoiding words, generalizing the prefix scheme in Dr. Zeilberger's paper "Enumeration Schemes and, More Importantly, their Automatic Generation" to words############## #Avw(L) inputs a list L and outputs the number of words associated with L that avoid pattern 123 Avw:=proc(L) local i: option remember: add(Avw1(i,L),i=1..nops(L)): end: Avw1:=proc(i,L) local L1,S,j,h: option remember: L1:=L: for j from 1 to nops(L1) do if L1[j]=0 then if j=nops(L1) then L1:=[op(1..j-1,L1)]: else L1:=[op(1..j-1,L1),op(j+1..nops(L1),L1)]: fi: break: fi: od: if i>nops(L1) then RETURN(0): fi: if add(L1[j],j=1..nops(L1))<3 then RETURN(1): fi: if i=nops(L1) then if L1[i]=1 then S:=add(Avw1(h,[op(1..i-1,L1),L1[i]-1,op(i+1..nops(L1),L1)]),h=1..i-1): else S:=add(Avw1(h,[op(1..i-1,L1),L1[i]-1,op(i+1..nops(L1),L1)]),h=1..i): fi: else if L1[i]=1 then S:=add(Avw1(h,[op(1..i-1,L1),L1[i]-1,op(i+1..nops(L1),L1)]),h=1..i-1)+Avw1(i,[op(1..nops(L1)-1,L1),L1[-1]-1]): else S:=add(Avw1(h,[op(1..i-1,L1),L1[i]-1,op(i+1..nops(L1),L1)]),h=1..i)+Avw1(i,[op(1..nops(L1)-1,L1),L1[-1]-1]): fi: fi: S: end: ###############Implementing the scheme in Dr.Zeilberger's paper "A Snappy Proof that 123 Avoiding Words are Equinumerous with 132 Avoiding Words"############ #AW(L) inputs a list L and outputs the number of 123-avoiding words associated with list L AW:=proc(L) local L1,j,S,i: option remember: S:={}: L1:=L: for j from 1 to nops(L1) do if L1[j]=0 then if j=nops(L1) then L1:=[op(1..j-1,L1)]: else L1:=[op(1..j-1,L1),op(j+1..nops(L1),L1)]: fi: break: fi: od: for i from 1 to nops(L1) do S:=S union {L1[i]}: od: if S={1} then RETURN(Av(nops(L1))): fi: add(AW([op(1..i-1,L1),L1[i]-1,add(L1[j],j=i+1..nops(L1))]),i=1..nops(L1)-1)+AW([op(1..nops(L1)-1,L1),L1[-1]-1]): end: ##################Permutations that contain exactly one pattern 123, brute force################# #Good(n) outputs the set of permutations of [n] that contains exactly one pattern 123 Good:=proc(n) local L,S,p: option remember: L:=permute(n): S:={}: for p in L do if Occur(p)=1 then S:=S union {p}: fi: od: S: end: #Occur(L) inputs a list L and outputs the number of occurrence of pattern 123 in L Occur:=proc(L) local n,co,i,j,k: option remember: co:=0: n:=nops(L): for i from 1 to nops(L)-2 do for j from i+1 to nops(L)-1 do for k from j+1 to nops(L) do if L[i]