#HomeWork#16
#Please do not post homework
#Abrar Almahmeed, March 29

#Question 1:

AntiRS := proc(pair)
local P,Q,n,k,i,j,x,pi,row:
P := pair[1]:
Q := pair[2]:
if pair=[[[],[]],[[],[]]] then 
RETURN ([]):
fi:
n := add(nops(P[i]), i=1..nops(P)): #number of entries
pi := []:
k := n:
while k >= 1 do #find k in Q
for i from 1 to nops(Q) do
for j from 1 to nops(Q[i]) do
if Q[i][j] = k then
x := P[i][j]: # take k from P
P[i] := [op(1..j-1,P[i]), op(j+1..-1,P[i])]: # remove it from P

row:=i:
while row > 1 do
row := row - 1:
j := nops(P[row]):
while j >= 1 do
if P[row][j] < x then
x, P[row][j] := P[row][j], x:
break:
fi:
j := j - 1:
od:
od:
pi := [x, op(pi)]:
fi:
od:
od:
k := k - 1:
od:
return pi:
end:


##Check:

RS([2,3,5,1,4]);
           [[[1, 3, 4], [2, 5]], [[1, 2, 3], [4, 5]]]

AntiRS([[[1,3,4],[2,5]], [[1,2,3],[4,5]]]);
                        [2, 3, 5, 1, 4]

AntiRS(RS([2,3,5,1,4]));
                        [2, 3, 5, 1, 4]

seq({seq(evalb(AntiRS(RS(pi))=pi), pi in permute(n))},n=2..7);

         {true}, {true}, {true}, {true}, {true}, {true}


seq({seq(evalb(RS(AntiRS(s))=s),s in SYTpairs(n))},n=2..7);

         {true}, {true}, {true}, {true}, {true}, {true}

###################################################################

#Question 2:


seq({seq(evalb(RS([seq(Search(i,pi),i=1..nops(pi))])=[op(RS(pi))[2],op(RS(pi))[1]]),pi in permute(n))},n=2..7);

         {true}, {true}, {true}, {true}, {true}, {true}



#claim: If the Robinson–Schensted correspondence associates tableaux (P, Q) to a permutation pi, then it associates (Q, P) to the inverse permutation pi^(−1).(i.e. if RS(pi)=(P,Q), then RS(pi^(-1))=(Q,P)), where P is the insertion tableaux dependes on the values of pi, and Q is the recording tableau.

#Proof:

The inverse of a permutation pi  is the permutation that satisfies pi^(-1)(pi(i))=i,
(i.e. if pi maps position i to value j, the inverse pi^(-1) maps position j back to i).

This switches the rules where P become the recording tableau and Q records the order of the insertion.

Therefore,  RS(pi^(-1))=(Q,P)).