#####################################################################
##FOATA: Save this file as  FOATA                                    #
## To use it, stay in the                                            #
##same directory, get into Maple (by typing: maple <Enter> )         #
##and then type:  read FOATA<Enter>                                  #
##Then follow the instructions given there                           #
##                                                                   #
##Written by Doron Zeilberger, Rutgers University ,                  #
#zeilberg at math dot rutgers dot edu                                #
######################################################################
 
#Created:  Oct. 1, 2014
 
print(`Created: Oct. 1, 2014`):
print(` This is FOATA`):
print(`It is one of the packages that accompany the Rutgers University Experimental Mathematics Seminar talk `):
print(`delivered, Oct. 2, 2014, 5:00-5:48pm`):
print(`by  Doron Zeilberger`):

print(` The video is  available from vimeo, and there is a link to it from `):
print(``):
 print(`http://www.math.rutgers.edu/~zeilberg/mamarim/mamarilhtml/foata80.html  .`):
print(``):
print(`Please report bugs to zeilberg at math dot rutgers dot edu`):
print(``):
 print(`The most current version of this  package and paper`):
 print(` are  available from`):
 print(`http://www.math.rutgers.edu/~zeilberg/  .`):

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

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

with(combinat):

ezra1:=proc()

if args=NULL then
 print(` The supporting procedures are: BreakUpS, BreakUpSv ,BreakUpL, BreakUpLv,CheckDF1,CheckDF1m, CheckDF2,CheckDF2m,DetachL, DetachS`):
 print(``):

else
ezra(args):
fi:

end:

ezra:=proc()

if args=NULL then
 print(`The main procedures are: CheckDF, CheckDFm, DF1, DF1v, DF1vv, DF2, inv, maj, Tavla, TavlaG, Tavlot `):
 print(` `):


elif nops([args])=1 and op(1,[args])=BreakUpL then
print(`BreakUpL(w,i): Given a sequence of numbers w, and another number i, returns the list of lists`):
print(`[a1,x1,a2,x2,...,ar,xr] where the elements of a1, a2,... are strings of elements >i and  x1,x2,..., are individuals<=i, try:`):
print(`BreakUpL([2,3,1,1,3,2],2);`):

elif nops([args])=1 and op(1,[args])=BreakUpLv then
print(`BreakUpLv(w,i): Verbose version of BreakUpL(w,i) (q.v.) . Try:`):
print(`BreakUpLv([2,3,1,1,3,2],2);`):

elif nops([args])=1 and op(1,[args])=BreakUpS then
print(`BreakUpS(w,i): Given a sequence of numbers w, and another number i, returns the list of lists`):
print(`[a1,x1,a2,x2,...,ar,xr] where the elements of a1, a2,... are strings of elements <=i and  x1,x2,..., are individuals>i, try:`):
print(`BreakUpS([2,3,1,1,3,2],2);`):

elif nops([args])=1 and op(1,[args])=BreakUpSv then
print(`BreakUpSv(w,i): Verbose version of BreakUpS(w,i) (q.v.) . Try:`):
print(`BreakUpSv([2,3,1,1,3,2],2);`):

elif nops([args])=1 and op(1,[args])=CheckDF then
print(`CheckDF(n): Does CheckDF1(n),CheckDF2(n), and that DF1(DF2) and DF2(DF1) are the identity maps defined on n-permutations.`):
print(`Try: CheckDF(5);`):

elif nops([args])=1 and op(1,[args])=CheckDFm then
print(`CheckDFm(L): Does CheckDF1(L),CheckDF2(L), and that DF1(DF2) and DF2(DF1) are the identity maps defined on the set.`):
print(`of multi-permutations with L[1] 1's, L[2] 2's, etc. `):
print(`Try: CheckDFm([3,2,3]);`):

elif nops([args])=1 and op(1,[args])=CheckDF1 then
print(`CheckDF1(n): checks that DF1 is a bijection and that it sends maj to inv for permutations of length n. Try:`):
print(`CheckDF1(5);`):

elif nops([args])=1 and op(1,[args])=CheckDF1m then
print(`CheckDF1m(L): checks that DF1 is a bijection and that it sends maj to inv for multi-set permutations of L[1] 1's, L[2] 2's. Try:`):
print(`CheckDF1m([3,4]);`):

elif nops([args])=1 and op(1,[args])=CheckDF2 then
print(`CheckDF2(n): checks that DF2 is a bijection and that it sends inv to maj for permutations of length n. Try:`):
print(`CheckDF2(5);`):

elif nops([args])=1 and op(1,[args])=CheckDF2m then
print(`CheckDF2m(L): checks that DF2 is a bijection and that it sends inv to maj for multi-set permutations of L[1] 1's, L[2] 2's. Try:`):
print(`CheckDF2m([3,4]);`):

elif nops([args])=1 and op(1,[args])=DetachL then
print(`DetachL(w,i): inputs a sequence w of numbers, and another number i, outputs the (possibly empty)`):
print(`string of elements >i , followed by the rest. Try:`):
print(`DetachL([2,1,2,2,1],1);`):
print(``):

elif nops([args])=1 and op(1,[args])=DetachS then
print(`DetachS(w,i): inputs a sequence w of numbers, and another number i, outputs the `):
print(` (possiblyempty)`):
print(`string of elements <=i , followed by the rest. Try:`):
print(`DetachS([2,1,2,2,1],1);`):
print(``):


elif nops([args])=1 and op(1,[args])=DF1 then
print(`DF1(a): implemenets Dominique Foata's seminal bijection that sends the major index to the number of inversion`):
print(`described in his paper published in Proc. Amer. Math. Soc. v. 19 (1968), 236-240.`):
print(`inputs a sequence of numbers a, and outputs a rearrangement of them whose number of inversions`):
print(`is the same as the major index of the original. It uses the formulation in Knuth's ACPIII, ex. 19 in section 5.1.1 (p. 581)`):
print(`Try:`):
print(`DF1([3,1,2,4]);`):


elif nops([args])=1 and op(1,[args])=DF1v then
print(`DF1v(a):  VERBOSE VERSION of DF1(a) (q.v.)`):
print(`Try:`):
print(`DF1v([3,1,2,4]);`):

elif nops([args])=1 and op(1,[args])=DF1vv then
print(`DF1vv(a):  A SUPER VERBOSE VERSION of DF1(a) (q.v.)`):
print(`Try:`):
print(`DF1vv([3,1,2,4]);`):

elif nops([args])=1 and op(1,[args])=DF2 then
print(`DF2(b): implemenets the inverse of Dominique Foata's seminal bijection that sends  inv to maj`):
print(`described in his paper published in Proc. Amer. Math. Soc. v. 19 (1968), 236-240.`):
print(`inputs a sequence of numbers b, and outputs a rearrangement of them whose major index`):
print(`is the same as the number of inversions of the original. It uses the formulation in Knuth's ACPIII, ex. 19 in section 5.1.1 (p. 581)`):
print(`Try:`):
print(`DF2([3,1,2,4]);`):

elif nops([args])=1 and op(1,[args])=inv then
print(`inv(w): the number of inversions of the sequence of numbers w. Try: inv([2,1,3]);`):

elif nops([args])=1 and op(1,[args])=maj then
print(`maj(w): the major index of the sequence of numbers w. Try: maj([2,1,3]);`):

elif nops([args])=1 and op(1,[args])=Tavla then
print(`Tavla(n): tabulates the Foata Bijection that sends the major index to the number of inversions to all permutations of length n`):
print(`Try:`):
print(`Tavla(6);`):

elif nops([args])=1 and op(1,[args])=TavlaG then
print(`TavlaG(a): tabulates the Foata Bijection that sends the major index to the number of inversions to all permutations of `):
print(`#1$a[1] ...n$a[n]`):
print(`Try: `):
print(`TavlaG([2,2,2]);`):

elif nops([args])=1 and op(1,[args])=Tavlot then
print(`Tavlot(N): tabulates the Foata Bijection that sends the major index to the number of inversions to all permutations of length n, for n<=N`):
print(`Try:`):
print(`Tavlot(6);`):

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


#DetachS(w,i): inputs a sequence w of numbers, and another number i, outputs the (possibly empty)
#string of elements <=i , followed by the rest. Try:
#DetachS([2,1,2,2,1],1);
DetachS:=proc(w,i) local j:

for j from 1 to nops(w) while w[j]<=i do od:
j:=j-1:
[op(1..j,w)],[op(j+1..nops(w),w)]:
end:

#DetachL(w,i): inputs a sequence w of numbers, and another number i, outputs the (possibly empty)
#string of elements >i , followed by the rest. Try:
#DetachL([2,1,2,2,1],1);
DetachL:=proc(w,i) local j:

for j from 1 to nops(w) while w[j]>i do od:
j:=j-1:
[op(1..j,w)],[op(j+1..nops(w),w)]:
end:


#BreakUpL(w,i): Given a sequence of numbers w, and another number i, returns the list of lists
#[a1,x1,a2,x2,...,ar,xr] where the strings of elements of a1, a2,... are >i and those of x1,x2,..., are the elements <=i, try:
#BreakUpL([2,3,1,1,3,2],2);
BreakUpL:=proc(w,i) local j,w1:
 
 if w=[] then
  RETURN([[]]):
fi:

for j from 1 to nops(w) while w[j]>i do od:
j:=j-1:
if j=nops(w) then
  RETURN([w]):
else
 w1:=[op(j+2..nops(w),w)]:
RETURN([[op(1..j,w)],[w[j+1]], op(BreakUpL(w1,i))]):
fi:

end:


#BreakUpLv(w,i): Verbose version of BreakUpL(w,i):
#Given a sequence of numbers w, and another number i, returns the list of lists
#[a1,x1,a2,x2,...,ar,xr] where the strings of elements of a1, a2,... are >i and those of x1,x2,..., are the elements <=i, try:
#BreakUpLv([2,3,1,1,3,2],2);
BreakUpLv:=proc(w,i) local gu:

gu:=BreakUpL(w,i):

print(`The break-up where entries larger than`, i,`are lumped together, but entries less than or equal to`, i, `are by themselves is`):

print(gu):

end:


#BreakUpS(w,i): Given a sequence of numbers w, and another number i, returns the list of lists
#[a1,x1,a2,x2,...,ar,xr] where the strings of elements of a1, a2,... are <=i and those of x1,x2,..., are the elements >i, try:
#BreakUpS([2,3,1,1,3,2],2);
BreakUpS:=proc(w,i) local j,w1:
 
 if w=[] then
  RETURN([[]]):
fi:

for j from 1 to nops(w) while w[j]<=i do od:
j:=j-1:
if j=nops(w) then
  RETURN([w]):
else
 w1:=[op(j+2..nops(w),w)]:
RETURN([[op(1..j,w)],[w[j+1]], op(BreakUpS(w1,i))]):
fi:

end:

#BreakUpSv(w,i): Verbose version of BreakUpS(w,i):
BreakUpSv:=proc(w,i) local gu:

gu:=BreakUpS(w,i):

print(`The break-up where entries smaller or equal  than`, i,`are lumped together, but entries larger `, i, `are by themselves is`):

print(gu):

end:

#DF1(a): implemenets Dominique Foata's seminal bijection that sends the major index to the number of inversion
#described in his paper published in Proc. Amer. Math. Soc. v. 19 (1968), 236-240.
#inputs a sequence of numbers s, and outputs a rearrangement of them whose number of inversions
#is the same as the major index of the original. It uses the formulation in Knuth's ACPIII, ex. 19 in section 5.1.1 (p. 581)
#Try:
#DF1([3,1,2,4]);
DF1:=proc(a) local n,an,a1,b1,r,i:
option remember:
if nops(a)<=1 then
 RETURN(a):
fi:

n:=nops(a):

an:=a[n]:

a1:=[op(1..n-1,a)]:
b1:=DF1(a1):

if a[n-1]<=a[n] then

b1:=BreakUpL(b1,an):

if nops(b1) mod 2=1 then
 if b1[nops(b1)]<>[] then
  b1:=[op(b1),[]]:
 else
  b1:=[op(1..nops(b1)-1,b1)]:
 fi:

fi:

r:=nops(b1)/2:
b1:=[seq(op([b1[2*i],b1[2*i-1]]),i=1..r)]:
b1:=[seq(op(b1[i]),i=1..nops(b1)),an]:
RETURN(b1):


else

b1:=BreakUpS(b1,an):

if nops(b1) mod 2=1 then
 if b1[nops(b1)]<>[] then
  b1:=[op(b1),[]]:
 else
  b1:=[op(1..nops(b1)-1,b1)]:
 fi:
fi:

r:=nops(b1)/2:
b1:=[seq(op([b1[2*i],b1[2*i-1]]),i=1..r)]:
b1:=[seq(op(b1[i]),i=1..nops(b1)),an]:
RETURN(b1):

fi:

end:

#maj(w): the major index of the sequence of numbers w. Try: maj([2,1,3]);
maj:=proc(w) local i,co:
co:=0:

for i from 1 to nops(w)-1 do
 if w[i]>w[i+1] then
  co:=co+i:
 fi:
od:

co:
end:


#inv(w): the number of inversions of the sequence of numbers w. Try: inv([2,1,3]);
inv:=proc(w) local i,j,co:
co:=0:

for i from 1 to nops(w)-1 do
 for j from i+1 to nops(w) do
  if w[i]>w[j] then
   co:=co+1:
  fi:
 od:
od:

co:
end:


#CheckDF1(n): checks that DF1 is a bijection and that it sends maj to inv for permutations of length n. Try:
#CheckDF1(5);
CheckDF1:=proc(n) local gu,pi:
gu:=convert(permute(n),set):

if {seq(DF1(pi), pi in gu)}<>gu then
 print(`Not a bijection`):
 RETURN(false):
fi:

if {seq(inv(DF1(pi))-maj(pi), pi in gu)}<>{0} then
 print(`Does not send maj to inv`):
 RETURN(false):
fi:

true:

end:

#CheckDF1m(L): checks that DF1 is a bijection and that it sends maj to inv for multiset permutations  with list L
#CheckDF1([3,2,3]);
CheckDF1m:=proc(L) local i,gu,pi:
gu:=convert(permute([seq(i$L[i],i=1..nops(L))]),set):

if {seq(DF1(pi), pi in gu)}<>gu then
 print(`Not a bijection`):
 RETURN(false):
fi:

if {seq(inv(DF1(pi))-maj(pi), pi in gu)}<>{0} then
 print(`Does not send maj to inv`):
 RETURN(false):
fi:

true:

end:




#DF2(b): implemenets Dominique Foata's the reverse seminal bijection that sends the inv to maj 
#described in his paper published in Proc. Amer. Math. Soc. v. 19 (1968), 236-240.
#inputs a sequence of numbers s, and outputs a rearrangement of them whose number of inversions
#is the same as the major index of the original. It uses the formulation in Knuth's ACPIII, ex. 19 in section 5.1.1 (p. 581)
#Try:
#DF2([3,1,2,4]);
DF2:=proc(b) local n,bn,b1, a1,a, r,i:
option remember:
if nops(b)<=1 then
 RETURN(b):
fi:

n:=nops(b):

bn:=b[n]:

b1:=[op(1..n-1,b)]:


if b[1]<=b[n] then

b1:=[[b1[1]],op(BreakUpL([op(2..nops(b1),b1)],bn) )]:

if nops(b1) mod 2=1 then
 if b1[nops(b1)]<>[] then
  b1:=[op(b1),[]]:
 else
  b1:=[op(1..nops(b1)-1,b1)]:
 fi:

fi:


r:=nops(b1)/2:
b1:=[seq(op([b1[2*i],b1[2*i-1]]),i=1..r)]:
b1:=[seq(op(b1[i]),i=1..nops(b1))]:
a1:=DF2(b1):
a:=[op(a1),bn]:
RETURN(a):



else

b1:=[[b1[1]],op(BreakUpS([op(2..nops(b1),b1)],bn))]:

if nops(b1) mod 2=1 then
 if b1[nops(b1)]<>[] then
  b1:=[op(b1),[]]:
 else
  b1:=[op(1..nops(b1)-1,b1)]:
 fi:

fi:


r:=nops(b1)/2:
b1:=[seq(op([b1[2*i],b1[2*i-1]]),i=1..r)]:
b1:=[seq(op(b1[i]),i=1..nops(b1))]:
a1:=DF2(b1):
a:=[op(a1),bn]:
RETURN(a):

fi:

end:


#CheckDF2(n): checks that DF2 is a bijection and that it sends maj to inv for permutations of length n. Try:
#CheckDF2(5);
CheckDF2:=proc(n) local gu,pi:
gu:=convert(permute(n),set):

if {seq(DF2(pi), pi in gu)}<>gu then
 print(`Not a bijection`):
 RETURN(false):
fi:

if {seq(maj(DF2(pi))-inv(pi), pi in gu)}<>{0} then
 print(`Does not send inv to maj`):
 RETURN(false):
fi:

true:

end:

#CheckDF2m(L): checks that DF2 is a bijection and that it sends maj to inv for multiset permutations  with list L
#CheckDF2([3,2,3]);
CheckDF2m:=proc(L) local i,gu,pi:
gu:=convert(permute([seq(i$L[i],i=1..nops(L))]),set):

if {seq(DF2(pi), pi in gu)}<>gu then
 print(`Not a bijection`):
 RETURN(false):
fi:

if {seq(maj(DF2(pi))-inv(pi), pi in gu)}<>{0} then
 print(`Does not send inv to maj`):
 RETURN(false):
fi:

true:

end:


#CheckDF(n): Does CheckDF1(n),CheckDF2(n), and that DF1(DF2) and DF2(DF1) are the identity maps defined on n-permutations.
#Try: CheckDF(5);
CheckDF:=proc(n) local gu,pi:
gu:=permute(n):

if {seq(evalb(DF2(DF1(pi))=pi),pi in gu)}<>{true} then
  RETURN(false):
fi:

if {seq(evalb(DF1(DF2(pi))=pi),pi in gu)}<>{true} then
  RETURN(false):
fi:

if not CheckDF1(n) then
  RETURN(false):
fi:

if not CheckDF2(n) then
  RETURN(false):
fi:

true:
end:

#CheckDFm(L): Does CheckDF1m(L),CheckDF2(L), and that DF1(DF2) and DF2(DF1) are the identity maps defined on L-multi-permutations.
#Try: CheckDFm([3,4]);
CheckDFm:=proc(L) local gu,pi,i:
gu:=convert(permute([seq(i$L[i],i=1..nops(L))]),set):

if {seq(evalb(DF2(DF1(pi))=pi),pi in gu)}<>{true} then
  RETURN(false):
fi:

if {seq(evalb(DF1(DF2(pi))=pi),pi in gu)}<>{true} then
  RETURN(false):
fi:

if not CheckDF1m(L) then
  RETURN(false):
fi:

if not CheckDF2m(L) then
  RETURN(false):
fi:

true:
end:









#DF1v(a): Verbose version of 
#Dominique Foata's seminal bijection that sends the major index to the number of inversion
#described in his paper published in Proc. Amer. Math. Soc. v. 19 (1968), 236-240.
#inputs a sequence of numbers s, and outputs a rearrangement of them whose number of inversions
#is the same as the major index of the original. It uses the formulation in Knuth's ACPIII, 
#ex. 1#9 in section 5.1.1 (p. 581)
#Try:
#DF1v([3,1,2,4]);
DF1v:=proc(a) local n,an,a1,b1,r,i,b1old,b1p:
option remember:
if nops(a)<=1 then
 RETURN(a):
fi:

n:=nops(a):

an:=a[n]:

a1:=[op(1..n-1,a)]:
b1:=DF1(a1):
b1old:=b1:
print(`The input word is`, a, `of length`, n):
print(`its major index is`, maj(a)):
print(`The last letter is`, a[n], `and the one before it is`, a[n-1]):

print(`The chopped  word, after deleting the last letter`, a[n], `is : `):
print(a1):
print(`Its major index is`, maj(a1)) :
print(`Applying the Foata bijection recursively (details omitted), we get`):
print(b1):
print(`whose number of inversions is`,  inv(b1)):

if a[n-1]<=a[n] then

print(` Since `, a[n-1]<=a[n], ` we have Case I`):



b1:=BreakUpL(b1,an):



if nops(b1) mod 2=1 then
 if b1[nops(b1)]<>[] then
  b1:=[op(b1),[]]:
 else
  b1:=[op(1..nops(b1)-1,b1)]:
 fi:

fi:

#print(`The break-up of the output of the recursive step`, b1old, `according  to blocks is`):
#print(b1):

BreakUpLv(b1old,an):

r:=nops(b1)/2:
b1p:=[seq(op([b1[2*i],b1[2*i-1]]),i=1..r)]:
print(`and  after the clever Foata interchange`):
print(b1p):
b1:=[seq(op([b1[2*i],b1[2*i-1]]),i=1..r)]:
print(`Catenating, and appending the last letter`, an, `we get`):

b1:=[seq(op(b1[i]),i=1..nops(b1)),an]:
print(b1):

RETURN(b1):


else

print(` Since `, a[n-1]>a[n], ` we have Case II`):
b1:=BreakUpS(b1,an):

if nops(b1) mod 2=1 then
 if b1[nops(b1)]<>[] then
  b1:=[op(b1),[]]:
 else
  b1:=[op(1..nops(b1)-1,b1)]:
 fi:
fi:

#print(`The break-up of the output of the recursive step`, b1old, `according  to blocks is`):
#print(b1):

BreakUpSv(b1old,an):
r:=nops(b1)/2:
b1p:=[seq(op([b1[2*i],b1[2*i-1]]),i=1..r)]:
print(`And  after the clever Foata interchange`):
print(b1p):

b1:=[seq(op([b1[2*i],b1[2*i-1]]),i=1..r)]:

print(`Catenating, and appending the last letter`, an, `we get`):
b1:=[seq(op(b1[i]),i=1..nops(b1)),an]:

print(b1):

RETURN(b1):

fi:

end:


#DF1vv(a): Verbose version of 
#Dominique Foata's seminal bijection that sends the major index to the number of inversion
#described in his paper published in Proc. Amer. Math. Soc. v. 19 (1968), 236-240.
#inputs a sequence of numbers s, and outputs a rearrangement of them whose number of inversions
#is the same as the major index of the original. It uses the formulation in Knuth's ACPIII, 
#ex. 1#9 in section 5.1.1 (p. 581)
#Try:
#DF1vv([3,1,2,4]);
DF1vv:=proc(a) local n,an,a1,b1,r,i,b1old,b1p:
option remember:

if nops(a)<=1 then
print(`The output is, of course,`):
print(a):
 RETURN(a):
fi:

n:=nops(a):

an:=a[n]:

a1:=[op(1..n-1,a)]:
b1:=DF1(a1):
b1old:=b1:
print(`The input word is`, a, `of length`, n):
print(`its major index is`, maj(a)):
print(`The last letter is`, a[n], `and the one before it is`, a[n-1]):

print(`The chopped  word, after deleting the last letter`, a[n], `is : `):
print(a1):
print(`whose number of inversions is`,  inv(b1)):
print(`Its major index is`, maj(a1)) :
print(`Applying the Foata bijection recursively, we get`):
print(b1):
print(`-------------------------------------------------------------`):
print(`Let's digress to see how it is done`):
DF1vv(a1):

print(`------------------------------------------------------------------`):
print(`Going back `):

if a[n-1]<=a[n] then

print(` Since `, a[n-1]<=a[n], ` we have Case I`):



b1:=BreakUpL(b1,an):



if nops(b1) mod 2=1 then
 if b1[nops(b1)]<>[] then
  b1:=[op(b1),[]]:
 else
  b1:=[op(1..nops(b1)-1,b1)]:
 fi:

fi:

print(`The break-up of the output of the recursive step`, b1old, `according  to blocks is`):
print(b1):

r:=nops(b1)/2:
b1p:=[seq(op([b1[2*i],b1[2*i-1]]),i=1..r)]:
print(`and  after the clever Foata interchange`):
print(b1p):
b1:=[seq(op([b1[2*i],b1[2*i-1]]),i=1..r)]:
print(`Catenating, and appending the last letter`, an, `we get`):

b1:=[seq(op(b1[i]),i=1..nops(b1)),an]:
print(b1):

RETURN(b1):


else

print(` Since `, a[n-1]>a[n], ` we have Case II`):
b1:=BreakUpS(b1,an):

if nops(b1) mod 2=1 then
 if b1[nops(b1)]<>[] then
  b1:=[op(b1),[]]:
 else
  b1:=[op(1..nops(b1)-1,b1)]:
 fi:
fi:

print(`The break-up of the output of the recursive step`, b1old, `according  to blocks is`):
print(b1):

r:=nops(b1)/2:
b1p:=[seq(op([b1[2*i],b1[2*i-1]]),i=1..r)]:
print(`And  after the clever Foata interchange`):
print(b1p):

b1:=[seq(op([b1[2*i],b1[2*i-1]]),i=1..r)]:

print(`Catenating, and appending the last letter`, an, `we get`):
b1:=[seq(op(b1[i]),i=1..nops(b1)),an]:

print(b1):

RETURN(b1):

fi:

end:

#Tavla(n): tabulates the Foata Bijection that sends the major index to the number of inversions to all permutations of length n
#Try:
#Tavla(6);
Tavla:=proc(n) local gu,i:
print(`Here is a table of the Foata bijection for all permutations of length`, n):
gu:=permute(n):

for i from 1 to nops(gu) do
print(gu[i], `: `, DF1(gu[i])):
od:

end:


Tavlot:=proc(N) local n:
for n from 1 to N do
Tavla(n):
od:
end:

#TavlaG(a): tabulates the Foata Bijection that sends the major index to the number of inversions to all permutations of 
#1$a[1] ...n$a[n]
#Try:
#TavlaG([2,2,2]);
TavlaG:=proc(a) local n,mu,gu,i:
n:=nops(a):
mu:=[seq(i$a[i],i=1..n)]:

print(`Here is a table of the Foata bijection for all permutations of `, mu):
gu:=permute(mu):

for i from 1 to nops(gu) do
print(gu[i], `: `, DF1(gu[i])):
od:

end: