######################################################################
##ParkingDyckWilf.txt: Save this file as ParkinDyckgWilf.txt.        #
#To use it, stay in the                                              #
##same directory, get into Maple (by typing: maple <Enter> )         #
##and then type:  read `ParkingDyckWilf.txt` : <Enter>               #
##Then follow the instructions given there                           #
##                                                                   #
##Written by Lucy Martinez and Doron Zeilberger, Rutgers University  #
#######################################################################
#Created: June 2025.
print(`This is ParkingDyckWilf.txt, a Maple package to study Pattern avoiding parking functions according to the Dyck convention`):
print(`It is one of the packages in an article by Lucy Martinez and Doron Zeilberger`):
print(`Auomated Counting of Parking Wilf Classes`):
print(`This Maple package, as well as the article, are `):
print(`available from:`):
print(` http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/pwilf.html `):
lprint(``):
print(`Please report bugs to DoronZeil@gmail.com `):
print(``):
print(`-----------------------------`):

lprint(``):
 print(`For a list of the procedures type ezra(), for help with`):
 print(`a specific procedure, type ezra(procedure_name)`):
print(`-----------------------------`):

print(`-----------------------------`):
 print(``):
lprint(``):
 print(`For a list of the supporting procedures type ezra1(), 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: CS, GFP, MulTable `):
else
ezra(args):
fi:

end:



ezra:=proc()

if args=NULL then
 print(`The main procedures are: `):
 print(`  BWilf, BWilfSeq, Mul, PP, PtoP, Wilf`):




elif nops([args])=1 and op(1,[args])=BWilfSeq then
print(`BWilfSeq(Patterns,N): The first N terms of the sequence enumerating parking functions whose permutations accoring to the Blcok Dyck version avoids the set of patterns.`):
print(`Warning; BY BRUTE FORCE. Try: `):
print(`BWilfSeq({[1,2,3],[1,3,2]},7);`):

elif nops([args])=1 and op(1,[args])=BWilf then
print(`BWilf(Patterns,n): The number of parking functions that yield permutations avoiding the patterns in the set of patterns Patterns according to the Dyck Block interpretation.`):
print(`Warning; BY BRUTE FORCE. Try: `):
print(`BWilf({[1,2,3],[1,3,2]},7);`):


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

elif nops([args])=1 and op(1,[args])=GFP then
print(`GFP(n,P): inputs a positive integer n, and a variable name P, outputs add(P[PtoP(L)], L in PP(n)):`):


elif nops([args])=1 and op(1,[args])=Mul then
print(`Mul(pi): The number of parking functions that lead to the permutation pi via the block Dyck  interpration . Try:`):
print(`Mul([2,1,4,3]);`):

elif nops([args])=1 and op(1,[args])=MulTable then
print(`MulTable(n): a table of the multiplicity (according to the block approach) for permutations of length n. Try:`):
print(`MulTable(5);`):


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

elif nops([args])=1 and op(1,[args])=PtoP then
print(`PtoP(L): inputs a parking function, outputs the corresponding permutation (using the block Dyck interpretation). Try:`):
print(`PtoP([3,1,1,2,2]);`):

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


else
print(`There is no ezra for`,args):
fi:
end:
#########################


with(combinat):





##############################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:

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


#BWilfSeq(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:
#BWilfSeq({[1,2,3],[1,3,2]},6);
BWilfSeq:=proc(Patterns, N) local n; seq(BWilf(Patterns,n), n = 1 .. N) end:

#end from Wilf

#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:



#PtoP(L): inputs a parking function, outputs the corresponding permutation (using the block Dyck interpretation). Try:
#PtoP([3,1,1,2,2]);
PtoP:=proc(L) local n,i,T:
n:=nops(L):

for i from 1 to n do
 T[i]:={}:
od:

for i from 1 to n do
T[L[i]]:=T[L[i]] union {i}:
od:

[seq(op(sort(convert(T[i],list))),i=1..n)]:

end:


#GFP(n,P): add(P[PtoP(L)], L in PP(n)):
GFP:=proc(n,P) local gu,L:
option remember:

gu:=PP(n):
add(P[PtoP(L)], L in gu):
end:


#MulTable(n): a table of the multiplicity (according to the block approach) for permutations of length n
MulTable:=proc(n) local P,gu,mu,mu1,T:
option remember:
gu:=GFP(n,P):
mu:=permute(n):
for mu1 in mu do
 T[mu1]:=coeff(gu,P[mu1],1):
od:
op(T):
end:

#Mul(pi): The number of parking functions that lead to the permutation pi via the block Dyck  interpration . Try:
#Mul([2,1,4,3]);
Mul:=proc(pi) local P:
option remember:
if nops(pi)<=7 then
  RETURN(MulTable(nops(pi))[pi]):
else
coeff(GFP(nops(pi),P),P[pi],1):
fi:
end: