########################################################################
## BijectionStern.txt Save this file as  BijectionStern.txt  to use it,#                
# stay in the                                                          #
## same directory, get into Maple (by typing: maple <Enter> )          #
## and then type:  read BjectionStern.txt <Enter>                      #
## Then follow the instructions given there                            #
##                                                                     #
## Written by Doron Zeilberger, Rutgers University ,                   #
##  DoronZeil at gmail dot com                                         # 
########################################################################


print(`First Written: Jan. 2021: tested for Maple 2018 `):
print(`Version  : Jan.  2021  `):
print():
print(`This is BijectionStern.txt, the  Maple package`):
print(`accompanying Shalosh B. Ekhad and Doron Zeilberger's  article: `):
print(`A Bijective Proof of Richard Stanley's Observation that the sum of the cubes of the n-th row of`):
print(`Stern's  Diatomic array equals 3 times 7 to the power n-1`):
print():
print(`The most current version is available on WWW at:`):
print(` http://sites.math.rutgers.edu/~zeilberg/tokhniot/BijectionStern.txt .`):
print(`Please report all bugs to: DoronZeil at gmail dot com .`):

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():



ezra1:=proc()
if args=NULL then

print(`The SUPPORTING procedures are: ank, AnrPre, Ankr, anr, MM3, PairL, Pre , Pre1, RedVV `):
print(``):

else
ezra(args):

fi:

end:


ezra:=proc()
if args=NULL then

print(` BijectionStern.txt: A Maple package for  bijective proofs related to Stanley's research on Stern Diatomic  triangle`):

print(`The MAIN procedures are`):
print(` Anr, Ank, CheckBij, InvStanBij, StanBij, StanBijT, StanWords, SternR `):

elif nargs=1 and args[1]=ank then
print(`ank(n,k): The coefficient of x^k in (1+x+x^2)*(1+x^2+x^4)*....*(1+x^(2^(n-1))+ x^(2*n)). Try`):
print(`ank(5,3);`):

elif nargs=1 and args[1]=Ank then
print(`Ank(n,k): The set of vectors in [x[1], .., x[n] ] where x[i] is in {0,1,2} such that add(x[i]*2^(i-1),i=1..n)=k.`):
print(`It is the natural set enumerated by ank(n,k) (q.v.). Try:`):
print(`Ank(5,3);`):

elif nargs=1 and args[1]=Ankr then
print(`Ankr(n,k,r): The set of r by n matrices of {0,1,2} where the valuations of each row is k`):
print(`It is the natural set enumerated by ank(n,k)^r. Try:`):
print(`Ankr(2,3,5); `):

elif nargs=1 and args[1]=anr then
print(`anr(n,r): add(ank(n,k)^r, k=0..2*(2^n-1)):. Try: `):
print(`anr(5,2);`):

elif nargs=1 and args[1]=Anr then
print(`Anr(n,r): The set of r by n matrices with entries {0,1,2} such that all rows have the same valuation.`):
print(`It is the natural set counted by the sum of the r-th power of the entries of the n-th row in the Stern's Diatomic triangle`):
print(`In other words, its cadinality is anr(n,r) (q.v.).  Try: `):
print(`Anr(3,3);`):

elif nargs=1 and args[1]=AnrPre then
print(`AnrPre(n,r,k): The set of the first k columns of the members of Anr(n,r) (q.v.) Try:`):
print(`AnrPre(4,3,2);`):

elif nargs=1 and args[1]=CheckBij then
print(`ChecjBij(n): Checks that StanBij from Anr(n,3) to StanWords(n) and its proposed inverse from StanWords(n) to Anr(n,3) are`):
print(` indeed bijections and inverses of each other . Try:`):
print(`CheckBij(3); `):

elif nargs=1 and args[1]=InvStanBij then
print(`InvStanBij(W):  inputs a word in the alphabet {1,2,3,4,5,6,7} of length n-1 followed by a letter in {1,2,3}`):
print(`outputs a 3 by n matrix whose entries are {0,1,2} counted by the sum of the third powers of the n-th row of the`):
print(`Stern array. Try:`):
print(`InvStanBij([7,3,5,3]);`):
print(`InvStanBij(StanWords(4)[1]);`):


elif nargs=1 and args[1]=MM3 then
print(`MM3(): The list of length 63 consisting of the dictionary needed for StanBij.Try:`):
print(`MM3();`):

elif nargs=1 and args[1]=PairL then
print(`PairL(L1,L2): Given two lists L1 and L2 such that nops(L1)/nops(L2) is an integer, returns the`):
print(`the one-one-mapping between L1x[1, nops(L2)/L1] and L2 as a list of pairs. Try`):
print(`PairL([a,b],[c,d,e,f]);`):

elif nargs=1 and args[1]=Pre then
print(`Pre(S,r): Inputs a set of matrices S each having at least r columns, and outputs the set of matrices obtained by`):
print(`taking the first r columns of each matrix. Try:`):
print(`Pre({[[1,1,1],[1,2,1]],[[3,1,2],[5,1,2]] },2);`):


elif nargs=1 and args[1]=Pre1 then
print(`Pre1(M,r): Inputs a matrix M having at least r columns, and outputs the matrix obtained by`):
print(`taking the first r columns. Try:`):
print(`Pre1([[1,1,1,1],[1,2,1,3]] ,2);`):

elif nargs=1 and args[1]=RedVV then
print(`RedVV(M): Given a matrix M finds the column vector of its reduced value.`):
print(`Try:`):
print(`RedVV([[0,0],[0,0],[0,2]]);`):


elif nargs=1 and args[1]=StanBij then
print(`StanBij(M): The bijection that gives a bijective proof of Stanley's result that anr(n,3)=3*7^(n-1).`):
print(`inputs a  member of Anr(n,3), i.e. a`):
print(`3 by n matrix whose entries are {0,1,2} counted by anr(n,3), the sum of the third powers of the n-th row of the`):
print(`Stern array, `):
print(`and outputs a member of StanWords(n), i.e. a word in the alphabet {1,2,3,4,5,6,7} of length n-1 followed by a letter in {1,2,3}`):
print(`Try: `):
print(` StanBij(Anr(3,3)[1]); `):

elif nargs=1 and args[1]=StanBijT then
print(`StanBijT(n): Gives the table of the bijection between memembers of Anr(n,3) (all 3 by n mattrices of {0,1} with the same valuations`):
print(`and the set of Stanley words of length n, that are words that end in {1,2,3} and otherwise use the letters {1, ..., 7}. Try:`):
print(`StanBijT(2);`):

elif nargs=1 and args[1]=StanWords then
print(`StanWords(n): The set of words of length n whose last letter is in {1,2,3} and the remaining letters are in {1,2,3,4,5,6,7}.`):
print(`It is the natural set enumerated by 3*7^n`):
print(`Try: StanWords(4);`):

elif nargs=1 and args[1]=SternR then
print(`SternR(n): The n-th row of the Stern array. Try:`):
print(`SternR(5);`):

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

fi:


end:

#SternR(n): The n-th row of the Stern array
SternR:=proc(n) local x,gu,i:
gu:=expand(mul(1+x^(2^i)+x^(2^(i+1)),i=0..n-1)):
[seq(coeff(gu,x,i),i=0..degree(gu,x))]:
end:


#ank(n,k): The coefficient of x^k in (1+x+x^2)*(1+x^2+x^4)*....*(1+x^(2^(n-1))+ x^(2*n))
ank:=proc(n,k)  option remember:
if n<0 then
RETURN(0):
elif n=0 then
 if k=0 then
  RETURN(1):
 else
 RETURN(0):
 fi:
else
ank(n-1,k)+ank(n-1,k-2^(n-1)) +ank(n-1,k-2^n):
fi:
end:

#anr(n,r): add(ank(n,k)^r, k=0..2*(2^n-1)):
anr:=proc(n,r) local k:
add(ank(n,k)^r, k=0..2*(2^n-1)):
end:

#Ank(n,k): The set of vectors in [x[1], .., x[n] ] where x[i] is in {0,1,2} such that add(x[i]*2^(i-1),i=1..n)=k. Try:
#Ank(5,3);
Ank:=proc(n,k) local gu0,gu1,gu2,g:
option remember:
if n<0 or k<0 then
 RETURN({}):
fi:
if n=0 then
 if k=0 then
  RETURN({[]}):
 else
  RETURN({}):
fi:
fi:

gu0:=Ank(n-1,k):
gu1:=Ank(n-1,k-2^(n-1)):
gu2:=Ank(n-1,k-2^n):

{seq([op(g),0], g in gu0), seq([op(g),1], g in gu1), seq([op(g),2], g in gu2)}:

end:

#Ankr(n,k,r): The set of r by n matrices of {0,1,2} where the valuations of each row is k
#Ankr(2,3,5):
Ankr:=proc(n,k,r) local gu,mu,mu1,gu1:
option remember:
mu:=Ank(n,k):

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

#if r=1 then
#RETURN({seq([mu1], mu1 in mu)}):
#fi:

gu:=Ankr(n,k,r-1):

{seq(seq([op(gu1),mu1],mu1 in mu),gu1 in gu)}:

end:


#Anr(n,r): The set of r by n matrices with entries {0,1,2} such that all rows have the same valuation. Try:
#Anr(3,3);
Anr:=proc(n,r) local k:
{seq(op(Ankr(n,k,r)),k=0..2*(2^n-1))}:
end:


#Pre1(M,r): The first r columns of the matrix M
Pre1:=proc(M,r) local i:
if nops(M[1])<r then
 M:
else
 [seq([op(1..r,M[i])],i=1..nops(M))]:
fi:
end:

#Pre(S,r): The set of first r columns of the matrices in the set S. Try:
#Pre({[[1,1,1],[1,2,1]],[[3,1,2],[5,1,2] },2);
Pre:=proc(S,r) local s: {seq(Pre1(s,r), s in S)}: end:

#AnrPre(n,r,k): The set of the first k columns of the members of Anr(n,r) (q.v.) Try:
#AnrPre(4,3,2);
AnrPre:=proc(n,r,k): Pre(Anr(n,r),k):end:



#RedVV(M): Given a matrix M finds the column vector of its reduced value.
#Try:
#RedVV([[0,0],[0,0],[0,2]]);
RedVV:=proc(M) local i,j,v,a:
v:=[seq(
 add(M[i][j]*2^(j-1),j=1..nops(M[i]) ) ,
  i=1..nops(M))]:

a:=min(op(v)):

v-[a$nops(v)]:
end:




#PairL(L1,L2): Given two lists L1 and L2 such that nops(L1)/nops(L2) is an integer, returns the
#the one-one-mapping between L1x[1, nops(L2)/L1] and L2 as a list of pairs. Try
#PairL([a,b],[c,d,e,f]);

PairL:=proc(L1,L2) local n,lu,i,j:
n:=nops(L2)/nops(L1):

if not type(n,integer) then
 RETURN(FAIL):
fi:

lu:={}:


for i from 1 to n do
 for j from 1 to nops(L1) do
   lu:=lu union { [ [i,L1[j]]  ,L2[(i-1)*nops(L1)+j] ] }:
od:
od:
lu:
end:


MM3:=proc() local A1,A2,T1,T2,V,v,a,gu1,gu2,mu:
option remember:
A1:=AnrPre(3,3,1):
A2:=AnrPre(3,3,2):

V:={seq(RedVV(a), a in A1)}:


for v in V do 
T1[v]:={}:
T2[v]:={}:
od:

for a in A1 do
T1[RedVV(a)]:=T1[RedVV(a)] union {a}:
od:


for a in A2 do
T2[RedVV(a)/2]:=T2[RedVV(a/2)] union {a}:
od:




mu:={}:

 for v in V do

   gu1:=T1[v]:
   gu2:=T2[v]:


   gu1:=convert(gu1,list):
   gu2:=convert(gu2,list):

 
   mu:=mu union PairL(gu1,gu2):

 od:
 
mu:

end:



#StanBij(M): The bijection that gives a bijective proof of Stanley's result that anr(n,3)=3*7^(n-1).
#inputs a  member of Anr(n,3), i.e. a
#3 by n matrix whose entries are {0,1,2} counted by anr(n,3), the sum of the third powers of the n-th row of the
#Stern array, 
#and outputs a member of StanWords(n), i.e. a word in the alphabet {1,2,3,4,5,6,7} of length n-1 followed by a letter in {1,2,3}
#Try:
#StanBij(Anr(3,3)[1]);
StanBij:=proc(M) local M1,F,mu,mu1,j,F1:

if nops(M[1])=1 then
 if M[1][1]=0 then
   RETURN([1]):
 elif M[1][1]=1 then
    RETURN([2]):
  elif M[1][1]=2 then
    RETURN([3]):
 fi:
fi:

mu:=MM3():

F:=Pre1(M,2):



for mu1 in mu while mu1[2]<>F do od:


F1:=mu1[1]:
j:=F1[1]:
F1:=F1[2]:




M1:=
[
   [F1[1][1],op(3..nops(M[1]),M[1]) ],
  [F1[2][1],op(3..nops(M[2]),M[2]) ],
  [F1[3][1],op(3..nops(M[3]),M[3])]
 ]:



[j,op(StanBij(M1) ) ];

end:



#InvStanBij(W):  inputs a word in the alphabet {1,2,3,4,5,6,7} of length n-1 followed by a letter in {1,2,3}
#outputs a 3 by n matrix whose entries are {0,1,2} counted by the sum of the third powers of the n-th row of the
#Stern array. Try:
#InvStanBij([7,3,5,3]);
InvStanBij:=proc(W) local W1,M1,mu,mu1,j,F1,F2:

if nops(W)=1 then
 if W[1]=1 then
  RETURN([[0],[0],[0]]):
 elif W[1]=2 then
  RETURN([[1],[1],[1]]):
 elif W[1]=3 then
  RETURN([[2],[2],[2]]):
else
 RETURN(FAIL):
fi:
fi:


mu:=MM3():

j:=W[1]:

W1:=[op(2..nops(W),W)]:

M1:=InvStanBij(W1):

F1:=Pre1(M1,1):


for mu1 in mu while mu1[1]<>[j,F1] do od:


F2:=mu1[2]:

 [
   [op(F2[1]),op(2..nops(M1[1]),M1[1]) ],
  [op(F2[2]),op(2..nops(M1[2]),M1[2]) ],
  [op(F2[3]),op(2..nops(M1[3]),M1[3])]
 ]:




end:


#StanWords(n): The set of words of length n whose last letter is in {1,2,3} and the remaining letters are in {1,2,3,4,5,6,7}.
#It is the natural set enumerated by 3*7^n
#Try: StanWords(4);
StanWords:=proc(n) local gu,i,gu1:
option remember:
if n=1 then
 RETURN({[1],[2],[3]}):
fi:
gu:=StanWords(n-1):

{seq(seq([i,op(gu1)],gu1 in gu),i=1..7)}:
end:

#ChecjBij(n): Checks that StanBij and InvStanBij are indeed bijections and inverses of each other
CheckBij:=proc(n) local A,B,a,b:
A:=Anr(n,3):
B:=StanWords(n):

if {seq(StanBij(a),a in A)}<>B then
 print(`The image of StanBij is NOT StanWords`):
 RETURN(false):
fi:


if {seq(InvStanBij(b),b in B)}<>A then
 print(`The image of InvStanBij is NOT Anr(n,3)`):
 RETURN(false):
fi:

if {seq(evalb(InvStanBij(StanBij(a))=a),a in A)}<>{true} then
 print(`InvStanBij composed with StanBij is not  the identity mapping `):
 RETURN(false):
fi:


if {seq(evalb(StanBij(InvStanBij(b))=b),b in B)}<>{true} then
 print(`StanBij composed with InvStanBij is not  the identity mapping `):
 RETURN(false):
fi:

true:

end:





#StanBijT(n): Gives the table of the bijection between memembers of Anr(n,3) (all 3 by n mattrices of {0,1} with the same valuations
#and the set of Stanley words of length n, that are words that end in {1,2,3} and otherwise use the letters {1, ..., 7}. Try:
#StanBijT(2);

StanBijT:=proc(n) local gu,M,i:
gu:=Anr(n,3):
print(``):
print(`---------------------------`):
print(``):

print(`A table of the bijection between balanced 3 by n Stern matrices and Stanley words for n=`,n):
print(``):
print(`By Shalosh B. Ekhad `):
print(``):
print(`The Ekhad-Zeilberger bijection takes as input 3 by n balanced matrices (see article) and outputs Stanley words of length n`):
print(`These are words with n letters in the alphabet {1,...,7} that must end with a letter in {1,2,3}, hence their number is 3*7^(n-1)`):
print(`We will illustrate it for n=`, n):
gu:=Anr(n,3):

for i from 1 to nops(gu) do
print(`The matrix`):
print(``):
print(matrix(gu[i])):
print(``):
M:=StanBij(gu[i]):
print(``):
print(`goes to the word`, M):
print(``):
od:
print(``):
print(`---------------------------`):
print(``):
end: