#####################################################################
## PWilf.txt Save this file as  PWilf.txt  to use it,                    #
# stay in the                                                        #
## same directory, get into Maple (by typing: maple <Enter> )        #
## and then type:  read  `PWilf.txt` <Enter>                           #
## Then follow the instructions given there                          #
##                                                                   #
## Written by Lucy Martinez and Doron Zeilberger, Rutgers University #
######################################################################

with(combinat):

print(`First Written: Feb., 2025: tested for Maple 2020 `):
print(`Version: May 2, 2025 `):
print():
print(`This is PWilf.txt, A Maple package`):
print(`accompanying Lucy Martinez and Doron Zeilberger's  article: `):
print(` Experimenting with Parking Permutations`):
print(` http://sites.math.rutgers.edu/~zeilberg/tokhniot/mamarim/mamarimhtml/pwilf.html `):
print():
print(`The most current version is available on WWW at:`):
print(` http://sites.math.rutgers.edu/~zeilberg/tokhniot/PWilf.txt .`):
print(`Please report all bugs to: DoronZeil at gmail dot com .`):
print():

print(`-------------------------------------------`):
print(`For general help, and a list of the MAIN functions,`):
print(` type "ezra();". For specific help type "ezra(procedure_name);" `):
print(`For a list of the supporting functions type: ezra1();`):
print():
print(`-------------------`):



print(`-------------------------------------------`):
print(`For  a list of the Story functions,`):
print(` type "ezraS();". For specific help type "ezra(procedure_name);" `):
print():
print(`-------------------`):


print(`-------------------------------------------`):
print(`For  a list of the State functions,`):
print(` type "ezraSt();". For specific help type "ezra(procedure_name);" `):
print():
print(`-------------------`):



print(`-------------------------------------------`):
print(`For  a list of the Traditional Scheme functions,`):
print(` type "ezraScT();". For specific help type "ezra(procedure_name);" `):
print():
print(`-------------------`):

print(`-------------------------------------------`):
print(`For  a list of the Scheme functions,`):
print(` type "ezraSc();". For specific help type "ezra(procedure_name);" `):
print():
print(`-------------------`):

print(`-------------------------------------------`):
print(`For  a list of the Test functions,`):
print(` type "ezraTest();". For specific help type "ezra(procedure_name);" `):
print():
print(`-------------------`):


print(`-------------------`):



ezraSc:=proc()
if args=NULL then

print(`The Scheme  procedures are: an,ani,apn,apni, bn, bpn, BreakUp,  cn,cni,cpn, cpni `):
print(`dn, dnr, dpn, dpnr, en, enir, epn, epnir, fn, fnir, fpn, fpnir, gn,gpn`):

else
ezra(args):
fi:

end:

ezraSt:=proc()
if args=NULL then
print(`The State  procedures are:  Comp,  PerSt, St1, St11 StateTable, Yels`):
print(``):

else
ezra(args):

fi:


end:



ezraS:=proc()
if args=NULL then

print(`The Story procedures are:  `):
print(``):

else
ezra(args):
fi:
end:

ezraTest:=proc()
if args=NULL then

print(`The test procedures are: Test231321a, Test231321, Test213a, Test213, Test321a, Test321 `):
print(``):

else
ezra(args):
fi:
end:



ezraScT:=proc()
if args=NULL then

print(`The Traditional Scheme procedures are: `):
print(` DomainWilf, DomainWilfTable, EvalScheme, ExtendScheme, FindPreScheme, FindScheme, FindScheme1, FixedSet, IsHope1, IsRevDel, IsRevDel1, RevDelSet1, WilfSeqVS, WilfTail, WilfTailTable `):

else
ezra(args):

fi:

end:

ezra1:=proc()
if args=NULL then

print(`The SUPPORTING procedures are: `):
print(`CS1, CS,  ParkingTable, PTable, PWilf, Tot, Wilf, WilfSeq `):

else
ezra(args):

fi:

end:

#Tot(S): Given a set of permutations S finds the sum of their CFO


ezra:=proc()
if args=NULL then

print(`PWilf.txt: A Maple package for  exploring patterns in parking permutations`):

print(`The MAIN procedures are: CFO, Park, PWilfSeq`):

elif nargs=1 and args[1]=WilfSeqVS then
print(`WilfSeqVS(n,r,Patterns,K,N): Tries to find a scheme via FindScheme(n,r,Patterns,K) and if found used it to compute WilfSeq(Patterns,N). If does not agree for the first 7 terms returns FAIL. Try:`):
print(`WilfSeqVS(6,2,{[1,2,3]},2,20);`):

elif nargs=1 and args[1]=WilfSeq then
print(`WilfSeq(Patterns,N): inputs a positive integer N, and a set of patterns Patterns, and outputs the list of length N whose n-th entry is`):
print(`the number of permutations avoiding the patterns in the set of patterns Patterns. This is by brute force!.Try:`):
print(`WilfSeq({[1,2,3],[1,3,2]},6);`):


elif nargs=1 and args[1]=EvalScheme then
print(`EvalScheme(S,n,v): inputs a scheme S (that is supposed to count permutations avoding patterns Pattern, and a vector v (of distinct positive integers all between 1 and n) outputs`):
print(`the number of such permutations that end with v. If v=[] then it counts all of them. Try:`):
print(`S:=FindScheme(6,2,{[1,2,3]},2): EvalScheme(S,8,[2]);`):

elif nargs=1 and args[1]=FixedSet then
print(`FixedSet(S): Given a list S of vectors of the same size, say, k, outputs`):
print(`the vector of length k, whose i-th component is 0 if they are not all the same`):
print(`and the common value if they are. Try:`):
print(`FixedSet({[1,2],[1,3],[1,4]});`):


elif nargs=1 and args[1]=FindPreScheme then
print(`FindPreScheme(n,r,Patterns,K): Tries to find a pre-scheme for the set of patterns Patterns up to length K by trying FindScheme1(n1,Patterns,K) for n1=n..n+r, and outputs it if they`):
print(`all agree. Otherwise returns FAIL.  (-1) indicates n. Try:`):
print(`FindPreScheme(6,2,{[1,2,3]},2);`):


elif nargs=1 and args[1]=FindScheme then
print(`FindScheme(n,r,Patterns,K): Tries to find a scheme for in the format [Expa,Redu,ReduTable], where Expa is the set of permutation-suffices that are expandable, Redu`):
print(`is the set of permutation-suffices thar are reducible, ReduTable is a table such that for every sigma in Redu, ReduTable[sigma] is the pair (list of length 2)`):
print(`[PlaceToDelete, Domain], where Domain has the format, a list of length nops(sig), where 0 means no restriction 1 means that it is literally 1, and -1 means that it is n. Try:`):
print(`FindScheme(6,2,{[1,2,3]},2);`):

elif nargs=1 and args[1]=FindScheme1 then
print(`FindScheme1(n,Patterns,K): Tries to find a scheme for the set of patterns Patterns up to length K. (-1) indicates n. Try:`):
print(`FindScheme1(8,{[1,2,3]},4);`):

elif nargs=1 and args[1]=ExtendScheme then
print(`ExtendScheme(n,Patterns, Sc): Given a partial scheme Sc=[RevR,YTD] takes YTD[1] and sees which of its children can go to RV and which go to YTD to the end of the queue. Try:`):
print(`ExtendScheme(8,{[1,2,3]},[[],[[1]] ]);`):

elif nargs=1 and args[1]=IsRevDel then
print(`IsRevDel(n,Patterns,sig,k): Is the k-th entry of all possible tails of length nops(sig) that reduce to pi Reversely deletable. Try:`):
print(`IsRevDel(8,{[1,2,3]},[2,1],2);`):

elif nargs=1 and args[1]=DomainWilf then
print(`DomainWilf(n,Patterns,sig): inputs a pos. integer n, a set of Patterns, Patterns, and a permutation sig, outputs the set of tails`):
print(`in Wilf(n,Patterns) that reduce to sig. Try:`):
print(`DomainWilf(7,{[1,2,3]},[1,2]);`):

elif nargs=1 and args[1]=IsHope1 then
print(`IsHope1(n,Patterns,r): Is there hope for a scheme of depth r for the set of Patterns. Try:`):
print(`IsHope1(8,{[1,2,3]},2);`):

elif nargs=1 and args[1]=an then
print(`an(n): the number of permutations of {1,...,n}  (obviously n!) but using our scheme. Try: `):
print(`an(7);`):

elif nargs=1 and args[1]=ani then
print(`ani(n,i): the number of permutations of {1,...,n}   that end with i (obviously (n-1)!) but using our scheme. Try: `):
print(`ani(7,3);`):

elif nargs=1 and args[1]=apn then
print(`apn(n): the number of parking functions of {1,...,n}  using our scheme. It is famously (n+1)^(n-1), but we are doing it our way. Try: `):
print(`{seq(apn(i)-(i+1)^(i-1),i=1..10)};`):

elif nargs=1 and args[1]=apni then
print(`apni(n,i): the number of parking functions of {1,...,n}   whose resulting permutations end with i (does not seem to be nice) but using our scheme. Needed for pn(n). Try: `):
print(`apni(7,3);`):


elif nargs=1 and args[1]=bn then
print(`bn(n): The number of permutations of {1,2,...,n} avoding the patterns 123,213, first proved to be 2^(n-1) by Rodica Simion and Frank Schmidt, using our way`):

elif nargs=1 and args[1]=bniOld then
print(`bniOld(n,i): The number of permutations of {1,2,...,n} avoding the patterns 123,213, that end in i.`):

elif nargs=1 and args[1]=bpn then
print(`bpn(n): The number of parking functions of {1,2,...,n} avoding the patterns 123,213, using our way. Try`):
print(`[seq(bpn(i),i=1..10)];`):

elif nargs=1 and args[1]=bpniOld then
print(`bpniOld(n,i): The number of parking functions of {1,2,...,n} that lead to permutations avoding the patterns 123,213, that end in i. Try`):
print(`bpniOld(10,1);`):


elif nargs=1 and args[1]=BreakUp then
print(`BreakUp(pi): Given a permutation pi of length n, If [pi1,pi2] are the reductions of those that come before the n and the one that comes after n`):
print(`outputs the location of the i and CFO(pi)/(CFO(pi1)*CFO(pi2)).`):
print(`Try:`):
print(`BreakUp([1,5,2,3,4]);`):


elif nargs=1 and args[1]=cn then
print(`cn(n): The number of permutations of {1,2,...,n} avoding the pattern 123`):


elif nargs=1 and args[1]=cni then
print(`cni(n,i): The number of permutations of {1,2,...,n} avoding the patterns 123 that end in i.`):

elif nargs=1 and args[1]=cpn then
print(`cpn(n): The number of parking functions in  {1,2,...,n} that produce permutations avoding the pattern 123. Try:`):
print(`[seq(cpn(i),i=1..10)];`):


elif nargs=1 and args[1]=cpni then
print(`cpni(n): The number of parking functions in  {1,2,...,n} that produce permutations avoding the pattern 123 and than end with i.`):

elif nargs=1 and args[1]=dn then
print(`dn(n): The number of permutations of {1,2,...,n} avoding the pattern 231, 321`):


elif nargs=1 and args[1]=dnr then
print(`dnr(n,r): the NUMBER of permutations of {1,...,n} avoiding the patterns 231,321 and state [i,r]`):
print(`where if 1<=r<=n-1 then i=n-1 and if r=n then i=n. Try: `):
print(`dnr(6,1);`):


elif nargs=1 and args[1]=dpn then
print(`dpn(n): The number of parking functions leading to permutations of {1,2,...,n} avoding the pattern 231, 321`):


elif nargs=1 and args[1]=dpnr then
print(`dpnr(n,r): the number of parking functions that lead to permutations of length n avoiding the patterns 231,321`):
print(`that have state (x,r) where if if 1<=r<=n-1 then x=n-1 and if r=n then x=n. Try: `):
print(`dpnr(6,1);`):

elif nargs=1 and args[1]=DomainWilfTable then
print(`DomainWilfTable(n,Patterns,r): The table that for each permutation of r gives you all tails of length r of members of Wilf(n,Patterns) that reduce to it. Try:`):
print(`DomainWilfTable(8,{[1,2,3]},2);`):

elif nargs=1 and args[1]=IsRevDel1 then
print(`IsRevDel1(n,Patterns,zanav,k): Is the k-th entry of zanav reversely deletable for permutations of length n that avoid the set of patterns Patterns and that end in zanav? Try`):
print(`IsRevDel1(8,{[2,1,3]},[5,2],2);`):


elif nargs=1 and args[1]=Test231321a then
print(`Test231321a(n,i,r): tests the 231,321 scheme for states (i,r)`):
print(`where 1<=r<=i<=n-1 and i=r=n. Try: `):
print(`Test213a(7,3,2);`);

elif nargs=1 and args[1]=Test231321 then
print(`Test231321(n) : Tests the 231,321 scheme for any n. Try`):
print(`Test231321(6);`);


elif nargs=1 and args[1]=en then
print(`en(n): the NUMBER of permutations of {1,...,n} avoiding the pattern 213. Try: `):
print(`[seq(en(i),i=2..10)];`);

elif nargs=1 and args[1]=enir then
print(`enir(n,i,r): the NUMBER of permutations of {1,...,n} avoiding the pattern 213 and state [i,r]. try: `):
print(`enir(6,1,1);`):


elif nargs=1 and args[1]=epn then
print(`epn(n): the NUMBER of parking functions that lead to permutations of {1,...,n} avoiding the pattern 213. Try: `):
print(`[seq(epn(i),i=2..10)];`);

elif nargs=1 and args[1]=epnir then
print(`epnir(n,i,r): the NUMBER of parking functions that lead to permutations of {1,...,n} avoiding the pattern 213`):
print(`with state (i,r). Try: `):
print(`epnir(6,1,1);`);
 
elif nargs=1 and args[1]=Test213a then
print(`Test213a(n,i,r): Test the 213 scheme for the states (i,r)`):
print(`where 1<=r<=i<=n-1 and i=r=n. Try: `):
print(`Test213a(7,3,2);`);

elif nargs=1 and args[1]=Test213 then
print(`Test213(n): Tests the 213 scheme for any n. Try`):
print(`Test213(6);`);

elif nargs=1 and args[1]=fn then
print(`fn(n): the NUMBER of permutations of {1,...,n} avoiding the pattern 321. Try: `):
print(`[seq(fn(i),i=1..10)];`);

elif nargs=1 and args[1]=fnir then
print(`fnir(n,i,r): the NUMBER of permutations of {1,...,n} avoiding the pattern 321 with state (i,r). Try: `):
print(`fnir(6,1,1);`);

elif nargs=1 and args[1]=fpn then
print(`fpn(n): the NUMBER of parking functions that lead to permutations of {1,...,n} avoiding the pattern 321. Try: `):
print(`[seq(fpn(i),i=1..10)];`);

elif nargs=1 and args[1]=fpnir then
print(`fpnir(n,i,r): the NUMBER of parking functions that lead to permutations of {1,...,n} avoiding the pattern 321.`):
print(`with state (i,r). Try: `):
print(`fpnir(6,1,1);`);

elif nargs=1 and args[1]=gn then
print(`gn(n): the number of parmutations that avoid 132 and also the number that avoid 231. Try:`):
print(`[seq(gn(i),i=1..20)];`):


elif nargs=1 and args[1]=gpn then
print(`gpn(n): the number parking functions of length n leading to parmutations that avoid 132 and also the number that avoid 231. Try:`):
print(`[seq(gpn(i),i=1..20)];`):


elif nargs=1 and args[1]=Test321a then
print(`Test321a(n,i,r): Test the 321 scheme for the states (i,r)`):
print(`where 1<=r<=i<=n-1 and i=r=n. Try: `):
print(`Test321a(7,3,2);`);

elif nargs=1 and args[1]=Test321 then
print(`Test321(n): Tests the 321 scheme for any n. Try`):
print(`Test321(6);`);


elif nargs=1 and args[1]=Comp then
print(`Comp(n,st): compares the decomposition into states`):


elif nargs=1 and args[1]=Park then
print(`Park(L): Given  a function L from [1,n] to [1,n] finds the final parking permutation or retunrs FAIL. It also returns the list of where every car winded up Try`):
print(`Park([1,1,1]);`):

elif nargs=1 and args[1]=ParkingTable then
print(`ParkingTable(n): for each permutation the set of parking functions that go with it. Try:`):
print(`ParkingTable(3);`):


elif nargs=1 and args[1]=PerSt then
print(`PerSt(n,Patterns,st) inputs a pos. integer n and a set of patterns state st, outputs the set of permutations avoiding the pattersns, with that state. Try:`):
print(`PerSt(7,{},[1,1]);`):


elif nargs=1 and args[1]=CS then
print(`CS(n): the set of Catalan sequences of length n. Try:`):
print(`CS(5);`):
print(``):

elif nargs=1 and args[1]=PP then
print(`PP(n): the set of parking functions of length n. Try:`):
print(`PP(5);`):
print(``):


elif nargs=1 and args[1]=Ptable then
print(`Ptable(pi) : the parking table of the permutation pi. Try:`):
print(`Ptable([4,1,2,3]);`):

elif nargs=1 and args[1]=PWilf then
print(`PWilf(Patterns,n): The number of parking functions that yield permutations avoiding the patterns in the set of patterns Patterns. Try:`):
print(`PWilf({[1,2,3],[1,3,2]},8);`):

elif nargs=1 and args[1]=PWilfSeq then
print(`PWilfSeq(Patterns,N): inputs a positive integer N, and a set of patterns Patterns, and outputs the list of length N whose n-th entry is`):
print(`the number of parking functions of length n that yield permutations avoiding the patterns in the set of patterns Patterns. Try:`):
print(`PWilfSeq({[1,2,3],[1,3,2]},6);`):


elif nargs=1 and args[1]=St1 then
print(`St1(pi): the state of the permutation pi.  Try: St1([4,3,2,1,5]);`):

elif nargs=1 and args[1]=St11 then
print(`St11(pi): The state of the permutation pi and the state of of its child. Try:`):
print(`St11([1,2,3,4]);`):

elif nargs=1 and args[1]=StateTable then
print(`StateTable(n,Patterns): outputs the list of states and the corresponding table T[state]:=set of permutations with that state in the set of permutations of {1,...,n}`):
print(`avoiding the set of patterns Patterns`):
print(`For all permutations take Patterns={}. For example, try:`):
print(`StateTable(5,{});`):
print(`StateTable(5,{[1,2,3],[2,1,3]});`):

elif nargs=1 and args[1]=Tot then
print(`Tot(S): Given a set of permutations S finds the sum of their CFO`):

elif nargs=1 and args[1]=Wilf then
print(`Wilf(n,Patterns): all permutations of length n`):
print(`that avoid the patterns in the set of patterns`):
print(`Patterns. Try: `):
print(`Wilf(5,{[1,2,3],[1,3,2]});`):

elif nargs=1 and args[1]=WilfTail then
print(`WilfTail(n,Patterns,zanav): all the members of Wilf(n,Patterns) that end in zanav. Try:`):
print(`WilfTail(7,{[3,1,2]},[1,2]);`):

elif nargs=1 and args[1]=WilfTailTable then
print(`WilfTailTable(n,Patterns,r): all the tails of size r of Wilf(n,Patterns), followed by the table. Try:`):
print(`WilfTailTable(7,{[3,1,2]},2);`):

elif nargs=1 and args[1]=Yels then
print(`Yels(n,Patterns,st): all the states of the children of the set of permutations of length n avoding the set of patterns Patterns, with the state st. Try:`):
print(`Yels(6,{[1,2,3]},[1,1]);`):


elif nargs=1 and args[1]=CFO then
print(`CFO(outcome): Given a permutation outcome, counts the number of`):
print(`parking functions that park in the order of the permutation outcome using`):
print(`the counting through permutations method. Try:`):
print(`CFO([1,2,3,4]);`):

elif nargs=1 and args[1]=RevDelSet1 then
print(`RevDelSet1(n,Patterns,r,k): The subset of WilfTailTable(n,Patterns,r)[1] that k<=r is reversely reducible. Try:`):
print(`RevDelSet1(8,{[1,2,3]},2,1);`):


else
 print(`There is no such thing as`, args):

fi:

end:



###############################
#CS1(n,k):
CS1:=proc(n,k) local gu,lu,lu1,k1:
option remember:
if n=1 then
if k=1 then
 RETURN({[1]}):
else
RETURN({}):
fi:
fi:

gu:={}:

for k1 from 1 to k do
lu:=CS1(n-1,min(k1,n-1)):
gu:=gu union {seq([op(lu1),k],lu1 in lu)}:
od:
gu:
end:

#CS(n): the set of Catalan sequences of length n. 
CS:=proc(n) local k:
option remember:
{seq(op(CS1(n,k)),k=1..n)}:
end:


#PP(n): the set of parking functions of length n
PP:=proc(n) local gu,gu1:
gu:=CS(n):
{seq(op(permute(gu1)),gu1 in gu)}:
end:



#Park(L): Given  a function L from [1,n] to [1,n] finds the final parking permutation or returns FAIL. It also returns the list of where every car winded up Try
#Park([1,1,1]);
Park:=proc(L) local n,L1,i,j,a,L2:
n:=nops(L):

if {op(L)} minus {seq(i,i=1..n)}<>{} then
 ERROR(`bad input`):
fi:

L1:=[0$n]:

for i from 1 to n do
 a:=L[i]:

 if L1[a]=0 then
   L1:=[op(1..a-1,L1),i,op(a+1..n,L1)]:
 L2[i]:=a:
 else
 for j from a+1 to n while L1[j]<>0 do od:
  if j=n+1 then
    RETURN(FAIL):
 else
   L1:=[op(1..j-1,L1),i,op(j+1..n,L1)]:
 L2[i]:=j:
 fi:
fi:

od:

[L1,[seq(L2[j],j=1..n)]]:

end:





#CSv1(v,k): the increasing sequences a such that a[i]<=v[i] and a[nops(v)]=k
CSv1:=proc(v,k) local n, gu,lu,k1,lu1:
option remember:
n:=nops(v):
if n=1 then
 if k<=v[1] then
 RETURN({[k]}):
else
 RETURN({}):
fi:
fi:

if  not (k>=1 and k<=v[n]) then
 RETURN({}):
fi:

gu:={}:

for k1 from 1 to min(k,v[n-1]) do
lu:=CSv1([op(1..n-1,v)],k1):
gu:=gu union {seq([op(lu1),k],lu1 in lu)}:
od:
gu:
end:

CSv:=proc(v) local n,k:
option remember:
n:=nops(v):
{seq(op(CSv1(v,k)),k=1..v[n])}:
end:


#ParkingTable(n): for each permutation the set of parking functions that go with it
ParkingTable:=proc(n) local gu,mu,T,i,mu1:
gu:=permute([seq(i,i=1..n)]):
mu:=PP(n):

for i from 1 to nops(gu) do
 T[gu[i]]:={}:
od:

for mu1 in mu do
T[Park(mu1)[1]]:=T[Park(mu1)[1]] union {mu1}:
od:

[seq([gu[i],T[gu[i]]],i=1..nops(gu))];

end:




#CFOold(outcome): Given an permutation outcome, counts the number of parking functions that
#park in the order of the permutation outcome using the counting through permutations method
#Try: CFO([3,2,1]);
CFOold:=proc(outcome) local n, i, j, Li, product:
n:=nops(outcome):
if {op(outcome)}<>{seq(i,i=1..n)} then
 print(`The given input must be a permutation`):
 return(FAIL):
fi:

product:=1: 
for i from 1 to n do
 Li :=0:  #start with a length of 1 for L(i, perm)
 #compute L(i,outcome) by looking backwards
 for j from i by -1 to 1 do
  if outcome[j]<=outcome[i] then
   Li := Li + 1:
  else
   break: #stop counting when the condition is violated
  fi:
 od:
 product:=product*Li:
od:
product:
end:


##############################Start from Wilf


#IV(n,k) all increasing vectors of length
#k of the form 1<=i_1< ...<i_k <=n

IV:=proc(n,k)
local i,gu,mu:

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

if n<k then
RETURN({}):
fi:

gu:=IV(n-1,k):
mu:=IV(n-1,k-1):

for i from 1 to nops(mu) do
 gu:=gu union {[op(op(i,mu)),n]}:
od:

gu:
end:


#good1(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)

good1:=proc(pi,pattern1)
local gu,k,n,i,j,subperm,vec:

if pi=pattern1 then
RETURN(0):
fi:

n:=nops(pi):

k:=nops(pattern1):
if k>n then
RETURN(1):
fi:
gu:=IV(n,k-2):

for i from 1 to nops(gu) do
vec:=op(i,gu):
subperm:=[op(1,pi)]:
for j from 1 to k-2 do
subperm:=[op(subperm),pi[vec[j]]]:
od:
subperm:=[op(subperm),pi[n]]:
if redu(subperm)=pattern1 then
RETURN(0):
fi:
od:

1:

end:



#good(pi,SetPatterns)
#Given a permutation pi, and a set of patterns
#SetPatterns, 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)

good:=proc(pi,SetPatterns)
local i:
if member(pi,SetPatterns) then
RETURN(0):
fi:

for i from 1 to nops(SetPatterns) do
if good1(pi,op(i,SetPatterns))=0 then
 RETURN(0):
fi:
od:
1:
end:
  
#redu(perm): Given a permutation on a set of positive integers
#finds its reduced form
 
redu:=proc(perm)
local gu,i,ra,mu:
gu:=sort(perm):
 
for i from 1 to nops(gu) do
ra[gu[i]]:=i:
od:
 
mu:=[]:
 
for i from 1 to nops(perm) do
mu:=[op(mu),ra[perm[i]]]:
od:
mu:
 
 
 
end:

#Insert(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
 
Insert:=proc(pi,i)
local mu,j:
mu:=[]:
 
for j from 1 to nops(pi) do
if pi[j]<i then
mu:=[op(mu),pi[j]]:
else
mu:=[op(mu),pi[j]+1]:
fi:
od:
mu:=[op(mu),i]:
mu:
end:

#Wilf(n,Patterns): all permutations of length n
#that avoid the patterns in the set of patterns
#Patterns
 
Wilf:=proc(n,Patterns)
local i,mu,gu,pi,j,muamad:
option remember:
 
 
if n=0 then
RETURN({[]}):
fi:
 
mu:=Wilf(n-1,Patterns):
gu:={}:
 
for i from 1 to nops(mu) do
pi:=op(i,mu):
 
for j from 1 to n do
muamad:=Insert(pi,j):
if member(redu([op(2..n,muamad)]),mu) then
  if good(muamad,Patterns)=1 then
   gu:=gu union {muamad}:
  fi:
fi:
od:
od:
 
gu:
end:

#PWilf(Patterns,n): The number of parking functions that yield permutations avoiding the patterns in the set of patterns Patterns. Try:
#PWilf({[1,2,3],[1,3,2]},n);
PWilf:= proc(Patterns,n) local gu, gu1; gu := Wilf(n, Patterns); add(CFO(gu1), gu1 in gu) end:


#PWilfSeq(Patterns,N): inputs a positive integer N, and a set of patterns Patterns, and outputs the list of length N whose n-th entry is
#the number of parking functions of length n that yield permutations avoiding the patterns in the set of patterns Patterns. Try:
#PWilfSeq({[1,2,3],[1,3,2]},6);
PWilfSeq:=proc(Patterns, N) local n; seq(PWilf(Patterns,n), n = 1 .. N) end:


#WilfSeq(Patterns,N): inputs a positive integer N, and a set of patterns Patterns, and outputs the list of length N whose n-th entry is
#the number of permutations avoiding the patterns in the set of patterns Patterns. This is by brute force!.Try:
#WilfSeq({[1,2,3],[1,3,2]},6);
WilfSeq:=proc(Patterns, N) local n; [seq(nops(Wilf(n,Patterns)), n = 1 .. N)]: end:

###end from Wilf


#CFOrec(pi): recursive version of CFO(pi)
CFOrec:=proc(pi) local i,n: 
option remember:
n:=nops(pi):
if pi=[1] or pi=[] then  
RETURN(1): 
fi:

for i from 0 to n-1 while pi[n-i]<=pi[n] do od:
i*CFO(redu([op(1..n-1,pi)])):
end:


CFO:=proc(pi) local i,j,n,p: 
if pi=[1] or pi=[] then  
RETURN(1): 
fi:

n:=nops(pi):
p:=1:
for j from 1 to n do
for i from 0 to j-1 while pi[j-i]<=pi[j] do od:
p:=i*p:
od:

end:




#Ptable(pi) : the parking table of the permutation pi. Try:
#Ptable([4,1,2,3]);
Ptable:=proc(pi) local i,j,n,L: 
n:=nops(pi):
L:=[]:
for j from 1 to n do
for i from 0 to j-1 while pi[j-i]<=pi[j] do od:
L:=[op(L),i]:
od:
L:
end:




###start States
#Ptable(pi) : the parking table of the permutation pi. Try:
#Ptable([4,1,2,3]);
Ptable:=proc(pi) local i,j,n,L: 
n:=nops(pi):
L:=[]:
for j from 1 to n do
for i from 0 to j-1 while pi[j-i]<=pi[j] do od:
L:=[op(L),i]:
od:
L:
end:



#St1(pi): the state of the permutation pi.  Try: St1([4,3,2,1,5]);
St1:=proc(pi) 
[pi[-1],Ptable(pi)[-1]]:
end:

#St11(pi): The state of the permutation pi and the state of of its child. Try:
#St11([1,2,3,4]);
St11:=proc(pi) local n,pi1:
n:=nops(pi):
pi1:=redu([op(1..n-1,pi)]):
[St1(pi),St1(pi1)]:
end:

#StateTable(n,Patterns): outputs the list of states and the corresponding table T[state]:=set of permutations of {1,..,n} that avoid the set of patterns Patterns. 
#and a tablewith that state. Try:
#StateTable(5,{[1,2,3]});
StateTable:=proc(n,Patterns) local gu,S,gu1,s,T:
option remember:
gu:=Wilf(n,Patterns):
S:={seq(St1(gu1),gu1 in gu)}:
for s in S do
 T[s]:={}:
od:
for gu1 in gu do
 T[St1(gu1)]:=T[St1(gu1)] union {gu1}:
od:
[S,op(T)]:

end:

#PerSt(n,Patterns,st) inputs a pos. integer n and a state st, outputs the set of permutations with that state
PerSt:=proc(n,Patterns,st) local gu:
option remember:
gu:=StateTable(n,Patterns):
if not member(st,gu[1]) then
 RETURN(FAIL):
fi:
gu[2][st]:
end:

 
#EndsTable(n): a table such that T[i] is the set of permutations of {1, ...,n} that end with i. Try:
#EndsTable(6)
EndsTable:=proc(n) local gu,T,gu1,i:
option remember:
for i from 1 to n do
T[i]:={}:
od:
gu:=permute(n):
for gu1 in gu do
T[gu1[n]]:=T[gu1[n]] union {gu1}:
od:
op(T):
end:

#PerEnd(n,i): the set of permutations of {1,...n} that end  with i. Try:
#PerEnd(6,3);
PerEnd:=proc(n,i)
EndsTable(n)[i]:
end:

#Comp(n,st): compares the decomposition into states
Comp:=proc(n,st) local i,r,gu1,pi,i1,gu2,lu,lu1:
i:=st[1]:
r:=st[2]:
if r=1 then
 gu1:=PerSt(n,st):
 gu1:={seq(redu([op(1..n-1,pi)]),pi in gu1)}:
 gu2:={seq(op(PerEnd(n-1,i1)),i1=i..n-1)}:
 RETURN([gu1 minus gu2 ,gu2 minus gu1]):
fi:

 gu1:=PerSt(n,st):
 gu1:={seq(redu([op(1..n-1,pi)]),pi in gu1)}:

 lu:=StateTable(n-1,{})[1]:

 gu2:={}:

 for lu1 in lu do
  if lu1[1]<i and lu1[2]<r then
   gu2:=gu2 union PerSt(n-1,lu1):
  fi:
od:

 RETURN([gu1 minus gu2 ,gu2 minus gu1]):

end:

#Yels(n,Patterns,st): all the states of the children of the set of permutations of length n avoding the set of patterns Patterns, with the state st. Try:
#Yels(6,{[1,2,3]},[1,1]);
Yels:=proc(n,Patterns,st)  local gu,gu1:
if not member(st,StateTable(n,Patterns)[1]) then
 RETURN(FAIL):
fi:

gu:=StateTable(n,Patterns)[2][st]:
{seq(St1(redu([op(1..nops(gu1)-1,gu1)])),gu1 in gu)}:
end:

#Tot(S): Given a set of permutations S finds the sum of their CFO
Tot:=proc(S) local s:
add(CFO(s),s in S):
end:


###End States

#Start Schemes


#ani(n,i): the NUMBER of permutations of {1, ...,n} that end with i using our scheme that is extendible to couunting parking functions. Try:
#ani(5,1);
ani:=proc(n,i) local j,r:
option remember:
if n=1 then
 if i=1 then
  RETURN(1):
else
 RETURN(0):
fi:
fi:

if i>n or i<1 then
 RETURN(0):
fi:

if i=n then
 RETURN(an(n-1)):
fi:
add(add(binomial(i-1,r-1)*an(r-1)*ani(n-r , j-r) , r=1..i),j=i+1..n):
end:

#an(n): the number of permutations of length  (obviously n!) but using our scheme. Try: 
#an(7);
an:=proc(n) local i:
option remember:
if n=0 then
 1:
else
add(ani(n,i),i=1..n):
fi:
end:




#cni(n,i): the NUMBER of permutations of {1, ...,n} avoding the pattern 123 that end with i using our scheme that is extendible to couunting parking functions. Try:
#cni(5,1);
cni:=proc(n,i) local j,r:
option remember:
if n=1 then
 if i=1 then
  RETURN(1):
else
 RETURN(0):
fi:
fi:

if i>n or i<1 then
 RETURN(0):
fi:

if i=n then
 RETURN(1):
fi:
add(add(cni(n-r , j-r) , r=1..i),j=i+1..n):
end:

#cn(n): the number of permutations of length  n avoiding the pattern 123. Try
#cn(7);
cn:=proc(n) local i:
option remember:
if n=0 then
 1:
else
add(cni(n,i),i=1..n):
fi:
end:




#cpni(n,i): the NUMBER of parking functions in {1, ...,n} that produce permutations avoding the pattern 123 that end with i using our scheme that is extendible to couunting parking functions. Try:
#cpni(5,1);
cpni:=proc(n,i) local j,r:
option remember:
if n=1 then
 if i=1 then
  RETURN(1):
else
 RETURN(0):
fi:
fi:

if i>n or i<1 then
 RETURN(0):
fi:

if i=n then
 RETURN(n):
fi:
add(add(r*cpni(n-r , j-r) , r=1..i),j=i+1..n):
end:

#cpn(n): the number of parking functions that lead to permutations of length  n avoiding the pattern 123. Try
#cpn(7);
cpn:=proc(n) local i:
option remember:
if n=0 then
 1:
else
add(cpni(n,i),i=1..n):
fi:
end:



#apni(n,i): the NUMBER of parking functions of {1, ...,n} that lead to permutations that end with i using our scheme . Try:
#apni(5,1);
apni:=proc(n,i) local j,r:
option remember:
if n=1 then
 if i=1 then
  RETURN(1):
else
 RETURN(0):
fi:
fi:

if i>n or i<1 then
 RETURN(0):
fi:

if i=n then
 RETURN(n*apn(n-1)):
fi:
add(add(binomial(i-1,r-1)*r*apn(r-1)*apni(n-r , j-r) , r=1..i),j=i+1..n):
end:

#apn(n): the total number of all parking functions of {1,...,n} using our scheme. Try:
#[seq(pn(i),i=1..20)];
apn:=proc(n) local i:
option remember:
if n=0 then
  RETURN(1):
fi:
add(apni(n,i),i=1..n):
end:


#bniOld(n,i): The number of permutations of {1,2,...,n} avoding the patterns 123,213 that end in i, using our way
bniOld:=proc(n,i) local j,r:
option remember:
if n=1 then
 if i=1 then
  RETURN(1):
else
 RETURN(0):
fi:
fi:
if n=2 then
RETURN(1):
fi:

if not member(i, {1,2}) then
 RETURN(0):
fi:

add(add(binomial(i-1,r-1)*bn(r-1)*bniOld(n-r , j-r) , r=1..i),j=i+1..n):
end:

#bnOld(n): The number of permutations of {1,2,...,n} avoding the patterns 123,213, using our way
bnOld:=proc(n) local i:
option remember:
if n=0 or n=1 then
  RETURN(1):
fi:
add(bniOld(n,i),i=1..2):
end:

#bpniOld(n,i): The number of parking functionsof {1,2,...,n} that lead to permutations avoding the patterns 123,213 that end in i, using our way. Try:
#bpniOld(10,2);
bpniOld:=proc(n,i) local j,r:
option remember:
if n=1 then
 if i=1 then
  RETURN(1):
else
 RETURN(0):
fi:
fi:

if n=2 then
 if i=2 then
   RETURN(2):
 elif i=1 then
 RETURN(1):
 else
  RETURN(0):
 fi:
fi:

if not member(i, {1,2}) then
 RETURN(0):
fi:

add(add(r*binomial(i-1,r-1)*bpnOld(r-1)*bpniOld(n-r , j-r) , r=1..i),j=i+1..n):
end:


#bpnOld(n): The number of parking functions of {1,2,...,n} avoding the patterns 123,213, using our way
bpnOld:=proc(n) local i:
option remember:
if n=0 or n=1 then
  RETURN(1):
fi:

add(bpniOld(n,i),i=1..2):
end:

#end Schemes


#start 123,213 avoiding
bn:=proc(n) option remember:
if n=0 then
 1:
elif n=1 then
 1:
elif n=2 then
 2:
else
bn11(n)+bn21(n)+bn22(n):
fi:
end:

bn11:=proc(n) option remember:
bn(n-1):
end:


bn21:=proc(n) option remember:
if n=3 then
 1:
else
bn21(n-1)+bn22(n-1):
fi:
end:


bn22:=proc(n) option remember:
if n=2 then
 1:
else
bn(n-2):
fi:
end:


bpn:=proc(n) option remember:
if n=0 then
 1:
elif n=1 then
 1:
elif n=2 then
 3:
else
bpn11(n)+bpn21(n)+bpn22(n):
fi:
end:

bpn11:=proc(n) option remember:
bpn(n-1):
end:


bpn21:=proc(n) option remember:
if n=3 then
 2:
else
bpn21(n-1)+bpn22(n-1):
fi:
end:


bpn22:=proc(n) option remember:
if n=2 then
 1:
else
2*bpn(n-2):
fi:
end:


#end 123,213 avoiding


#start avoiding 231,321

#dn(n): the number of permutations of length  n avoiding the pattern 231,321. Try
#dn(7);
dn:=proc(n) local r:
option remember:
if n=0 then
 1:
elif n=1 then 
1:
elif n=2 then
 2:
else
add(dnr(n,r),r=1..n):
fi:
end:

#dnr(n,r): the number of permutations of length n avoiding the patterns 231,321
# that have state (x,r) where if if 1<=r<=n-1 then x=n-1 and if r=n then x=n
dnr:=proc(n,r) local j:
option remember:
if not (r>=1 and r<=n) then
 RETURN(FAIL):
fi:

if n=2 then
 if r=1 then
   RETURN(1):
 elif r=2 then
   RETURN(1):
 else
  RETURN(0):
 fi:
fi:

if r=1 then
 RETURN(dnr(n-1,n-1)):
fi:

if r>=2 and r<=n-1 then
 RETURN(dnr(n-1,r-1)):
fi:

if r=n then
 return(add(dnr(n-1,j),j=1..n-2)+dnr(n-1,n-1)):
fi:

end:




#dpn(n): the number of parking functions  of length  n whose outcome permutations avoid the pattern 231,321. Try
#dpn(7);
dpn:=proc(n) local r:
option remember:
if n=0 then
 1:
elif n=1 then 
1:
elif n=2 then
 3:
else
add(dpnr(n,r),r=1..n):
fi:
end:


#dpnr(n,r): the number of parking functions that lead to permutations of length n avoiding the patterns 231,321
# that have state (x,r) where if if 1<=r<=n-1 then x=n-1 and if r=n then x=n
dpnr:=proc(n,r) local j:
option remember:
if not (r>=1 and r<=n) then
 RETURN(FAIL):
fi:

if n=2 then
 if r=1 then
   RETURN(1):
 elif r=2 then
   RETURN(2):
 else
  RETURN(0):
 fi:
fi:


if r=1 then
 RETURN(dpnr(n-1,n-1)):
fi:

if r>=2 and r<=n-1 then
 RETURN(r*dpnr(n-1,r-1)):
fi:

if r=n then
 return(add(n*dpnr(n-1,j),j=1..n-2)+n*dpnr(n-1,n-1)):
fi:
end:


#Test231321a(n,i,r): tests the 231,321 scheme for states (x,r)
# where if x=n-1 then 1<=r<=n-1 and if x=n then r=n
Test231321a:=proc(n,i,r) local S, Sa,s,j:
if not (1<=r and r<=n-1 and i=n-1) and not (r=n and i=n) then
 print(`The states are (n-1,i) where 1<=i<=n-1 and (n,n)`):
 RETURN(FAIL):
fi:

#r=1 for i=n-1
if r=1 and i=n-1 then
 S:=PerSt(n,{[2,3,1],[3,2,1]},[i,r]):
 S:={seq(redu([op(1..n-1,s)]),s in S)}:
 Sa:={op(PerSt(n-1,{[2,3,1],[3,2,1]},[n-1,n-1]))}:
 RETURN(evalb(S=Sa)):
fi:

#2<=r<=n-1 for i=n-1
if 2<=r and r<=n-1 and i=n-1 then
 S:=PerSt(n,{[2,3,1],[3,2,1]},[i,r]):
 S:={seq(redu([op(1..n-1,s)]),s in S)}:
 Sa:={op(PerSt(n-1,{[2,3,1],[3,2,1]},[i-1,r-1]))}:
 RETURN(evalb(S=Sa)):
fi:

#r=n for i=n
if r=n and i=n then
 S:=PerSt(n,{[2,3,1],[3,2,1]},[i,r]):
 S:={seq(redu([op(1..n-1,s)]),s in S)}:
 Sa:={seq(op(PerSt(n-1,{[2,3,1],[3,2,1]},[i-2,j])),j=1..n-2),op(PerSt(n-1,{[2,3,1],[3,2,1]},[i-1,n-1]))}:
 RETURN(evalb(S=Sa)):
fi:

end:


#Test231321(n) : Tests the 231,321 scheme for any n
Test231321:=proc(n) local r:
{seq(Test231321a(n,n-1,r),r=1..n-1),Test231321a(n,n,n)}:
end:

#end avoiding 231,321

#start avoiding 213
#en(n): the NUMBER of permutations of {1,...,n} avoiding the pattern 213
en:=proc(n)  local i,r:
option remember:
if n=0 then
 return(1):
elif n=1 then
 RETURN(1):
elif n=2 then
 RETURN(2):
fi:
return(add(enir(n,i,1),i=1..n-1)+add(add(enir(n,i,r),r=2..i),i=2..n-1)+enir(n,n,n)):
end:

#enir(n,i,r): the NUMBER of permutations of {1,...,n} avoiding the pattern 213 with state (i,r)
enir:=proc(n,i,r) local k,j:
option remember:

if n=2 then
 if (i=1 and r=1) or (i=2 and r=2) then
  return(1):
 else
  return(0):
 fi:
fi:


if r=1 then
 return(enir(n-1,n-1,n-1)+add(add(enir(n-1,k,j),j=1..k),k=i..n-2)):
fi:
return(enir(n-1,i-1,r-1)):
end:


#epn(n): the NUMBER of parking functions that lead to permutations of {1,...,n} avoiding the pattern 213
epn:=proc(n)  local i,r:
option remember:
if n=0 then
 return(1):
elif n=1 then
 RETURN(1):
elif n=2 then
 RETURN(3):
fi:
return(add(epnir(n,i,1),i=1..n-1)+add(add(epnir(n,i,r),r=2..i),i=2..n-1)+epnir(n,n,n)):
end:


#epnir(n,i,r): the NUMBER of parking functions that lead to permutations of {1,...,n} avoiding the pattern 213
# with state (i,r)
epnir:=proc(n,i,r) local k,j:
option remember:

if n=2 then
 if i=1 and r=1 then
  return(1):
 elif i=2 and r=2 then
  return(2):
 else
  return(0):
 fi:
fi:

if r=1 then
 return(epnir(n-1,n-1,n-1)+add(add(epnir(n-1,k,j),j=1..k),k=i..n-2)):
fi:
return(r*epnir(n-1,i-1,r-1)):
end:



#Test213a(n,i,r): tests the 213 scheme for states (i,r)
# where 1<=r<=i<=n-1 and i=r=n
Test213a:=proc(n,i,r) local S, Sa,s,k,j:
if not (1<=r and r<=i and i<=n-1) and not (i=n and r=n) then
 RETURN(FAIL):
fi:

#(1<=i and i<=n-2) and r=1
if r=1 and 1<=i and i<=n-1 then
 S:=PerSt(n,{[2,1,3]},[i,1]):
 S:={seq(redu([op(1..n-1,s)]),s in S)}:
 Sa:={seq(seq(op(PerSt(n-1,{[2,1,3]},[k,j])),j=1..k),k=i..n-2),op(PerSt(n-1,{[2,1,3]},[n-1,n-1]))}:
 RETURN(evalb(S=Sa)):
else
 S:=PerSt(n,{[2,1,3]},[i,r]):
 S:={seq(redu([op(1..n-1,s)]),s in S)}:
 Sa:=PerSt(n-1,{[2,1,3]},[i-1,r-1]):
 RETURN(evalb(S=Sa)):
fi:

end:


#Test213(n) : Tests the 213 scheme for any n
Test213:=proc(n) local i,r:
{seq(seq(Test213a(n,i,r),r=1..i),i=1..n-1),Test213a(n,n,n)}:
end:

#end avoiding 213


#start avoiding 321

#fn(n): the NUMBER of permutations of {1,...,n} avoiding the pattern 321
fn:=proc(n)  local i,r:
option remember:
if n=0 then
 return(1):
elif n=1 then
 RETURN(1):
elif n=2 then
 RETURN(2):
fi:
return(add(add(fnir(n,i,r),r=2..i),i=2..n-1)+fnir(n,1,1)+add(fnir(n,i,1),i=2..n-2)+fnir(n,n-1,1)+fnir(n,n,n)
):
end:


#fnir(n,i,r): the NUMBER of permutations of {1,...,n} avoiding the pattern 321 with state (i,r)
fnir:=proc(n,i,r) local k,j:
option remember:

if n=2 then
 if i=1 and r=1 then
  return(1):
 elif i=2 and r=2 then
  return(1):
 fi:
fi:

if (1<=i and i<=n-2) and r=1 then
 return(add(fnir(n-1,i,j),j=1..i)):
elif (2<=r and r<=i and i<=n-1) then
 return(add(fnir(n-1,k,r-1),k=r-1..i-1)):
elif i=n-1 and r=1 then
 return(fnir(n-1,n-1,n-1)):
elif i=n and r=n then
 return(add(add(fnir(n-1,k,j),j=1..k),k=1..n-2)+fnir(n-1,n-1,n-1)):
fi:
end:


#fpn(n): the NUMBER of parking functions that lead to permutations of {1,...,n} avoiding the pattern 321
fpn:=proc(n)  local i,r:
option remember:
if n=0 then
 return(1):
elif n=1 then
 RETURN(1):
elif n=2 then
 RETURN(3):
fi:
return(add(add(fpnir(n,i,r),r=2..i),i=2..n-1)+fpnir(n,1,1)+add(fpnir(n,i,1),i=2..n-2)+fpnir(n,n-1,1)+fpnir(n,n,n)
):
end:


#fpnir(n,i,r): the NUMBER of parking functions that lead to permutations of {1,...,n} avoiding the pattern 321
# with state (i,r)
fpnir:=proc(n,i,r) local k,j:
option remember:

if n=2 then
 if i=1 and r=1 then
  return(1):
 elif i=2 and r=2 then
  return(2):
 fi:
fi:


if (1<=i and i<=n-2) and r=1 then
 return(add(((n-1)/j)*fpnir(n-1,i,j),j=1..i)):
elif (2<=r and r<=i and i<=n-1) then
 return(r*add(fpnir(n-1,k,r-1),k=r-1..i-1)):
elif i=n-1 and r=1 then
 #multiply by r=1
 return(fpnir(n-1,n-1,n-1)):
elif i=n and r=n then
 #multiply by r=n
 return(n*(add(add(fpnir(n-1,k,j),j=1..k),k=1..n-2)+fpnir(n-1,n-1,n-1))):
fi:
end:


#Test321a(n,i,r): tests the 321 scheme for states (i,r)
# where 1<=r<=i<=n-1 and i=r=n
Test321a:=proc(n,i,r) local S, Sa,s,k,j:
if not (1<=r and r<=i and i<=n-1) and not (i=n and r=n) then
 RETURN(FAIL):
fi:

#(1<=i and i<=n-2) and r=1
if r=1 and 1<=i and i<=n-2 then
 S:=PerSt(n,{[3,2,1]},[i,1]):
 S:={seq(redu([op(1..n-2,s),s[n]]),s in S)}:
 Sa:={seq(op(PerSt(n-1,{[3,2,1]},[i,j])),j=1..i)}:
 RETURN(evalb(S=Sa)):
fi:

#(2<=r and r<=i and i<=n-1)
if 2<=r and r<=i and i<=n-1 then
 S:=PerSt(n,{[3,2,1]},[i,r]):
 S:={seq(redu([op(1..n-1,s)]),s in S)}:
 Sa:={seq(op(PerSt(n-1,{[3,2,1]},[k,r-1])),k=r-1..i-1)}:
 RETURN(evalb(S=Sa)):
fi:

if i=n-1 and r=1 then
 S:=PerSt(n,{[3,2,1]},[i,r]):
 S:={seq(redu([op(1..n-1,s)]),s in S)}:
 Sa:=PerSt(n-1,{[3,2,1]},[n-1,n-1]):
 RETURN(evalb(S=Sa)):
fi:


if i=n and r=n then
 S:=PerSt(n,{[3,2,1]},[i,r]):
 S:={seq(redu([op(1..n-1,s)]),s in S)}:
 Sa:={seq(seq(op(PerSt(n-1,{[3,2,1]},[k,j])),j=1..k),k=1..n-2),op(PerSt(n-1,{[3,2,1]},[n-1,n-1]))}:
 RETURN(evalb(S=Sa)):
fi:
end:


#Test321(n) : Tests the 321 scheme for any n
Test321:=proc(n) local i,r:
{seq(seq(Test321a(n,i,r),r=1..i),i=1..n-1),Test321a(n,n,n)}:
end:

#end avoiding 321

#start Avoiding 132 (and avoiding 231)

#BreakUp(pi): Given a permutation pi of length n, If [pi1,pi2] are the reductions of those that come before the n and the one that comes after n
#outputs the location of the i and CFO(pi)/(CFO(pi1)*CFO(pi2)).
#Try:
#BreakUp([1,5,2,3,4]);
BreakUp:=proc(pi) local n,i,pi1,pi2:
n:=nops(pi):

for i from 1 while pi[i]<>n do od:

pi1:=redu([op(1..i-1,pi)]):
pi2:=redu([op(i+1..n,pi)]):

[i,CFO(pi)/CFO(pi1)/CFO(pi2)]:
end:

#gn(n): the number  of n-parmutations that avoid 132 (also the number that 231)
#[seq(gn(i),i=1..20)];
gn:=proc(n) local i:
option remember:
if n=0 or n=1 then
 RETURN(1):
else

add(gn(i-1)*gn(n-i),i=1..n):
fi:
end:

#gpn(n): the number parking functions of length n leading to parmutations that avoid 132 and also the number that avoid 231. Try:
#[seq(gpn(i),i=1..20)];
gpn:=proc(n) local i:
option remember:
if n=0 or n=1 then
 RETURN(1):
else

add(i*gpn(i-1)*gpn(n-i),i=1..n):
fi:
end:
#End Avoiding 132 (and avoiding 231)




#start Avoiding 132 and 231


#hn(n): the number of permutations of length n avoiding both 132 and 231
#[seq(hn(i),i=1..20)];
hn:=proc(n)
option remember:
if n=0 or n=1 then
 RETURN(1):
else

hn(n-1)+hn(n-1):
fi:
end:


#hpn(n): the number parking functions of length n leading to parmutations that avoid 132 and also the number that avoid 231. Try:
#[seq(hpn(i),i=1..20)];
hpn:=proc(n) 
option remember:
if n=0 or n=1 then
 RETURN(1):
else

hpn(n-1)+n*hpn(n-1):
fi:
end:



#End Avoiding 132 and 231





#start Avoiding 312
#TO BE CONTINUED
#End Avoiding 312


#WilfTailTable(n,Patterns,r): all the tails of size r of Wilf(n,Patterns), followed by the table. Try:
#WilfTailTable(7,{[3,1,2]},2);
WilfTailTable:=proc(n,Patterns,r) local gu,gu1,mu,mu1,T:
option remember:
mu:=Wilf(n,Patterns):
if r>n then
 RETURN(FAIL):
fi:

gu:={seq([op(n-r+1..n,mu1)], mu1 in mu)}:

for gu1 in gu do
 T[gu1]:={}:
od:

for mu1 in mu do
T[[op(n-r+1..n,mu1)]]:=T[[op(n-r+1..n,mu1)]] union {mu1}:
od:
gu,op(T):

end:

#WilfTail(n,Patterns,zanav): all the members of Wilf(n,Patterns) that end in zanav. Try:
#WilfTail(7,{[3,1,2]},[1,2]);
WilfTail:=proc(n,Patterns,zanav) local r,gu:
r:=nops(zanav):
gu:=WilfTailTable(n,Patterns,r):
if not member(zanav,gu[1]) then
 {}:
else
gu[2][zanav]:
fi:
end:



#IsRevDel1(n,Patterns,zanav,k): Is the k-th entry of zanav reversely deletable for permutations of length n that avoid the set of patterns Patterns and that end in zanav? Try
#IsRevDel1(8,{[2,1,3]},[5,2],2);
IsRevDel1:=proc(n,Patterns,zanav,k) local gu,z,gu1,lu,akha:
gu:=WilfTail(n,Patterns,zanav):
z:=nops(zanav):
if gu=FAIL then
  RETURN(FAIL):
fi:

if not (k>=1 and k<=z) then
 RETURN(FAIL):
fi:
gu:={seq(redu([op(1..n-z+k-1,gu1),op(n-z+k+1..n,gu1)]), gu1 in gu)}:

if z=1 then
lu:=Wilf(n-1,Patterns):
RETURN(evalb(gu=lu)):
else

akha:={seq([op(n-z+1..n-1,gu1)],gu1 in gu)}:
if nops(akha)<>1 then
 RETURN(FAIL):
fi:
akha:=akha[1]:
lu:=WilfTail(n-1,Patterns,akha):
evalb(gu=lu):
fi:
end:

#RevDelSet1(n,Patterns,r,k): The subset of WilfTailTable(n,Patterns,r)[1] that k<=r is reversely reducible. Try:
#RevDelSet1(8,{[1,2,3]},2,1);
RevDelSet1:=proc(n,Patterns,r,k) local mu,mu1,gu:

mu:=WilfTailTable(n,Patterns,r)[1]:

gu:={}:

for  mu1 in mu do 
 if IsRevDel1(n,Patterns,mu1,k) then
  gu:=gu union {mu1}:
 fi:
od:

gu:
end:

   
#IsHope1(n,Patterns,r): Is there hope for a scheme of depth r for the set of Patterns. Try:
#IsHope1(8,{[1,2,3]},2);
IsHope1:=proc(n,Patterns,r) local gu,k:
gu:=WilfTailTable(n,Patterns,r)[1]:
evalb({seq(op(RevDelSet1(n,Patterns,r,k)),k=1..r)}=gu);
end:


#DomainWilfTable(n,Patterns,r): The table that for each permutation of r gives you all tails of length r of members of Wilf(n,Patterns) that reduce to it. Try:
#DomainWilfTable(8,{[1,2,3]},2);
DomainWilfTable:=proc(n,Patterns,r) local gu,gu1,T,mu,mu1:
option remember:

gu:=permute(r):

for gu1 in gu do
 T[gu1]:={}:
od:

mu:=WilfTailTable(n,Patterns,r)[1]:

for mu1 in mu do
 T[redu(mu1)]:= T[redu(mu1)] union {mu1}:
od:
op(T):
end:



#DomainWilf(n,Patterns,sig): inputs a pos. integer n, a set of Patterns, Patterns, and a permutation sig, outputs the set of tails
#in Wilf(n,Patterns) that reduce to sig. Try:
#DomainWilf(7,{[1,2,3]},[1,2]);
DomainWilf:=proc(n,Patterns,sig)
option remember:
DomainWilfTable(n,Patterns,nops(sig))[sig]:
end:






#IsRevDel(n,Patterns,sig,k): Is the k-th entry of all possible tails of length nops(sig) that reduce to pi Reversely deletable. Try:
#IsRevDel(8,{[1,2,3]},[2,1],2);
IsRevDel:=proc(n,Patterns,sig,k) local gu,gu1:

gu:=DomainWilf(n, Patterns, sig):
evalb({seq(IsRevDel1(n,Patterns,gu1,k),gu1 in gu)}={true}):
end:



#ExtendScheme(n,Patterns, Sc): Given a partial scheme Sc=[RevR,YTD] takes YTD[1] and sees which of its children can go to RV and which go to YTD to the end of the queue. Try:
#ExtendScheme(8,{[1,2,3]},[[],[[1]] ]);

ExtendScheme:=proc(n,Patterns,Sc) local RevD, YTD,sig,S,i,r,j1,k,ku:
RevD:=Sc[1]:
YTD:=Sc[2]:

if YTD=[] then
  RETURN(RevD):
fi:

sig:=YTD[1]:

YTD:=[op(2..nops(YTD),YTD)]:

if member(true,{seq(IsRevDel(n,Patterns,sig,k),k=1..nops(sig))}) then
 RETURN(FAIL):
fi:

r:=nops(sig)+1:

S:={seq([i, op(subs({seq(j1=j1+1,j1=i..r-1)},sig))],i=1..r)}:

for sig in S do
 ku:={}:
 for k from 1 to nops(sig) do
  if IsRevDel(n,Patterns,sig,k) then
   ku:=ku union {k}:
  fi:
 od:
if ku<>{} then
RevD:=[op(RevD),[sig,ku]]:
else
YTD:=[op(YTD),sig]:
fi:
od:

[RevD,YTD]:


end:


#FixedSet(S): Given a list S of vectors of the same size, say, k, outputs
#the vector of length k, whose i-th component is 0 if they are not all the same
#and the common value if they are. Try:
#FixedSet({[1,2],[1,3],[1,4]});
FixedSet:=proc(S) local s,k,i,V,lu:

if S={} then
 RETURN(FAIL):
fi:

if nops({seq(nops(s), s in S)})<>1 then
  RETURN(FAIL):
fi:
k:=nops(S[1]):

V:=[]:

for i from 1 to k do

 lu:={seq(s[i],s in S)}:
  if nops(lu)=1 then
   V:=[op(V),lu[1]]:
  else
   V:=[op(V),0]:
  fi:
od:
V:
end:

#FindScheme1(n,Patterns,K): Tries to find a scheme for the set of patterns Patterns up to length K. Try:
#FindScheme1(8,{[1,2,3]},4); -1 means n

FindScheme1:=proc(n,Patterns,K) local gu,i1,lu,Gu,i:
gu:=[[],  [[1]]]:

while max(seq(nops(gu[1][i1][1]),i1=1..nops(gu[1])))<=K and gu[2]<>[] do
gu:=ExtendScheme(n,Patterns,gu):
od:

if gu[2]<>[] then
 RETURN(FAIL)
fi:

if max(seq(nops(gu[1][i1][1]),i1=1..nops(gu[1])))>K then
 RETURN(FAIL):
fi:

gu:=gu[1]:

Gu:=[]:

for i from 1 to nops(gu) do
lu:=FixedSet(DomainWilf(n, Patterns, gu[i][1])):
if lu=FAIL then
 RETURN(FAIL):
else
lu:=subs(n=-1,lu):
Gu:=[op(Gu),[op(gu[i]),lu]]:
fi:
od:

Gu:
end:




#FindPreScheme(n,r,Patterns,K): finds a pre-scheme of depth <=K by starting at n, and then, doing n+1.n+2, ..., n+r and if they all agree then
#it outputs the common scheme. Try:
#FindPreScheme(6,2,{[1,2,3]},2);
FindPreScheme:=proc(n,r,Patterns,K) local lu,n1:
option remember:
for n1 from n to n+r do
 lu[n1]:=FindScheme1(n1,Patterns,K):
 if lu[n1]=FAIL then
    RETURN(FAIL):
 fi:
od:

if nops({seq(lu[n1],n1=n..n+r)})=1 then
 RETURN(lu[n]):
else
 RETURN(FAIL):
fi:
end:


#Kid(pi,k): inputs  a permutation pi of length n=nops(pi), and an integer k from 1 to n+1 outputs the permutation
#of length n+1 that starts with k and such that the last n entries reduce to k. Try:
#Kid([2,1,3],2);
Kid:=proc(pi,k) local n,i:
n:=nops(pi):
[k,op(subs({seq(i=i+1,i=k..n)},pi))]:
end:

#FindSchemeOld(n,r,Patterns,K): Tries to to find a suffix-scheme of depth <=K for the set of permutations avoiding the set Patterns. It tries to find a pre-scheme using date for n,n+1, ...n+r-1
#if successful, it converts it into the format [Expa,Red, RedTable] where for any member sigma of Red, RedTable[sigma]=[Domain,RedSet]. Try:
#FindSchemeOld(6,2,{[1,2,3]},2);
FindSchemeOld:=proc(n,r,Patterns,K) local gu,Redu,i,Expa,ToDo,pi,pi1,k,T1:
gu:=FindPreScheme(n,r,Patterns,K):
if gu=FAIL then
 RETURN(FAIL):
fi:
Redu:={seq(gu[i][1],i=1..nops(gu))}:


Expa:={[1]}:

ToDo:={[1]}:

while ToDo<>{} do
pi:=ToDo[1]:
ToDo:=ToDo minus {pi}:

for k from 1 to nops(pi)+1 do
pi1:=Kid(pi,k):

if not member(pi1,Redu) then
 Expa:=Expa union {pi1}:
 ToDo:=ToDo union {pi1}:
fi:
od:
od:

if Expa union {seq(seq(Kid(pi,k),k=1..nops(pi)+1), pi in Expa)}<>Expa union Redu then
print(Expa union {seq(seq(Kid(pi,k),k=1..nops(pi)+1), pi in Expa)}, Expa union Redu):
 RETURN(FAIL):
fi:


for i from 1 to nops(gu) do
T1[gu[i][1]]:=[gu[i][2],gu[i][3]]:
od:

[Redu,Expa,op(T1)]:


end:




#EvalSchemeOld(S,n,L): If S is the enumeration scheme that counts the Wilf class Patterns, and n is a positive integer, and L is a list of distinct integers between 1 and n, outputs the number of permutations of length n that end with L
EvalSchemeOld:=proc(S,n,L) local pi, Surv,Avel,i,R,V,L1:
option remember:


if n=0 then
 if L=[] then
  RETURN(1):
 else
  RETURN(0):
fi:
fi:

 
if L=[] then
 RETURN(add(EvalSchemeOld(S,n,[i]),i=1..n)):
fi:

if n=1 then
 if L=[1] then
   RETURN(1):
 else
  RETURN(0):
 fi:
fi:

if nops(L)=n then
 RETURN(1):
fi:

pi:=redu(L):

Avel:={seq(i,i=1..n)} minus {op(L)}:

if member(pi,S[2]) then
 RETURN(add(EvalSchemeOld(S,n,[i,op(L)]),i in Avel)):
fi:

V:=S[3][pi][2]:

for i from 1 to nops(L) do
 if V[i]=1 and L[i]<>1 then
    RETURN(0):
 fi:
if V[i]=-1 and L[i]<>n then
  RETURN(0):
fi:
od:

R:=S[3][pi][1]:

L1:=[]:

Surv:={seq(i,i=1..n)}:

for i from 1 to nops(L) do
 if not member(i,R) then
  L1:=[op(L1),L[i]]:
 else
  Surv:=Surv minus {L[i]}:
 fi:
od:
Surv:=sort(convert(Surv,list)):
L1:=subs({seq(Surv[i]=i,i=1..nops(Surv))},L1):
RETURN(EvalSchemeOld(S,n-nops(R),L1)):
end:

 

 



#WilfSeqVS(n,r,Patterns,K,N): Tries to find a scheme via FindScheme(n,r,Patterns,K) and if found used it to compute WilfSeq(Patterns,N). If does not agree for the first 7 terms returns FAIL. Try:
#WilfSeqVS(6,2,{[1,2,3]},2,20);
WilfSeqVS:=proc(n,r,Patterns,K,N) local gu,i:
gu:=FindScheme(n,r,Patterns,K):
if gu=FAIL then
 print(`No scheme found`):
 RETURN(FAIL):
fi:

if [seq(EvalScheme(gu,i,[]),i=1..7)]<>WilfSeq(Patterns,7) then
 print(`The scheme didn't work out`):
 RETURN(FAIL):
fi:

 [seq(EvalScheme(gu,i,[]),i=1..N)]:
end:







#FindScheme(n,r,Patterns,K): Tries to to find a suffix-scheme of depth <=K for the set of permutations avoiding the set Patterns. It tries to find a pre-scheme using date for n,n+1, ...n+r-1
#if successful, it converts it into the format [Expa,Red, RedTable] where for any member sigma of Red, RedTable[sigma]=[Domain,RedSet]. Try:
#FindScheme(6,2,{[1,2,3]},2);
FindScheme:=proc(n,r,Patterns,K) local gu,Redu,i,Expa,ToDo,pi,pi1,k,T1,K1,INI, INItable,ka,n1,lu,i1,lu1,ini1:
gu:=FindPreScheme(n,r,Patterns,K):
if gu=FAIL then
 RETURN(FAIL):
fi:
Redu:={seq(gu[i][1],i=1..nops(gu))}:


Expa:={[1]}:

ToDo:={[1]}:

while ToDo<>{} do
pi:=ToDo[1]:
ToDo:=ToDo minus {pi}:

for k from 1 to nops(pi)+1 do
pi1:=Kid(pi,k):

if not member(pi1,Redu) then
 Expa:=Expa union {pi1}:
 ToDo:=ToDo union {pi1}:
fi:
od:
od:

if Expa union {seq(seq(Kid(pi,k),k=1..nops(pi)+1), pi in Expa)}<>Expa union Redu then
print(Expa union {seq(seq(Kid(pi,k),k=1..nops(pi)+1), pi in Expa)}, Expa union Redu):
 RETURN(FAIL):
fi:


for i from 1 to nops(gu) do
T1[gu[i][1]]:=[gu[i][2],gu[i][3]]:
od:

[Redu,Expa,op(T1)]:




K1:=max(seq(nops(ka),ka in Redu)):

INI:={}:

for n1 from 1 to K1 do
for i1 from 1 to n1 do
lu:=convert(permute(n1,i1),set):
INI:=INI union {seq([n1,lu1],lu1 in lu)}:
od:
od:



for ini1 in INI do

INItable[ini1]:=nops(WilfTail(ini1[1],Patterns,ini1[2])):

od:

[Redu,Expa,op(T1),INI, op(INItable)]:


end:



#EvalScheme(S,n,L): If S is the enumeration scheme that counts the Wilf class Patterns, and n is a positive integer, and L is a list of distinct integers between 1 and n, outputs the number of permutations of length n that end with L
EvalScheme:=proc(S,n,L) local pi, Surv,Avel,i,R,V,L1:
option remember:


 
if L=[] then
 RETURN(add(EvalScheme(S,n,[i]),i=1..n)):
fi:

if member([n,L],S[4]) then
 RETURN(S[5][[n,L]]):
fi:


pi:=redu(L):

Avel:={seq(i,i=1..n)} minus {op(L)}:

if member(pi,S[2]) then
 RETURN(add(EvalScheme(S,n,[i,op(L)]),i in Avel)):
fi:

V:=S[3][pi][2]:

for i from 1 to nops(L) do
 if V[i]=1 and L[i]<>1 then
    RETURN(0):
 fi:
if V[i]=-1 and L[i]<>n then
  RETURN(0):
fi:
od:

R:=S[3][pi][1]:

L1:=[]:

Surv:={seq(i,i=1..n)}:

for i from 1 to nops(L) do
 if not member(i,R) then
  L1:=[op(L1),L[i]]:
 else
  Surv:=Surv minus {L[i]}:
 fi:
od:
Surv:=sort(convert(Surv,list)):
L1:=subs({seq(Surv[i]=i,i=1..nops(Surv))},L1):
RETURN(EvalScheme(S,n-nops(R),L1)):
end: