#CATALAN: A Maple program supplement to Doron Zeilberger's
#paper `Catalan strikes again (and again)*'
 
print(`This is Catalan, a Maple program supplement to Doron Zeilberger's`):
print(`paper "Catalan Strikes again" `):
print(`For help type ezra(), for specific help, type ezra(proc_name)`):
 
 
 
#Bal(m,n) gives the set of lattice paths with m 0's and n 1's
 
Bal:=proc(m,n)
local gu1,gu2,gu,i:
option remember:
 
gu:={}:
if m=0 and n=0 then
 RETURN({[]}):
fi:
 
if n=0 and m>0 then
  gu1:=Bal(m-1,n):
 
  for i from 1 to nops(gu1) do
    gu:=gu union {[op(op(i,gu1)),B]}:
  od:
 RETURN(gu):
fi:
 
if m=n then
   gu1:=Bal(m,n-1):
 
    
  for i from 1 to nops(gu1) do
    gu:=gu union {[op(op(i,gu1)),E]}:
  od:
 
 RETURN(gu):
fi:
 
   gu1:=Bal(m,n-1):
 
    
  for i from 1 to nops(gu1) do
    gu:=gu union {[op(op(i,gu1)),E]}:
  od:
 
 
   gu2:=Bal(m-1,n):
 
    
  for i from 1 to nops(gu2) do
    gu:=gu union {[op(op(i,gu2)),B]}:
  od:
 
 RETURN(gu):
end:
 
IP:=proc(n)
local gu1,gu,i:
 
if n<1 then
 ERROR(`n must be >=1`):
fi:
 
gu1:=Bal(n-1,n-1):
gu:={}:
 
for i from 1 to nops(gu1) do
 
gu:=gu union {[B,op(op(i,gu1)),E]}:
 
od:
 
gu:
 
end:
 
 
#sigma inputs an irreducible legal parenthesing and outputs a
#Stanley tree
 
sigma:=proc(ilp)
local k,r,l,Il,Jl,i,v,Edg,n:
 
n:=nops(ilp)/2:
 
l:=0:
r:=0:
 
for i from 1 to n do
 
 if op(2*i-1,ilp)=B and op(2*i,ilp)=E then
   v[i]:=0:
 fi:
 if op(2*i-1,ilp)=E and op(2*i,ilp)=B then
   v[i]:=1:
 fi:
 
 if op(2*i-1,ilp)=B and op(2*i,ilp)=B then
   v[i]:=2:
  l:=l+1:
  Il[l]:=i:
 fi:
 
 if op(2*i-1,ilp)=E and op(2*i,ilp)=E then
   v[i]:=2:
   r:=r+1:
   Jl[r]:=i:
 fi:
 
od:
 
if r<>l then
 ERROR(`Input must have been bad`):
fi:
 
 
Edg:={}:
 
for i from 1 to r do
 Edg:=Edg union {{Il[i],Jl[i]}}:
od:
 
for i from 1 to n do
    if v[i]=0 then
        for k from 1 to r do
          if Il[k]<i and Jl[k]>i then
               Edg:=Edg union {{Il[k],i}}:
               break:
           fi:    
        od:
    fi:
 
 
    if v[i]=1 then
       
               for k from r by -1 to 1 do
                if Il [k]<i and Jl[k]>i then
                 Edg:=Edg union {{i,Jl[k]}}:
                 break:
                fi:
               od:
   fi:
 
od:
 
for k from 1 to r-1 do
 Edg:=Edg union {{Il[k+1],Jl[k]}}:
od:
 
Edg:
 
end:
 
 
 
 
#pi inputs a Stanley tree on n vertices and outputs an irred.
#legal paraenthesing
 
pi:=proc(T)
local edg,n,m1,l1, i,j,r,k,lp,lp1,Iset, Jset, bud, i1, 
      lu, m2, v:
 
n:=nops(T)+1:
j[0]:=0:
i[1]:=1:
 
for r from 1 to n do
  for m1 from n by -1 to 1 do
    if member({i[r],m1},T) then
        j[r]:=m1:
        break:
     fi:
   od:
 
   if j[r]=n then
        k:=r:
        break:
   fi:
 
   
  for m1 from i[r]+1 to n do
      lu:=0:
        for m2 from j[r]+1 to n do
           if member({m1,m2},T) then
               lu:=1:
               break:
           fi:
         od:
     if lu=1 then
           i[r+1]:=m1:
           break:
     fi:
  od:
od:
 
Iset:={}:
Jset:={}:
 
for r from 1 to k do
 Iset:=Iset union {i[r]}:
 Jset:=Jset union {j[r]}:
od:
 
lp:=[seq(l1,l1=1..n)]:
 
for v from 1 to n do
 if member(v,Iset) then
  lp:=[op(1..v-1,lp),[B,B],op(v+1..n,lp)]:
 
 elif member(v,Jset) then
  lp:=[op(1..v-1,lp),[E,E],op(v+1..n,lp)]:
 
 else
 
 
 for m1 from 1 to n-1 do
   edg:=op(m1,T):
   if member(v,edg) then
       bud:=edg minus {v}:
       bud:=op(1,bud):
        if member(bud,Iset) then
             lp:=[op(1..v-1,lp),[B,E],op(v+1..n,lp)]:
             break:
        fi:
 
        if member(bud,Jset) then
             lp:=[op(1..v-1,lp),[E,B],op(v+1..n,lp)]:
             break:
        fi:
    fi:
  od:
 
fi:
od:
 
 
lp1:=[]:
 
for i1 from 1 to n do
 lp1:=[op(lp1),op(op(i1,lp))]:
od:
 
lp1:
end:
 
sigmaall:=proc(n)
local i,gu,mu,ku:
 
mu:={}:
 
print(`Here is how sigma acts on all the possible irred. legal para. of`):
print(`size n`):
 
gu:=IP(n):
 
for i from 1 to nops(gu) do
 ku:=sigma(op(i,gu)):
 print(`sigma(`,op(i,gu),`)=`,ku):
od:
end:
 
 
piall:=proc(n)
local i,gu,mu,ku:
 
mu:={}:
 
print(`Here is how pi acts on all the possible  Stanley trees `):
print(`size n`):
 
gu:=stanley(n):
 
for i from 1 to nops(gu) do
 ku:=pi(op(i,gu)):
 print(`pi(`,op(i,gu),`)=`,ku):
od:
end:
 
 
stanley:=proc(n)
local i,gu,mu,ku:
 
mu:={}:
 
#print(`Here is the set of all Stanley trees of`):
print(`size n`):
 
gu:=IP(n):
 
for i from 1 to nops(gu) do
 ku:=sigma(op(i,gu)):
mu:=mu union {ku}:
od:
mu:
end:
 
 
pisigmaall:=proc(n)
local i,gu,mu,ku:
 
mu:={}:
 
print(`Here is how pi(sigma) acts on all the possible irred. legal para. of`):
print(`size n`):
 
gu:=IP(n):
 
for i from 1 to nops(gu) do
 ku:=pi(sigma(op(i,gu))):
 print(`pi(sigma(`,op(i,gu),`))=`,ku):
od:
end:
 
 
sigmapiall:=proc(n)
local i,gu,mu,ku:
 
mu:={}:
 
print(`Here is how sigma(pi) acts on all the possible irred. legal para. of`):
print(`size n`):
 
gu:=IP(n):
 
for i from 1 to nops(gu) do
  
 ku:=sigma(op(i,gu)):
 print(`sigma(pi(`, ku ,`))=`, sigma(pi(ku))):
od:
end:
 
 
ezra:=proc()
if args=NULL then
print(`Version of  Jan. 31, 1995. Written by D, Zeilberger`):
print(`This small package contains the bijections pi, described in `):
 print(` the paper "Catalan Strikes again (and again)" by D. Zeilberger `):
 print(`as well as its inverse sigma .Contains the following procedures`):
 print(` 'pi','sigma','IP','sigmapiall','pisigmall','sigmaall','piall'`):
 print(`'stanley'`):
 print(`For help with a specific prodecure, type ezra(procedure_name)`):
fi:
 
 
 
if nops([args])=1 and op(1,[args])=`pi` then
 print(`pi(T): Inputs a Stanley tree T on the vertices 1, ... ,n  `):
 print(`that should be given as a set of edges, like {{1,2},{1,3}}.`):
 print(`outputs an irred. legal parenthesing, using the bijection pi`):
 print(`described in the paper`):
fi:
 
 
if nops([args])=1 and op(1,[args])=`sigma` then
 print(`sigma(ILP): Inputs an irred. legal paranethesing, using B and E  `):
 print(`outputs a Stanley tree using the bijection sigma `):
 print(`mentioned in the paper`):
fi:
 
 
if nops([args])=1 and op(1,[args])=`sigmapiall` then
 print(`sigmapiall(n): Inputs a positive integer n  `):
 print(`outputs  sigmapi(T) for all the Stanley trees on n vertices `):
 print(`verifying empirically that it is the identity`):
fi:
 
 
 
if nops([args])=1 and op(1,[args])=`pisigmaall` then
 print(`pisigmaall(n): Inputs a positive integer n  `):
 print(`outputs  pisigma(ILP) for all irred. legal paranethesings `):
 print(` of size n, verifying empirically that it is the identity`):
fi:
 
 
if nops([args])=1 and op(1,[args])=`sigmaall` then
 print(`sigmaall(n): Inputs a positive integer n  `):
 print(`outputs  sigma(ILP) for all irred. legal paranethesings `):
 print(` of size n, showing how sigma acts for all possible inputs of size n`):
fi:
 
 
if nops([args])=1 and op(1,[args])=`piall` then
 print(`piall(n): Inputs a positive integer n  `):
 print(`outputs  pi(T) for all Stanley `):
 print(` of size n, showing how pi acts for all possible inputs of size n`):
fi:
 
 
 
if nops([args])=1 and op(1,[args])=`IP` then
 print(`IP(n): Inputs a positive integer n  `):
 print(`outputs  all irred. legal paranethesings `):
 print(` of size n`):
fi:
 
 
if nops([args])=1 and op(1,[args])=`stanley` then
 print(`stanley(n): Inputs a positive integer n  `):
 print(`outputs  all possible Stanley trees `):
 print(` of size n`):
fi:
 
 
end: