#OK to post
#Yuxuan Yang, April 17th, Assignment 23

with(combinat):

#2
#SYTpairs(n)：
#inputs a positive integer n and outputs the set of pairs of standard Young tableaux of the same shape [S,T] each with n cells.
SYTpairs:=proc(n) local S:
S:=Pn(n):
{seq(seq(seq([a,b],b in SYT(S[i])),a in SYT(S[i])),i=1..nops(S))}:
end:





#3
RS:=proc(pi) local Y,i,don,j,ny1,ny2:
Y:=[[[pi[1]]],[[1]]]:
for i from 2 to nops(pi) do
 ny1:=RS1(Y[1],pi[i]):
 don:=0:
 for j from 1 to nops(Y[2]) do
  if nops(ny1[j])>nops(Y[2][j]) then
   ny2:=AP(Y[2],j,i):
   don:=1:
  fi:
 od:
 if don=0 then 
  ny2:=AP(Y[2],nops(Y[2])+1,i):
 fi:
 Y:=[ny1,ny2]:
od:
Y:
end:




#4
InvRS:=proc(Y) local pi,i,Y1,outp:
pi:=[]:
Y1:=Y:
for i from 1 to add(nops(Y[2][j]),j=1..nops(Y[2])) do
 outp:=InvRS1(Y1):
 Y1:=[op(1..2,outp)]:
 pi:=[outp[3],op(pi)]:
od:
pi:
end:


InvRS1:=proc(Y) local i,j,k,inew,y1,y2,mem:
#find the size of Y[2], also the largest number
inew:=add(nops(Y[2][i]),i=1..nops(Y[2])):
#find the row of inew in Y[2]
for i from 1 to nops(Y[2]) while Y[2][i][-1]<>inew do od:
#give the last Y[2]
y2:=Y[2]:
y2[i]:=[op(1..nops(y2[i])-1,y2[i])]:
#give the last Y[1]
y1:=Y[1]:
mem:=Y[1][i][-1]:
y1[i]:=[op(1..nops(y1[i])-1,y1[i])]:
for j from i-1 by -1 to 1 do 
 #y1[j][k-1] is the last one < mem
 for k from 1 to nops(y1[j]) while y1[j][k]<mem do od:
 y1[j][k-1]:=mem:
 mem:=Y[1][j][k-1]:
od:
[y1,y2,mem]:
end:



#5

Proof is in the pdf attached



















#C23.txt:  Maple code for Lecture 23

Help23:=proc(): print(` Ins(Y,i,m), RS1(Y,m) , RSleft(pi), AllSYT(n) `): end:

#Ins(Y,i,m): Inputs a (partially filled tableux Y,
#a row i, between 1 and nops(Y)+1 and an integer m
#and tries to place it LEGALLY at row i
#(if it is larger than all the current entries of row i
#and does not stick out, i=1 OR nops(Y[i])<nops(Y[i-1])
#and outputs the new tableau and either 0 or the new bumpbee
Ins:=proc(Y,i,m) local Y1,j:
if not (1<=i and i<=nops(Y)+1) then
 RETURN(FAIL):
fi:

if i=nops(Y)+1 then
  RETURN([op(Y),[m]],0):
fi:

if i=1 then 
  if m>=Y[1][-1] then
    RETURN([[op(Y[1]),m], op(2..nops(Y),Y)],0):
   fi:
fi:

for j from 1 to nops(Y[i]) while m>Y[i][j] do od:

if j=nops(Y[i])+1  and (i=1 or nops(Y[i])<nops(Y[i-1])) then

#corrected after class , Maple does not like op(m..n,L) if m-n>=2
if j+1<=nops(Y[i]) then
  RETURN ([op(1..i-1,Y),[op(1..j-1,Y[i]),m,op(j+1..nops(Y[i]),Y[i])],
op(i+1..nops(Y),Y)],0):
else

RETURN ([op(1..i-1,Y),[op(1..j-1,Y[i]),m],
op(i+1..nops(Y),Y)],0):
fi:


else
RETURN([op(1..i-1,Y),[op(1..j-1,Y[i]),m,op(j+1..nops(Y[i]),Y[i])],
op(i+1..nops(Y),Y)],Y[i][j]):
fi:

end:

#RS1(Y,m): ONE STEP OF THE RS algorithm
RS1:=proc(Y,m) local i,Y1:

Y1:=Ins(Y,1,m):
if Y1[2]=0 then
  RETURN(Y1[1]):
fi:

#continued after class
for i from 2 to nops(Y)+1 while Y1[2]<>0 do
Y1:=Ins(Y1[1],i,Y1[2]):
od:
Y1[1]:
end:

with(combinat):

#RSleft(pi): The left tableau,S of the pair (S,T) that is the output
#of the Robinson-Scheastead mapping
RSleft:=proc(pi) local Y,i:
Y:=[[pi[1]]]:
for i from 2 to nops(pi) do
 Y:=RS1(Y,pi[i]):
od:
Y:
end:

#AllSYT(n): The set of all Standard Young Tableau with n cells
AllSYT:=proc(n) local S:
S:=Pn(n):
{seq(op(SYT(S[i])),i=1..nops(S))}:
end:

#OLD STUFF
#C22.txt
Help22:=proc(): print(` Pn(n), AP(Y,i,m), SYT(L) , AllSYT(n) `): end:

#Ap(Y,i,m):write a procedure that inputs a Standard Young Tableau
#and an integer i between 1 and nops(Y)+1 and inserts the
#entry m at  the end of the i-th row, or if i=nops(Y)+1 make
#a new row with 1 cell occupied with m
AP:=proc(Y,i,m):

if i=nops(Y)+1 then
 RETURN([op(Y),[m]]):
fi:


if i>1 and nops(Y[i])=nops(Y[i-1]) then
  RETURN(FAIL):
fi:

[op(1..i-1,Y),[op(Y[i]),m],op(i+1..nops(Y),Y)]:


end:

#SYT(L): inputs an integer partion (given as a weakly decreasing
#list of POSITIVE integers OUTPUTS the LIST of
#Standard Young Tableax of shape L (n=Number of boxes of L)
#(A way of filling 1, ..., n in the boxes such that horiz. and
#vertically they are increasing
SYT:=proc(L) local n,L1,S,S1,i,j:
option remember:
n:=add(L):

if n=1 then 
  RETURN([[[1]]]):
fi:

S:=[]:

for i from 1 to nops(L)-1 do
 if L[i]>L[i+1] then
  L1:=[op(1..i-1,L),L[i]-1,op(i+1..nops(L),L)]:
  S1:=SYT(L1):
 S:=[op(S), seq(AP(S1[j],i,n),j=1..nops(S1))]:
 fi:
od:


 if L[-1]>1 then
  L1:=[op(1..nops(L)-1,L), L[nops(L)]-1 ]:
  else
  L1:=[op(1..nops(L)-1,L)]:
 fi:

 S1:=SYT(L1):
 S:=[op(S), seq(AP(S1[j],nops(L),n),j=1..nops(S1))]:

S:

end:



#syt(L): inputs an integer partion (given as a weakly decreasing
#list of POSITIVE integers OUTPUTS the NUMBER of
#Standard Young Tableax of shape L (n=Number of boxes of L)
#(A way of filling 1, ..., n in the boxes such that horiz. and
#vertically they are increasing
syt:=proc(L) local n,L1,S,S1,i,j:
option remember:
n:=add(L):

if n=1 then 
  RETURN(1):
fi:

S:=0:

for i from 1 to nops(L)-1 do
 if L[i]>L[i+1] then
  L1:=[op(1..i-1,L),L[i]-1,op(i+1..nops(L),L)]:
  S:=S+syt(L1):
 
fi:
od:


 if L[-1]>1 then
  L1:=[op(1..nops(L)-1,L), L[nops(L)]-1 ]:
  else
  L1:=[op(1..nops(L)-1,L)]:
 fi:

 S:=S+syt(L1):
S:
end:

##FROM C11.txt
#Pnk(n,k): The LIST of integer partitions of n with largest part k
Pnk:=proc(n,k) local k1,L,L1:
option remember:

if not (type(n,integer) and type(k,integer) and n>=1 and k>=1 )then
 RETURN([]):
fi:
 
if k>n then
 RETURN([]):
fi:

if k=n then
 RETURN([[n] ]):
fi:

L:=[]:

for k1 from min(n-k,k) by -1 to 1 do
 L1:=Pnk(n-k,k1):
 L:=[op(L), seq([k, op(L1[j])],j=1..nops(L1))]:
od:

L:

end:

#Pn(n): The list of integer partitions of n in rev. lex. order
Pn:=proc(n) local k:option remember:[seq(op(Pnk(n,n-k+1)),k=1..n)]:end:
#END FROM C11.txt


#END OLD STUFF