######################################################################
## PHIL: Save this file as  PHIL  to use it,                          #
# stay in the                                                        #
## same directory, get into Maple (by typing: maple <Enter> )        #
## and then type:  read PHIL: <Enter>                                #
## Then follow the instructions given there                          #
##                                                                   #
## Written by Doron Zeilberger, Rutgers University ,                 #
##  zeilberg@math.rutgers.edu.                                       # 
######################################################################


print(`First Written: Dec. 9, 2005: tested for Maple 10 `):
print(`Version of Dec. 9, 2005:  `):
print():
print(`This is PHIL, A Maple package`):
print(`accompanying  Philip Matchett Wood's  lovely article: `):
print(`"A bijective proof of `):
print(` "f_{n+4}+1f_1+2f_2+ ... + n f_n =(n+1)f_{n+2}+ 3" `):
print(`Available from http://www.math.rutgers.edu/~matchett/ `):


print():
print(`The most current version of this program is  available on WWW at:`):
print(` http://www.math.rutgers.edu/~zeilberg/tokhniot/PHIL .`):
print(`Please report all bugs to: zeilberg at math dot rutgers dot edu .`):
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():
 


ezra:=proc()
if args=NULL then

print(` PHIL: A Maple package implementing the lovely `):
print(`bijection described in Phlip Matchett Wood's article`):
print(`A bijective proof of `): 
print(` "f_{n+4}+1f_1+2f_2+ ... + n f_n =(n+1)f_{n+2}+ 3" `):
print(`The MAIN procedures are`):
print(`Fn, Left1, phi psi, Right1 , `):
print(`Checkphi(n), , Checkphipsi(n), Checkpsi(n), Checkpsiphi(n)`):
print(`For help with a specific procedure, type ezra(Procedure);`):
print(`For example, for help with Checkpsi, type: ezra(Checkpsi);`):

elif nargs=1 and args[1]=Checkphi then
print(`Checkphi(n): For an integer n, checks that`):
print(` phi(Left1(n))=Right1(n)`):
print(`For example, try: Checkphi(5);`):

elif nargs=1 and args[1]=Checkphipsi then
print(`Checkphipsi(n): For an integer n, checks that`):
print(` phi composed with psi is the identity mapping `):
print(`For example, try: Checkphipsi(5);`):

elif nargs=1 and args[1]=Checkpsiphi then
print(`Checkpsiphi(n): For an integer n, checks that`):
print(` psi composed with phi is the identity mapping `):
print(`For example, try: Checkpsiphi(5);`):

elif nargs=1 and args[1]=Checkpsi then
print(`Checkpsi(n): For an integer n, checks that`):
print(` psi(Right1(n))=Left1(n)`):
print(`For example, try: Checkpsi(5);`):

elif nargs=1 and args[1]=Fn then
print(`Fn(n): For n positive integer,`):
print(`the set of all lists with entries from {1,2}`):
print(`that add-up to n.`):
print(`For example, try: Fn(5);`):

elif nargs=1 and args[1]=Left1 then
print(`Left1(n): The Domain of phi (and Range of psi)`):
print(`For example, try: Left1(4);`):

elif nargs=1 and args[1]=phi then
print(`phi(w,n): Given an element of Left1(n), applies Phlip`):
print(`Matchett Wood's mapping phi`):
print(`For example, try: phi(Left1(5)[1],5);`):

elif nargs=1 and args[1]=psi then
print(`psi(w,n): Given an element of Right1(n), applies Phlip`):
print(`Matchett Wood's mapping psi`):
print(`For example, try: psi(Right1(5)[1],5);`):

elif nargs=1 and args[1]=Right1 then
print(`Right1(n): The Domain of psi (and Range of phi)`):
print(`For example, try: Right1(4);`):


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

fi:


end:


ez:=proc():print(`Fn(n), Left1(n), Right1(n) , phi(w,n), psi(w,n) `):
print(`Checkphi(n), Checkpsi(n), Checkpsiphi(n), Checkphipsi(n) `):
end:

Fn:=proc(n) local gu1,gu2,i:
if n<0 then
 {}:
elif n=0 then
 {[]}:
else
 gu1:=Fn(n-1):gu2:=Fn(n-2):
{seq([op(gu1[i]),1],i=1..nops(gu1)),seq([op(gu2[i]),2],i=1..nops(gu2))}:
fi:
end:

Left1:=proc(n) local gu,i,j,mu,i1:
mu:=Fn(n+4):
gu:={seq([0,mu[i]],i=1..nops(mu))}:

for i from 1 to n do
 mu:=Fn(i):
for j from 1 to i do
gu:=gu union {seq([j,mu[i1]],i1=1..nops(mu))}:
od:
od:
gu:
end:

Right1:=proc(n) local mu,i,j:
mu:=Fn(n+2):
{1,2,3} union {seq(seq([i,mu[j]],i=1..n+1),j=1..nops(mu))}:
end:

phi:=proc(w,n)
local i,L,x:
if w[1]=0 then
   x:=w[2]:

 if x=[1$(n+4)] then
    RETURN([1,[1$(n+2)]]):
  elif x=[2,1$(n+2)] then
    RETURN(1):
  elif x=[1,2,1$(n+1)] then
   RETURN(2):
  elif x=[1,1,2,1$n] then
    RETURN(3):
  elif x=[2,2,1$n] then
   RETURN([1,[2,1$n]]):
 else  
     for i from 1 to nops(x) while x[nops(x)-i+1]=1 do od:
     L:=i-1:
     RETURN([n-L+1,[op(1..nops(x)-L-1,x),1$L]]):
 fi:
else
  i:=w[1]:
   x:=w[2]:
   L:=convert(x,`+`):
    RETURN([i,[op(x),2,1$(n-L)]]):
 fi:
end:



psi:=proc(w,n) local i,y,L,i1:

if w=[1,[1$(n+2)]] then
  RETURN([0,[1,1,1,1,1$n]]):
 elif w=1 then
  RETURN([0,[2,1,1,1$n]]):
 elif w=2 then
  RETURN([0,[1,2,1,1$n]]):
 elif w=3 then
  RETURN([0,[1,1,2,1$n]]):
else
  i:=w[1]: y:=w[2]:
     for i1 from 1 to nops(y) while y[nops(y)-i1+1]=1 do od:
      L:=i1-1:
    if L>=n+1-i then
     RETURN([0,[op(1..nops(y)-(n+1-i),y),2,1$(n-i+1)]]):
    else
      RETURN([i,[op(1..nops(y)-L-1,y)]]):
    fi:
 fi:
end:


Checkphi:=proc(n) local guL, guR,i:
 guL:=Left1(n): guR:=Right1(n):
 evalb({seq(phi(guL[i],n),i=1..nops(guL))}=guR):
end:

Checkpsi:=proc(n) local guL, guR,i:
 guL:=Left1(n): guR:=Right1(n):
 evalb({seq(psi(guR[i],n),i=1..nops(guR))}=guL):
end:

Checkpsiphi:=proc(n) local i,guL:
 guL:=Left1(n): 
{seq( evalb(psi(phi(guL[i],n),n)=guL[i]),i=1..nops(guL))}:
end:

Checkphipsi:=proc(n) local guR,i:
 guR:=Right1(n): 
{seq( evalb(phi(psi(guR[i],n),n)=guR[i]),i=1..nops(guR))}:
end: