#OK to post homework
#George Spahn, 4/14/2021, Assignment 22

# TotalSYT(n)  inputs a positive integer n, and outputs the total 
# number of standard Young tableaux with n cells
TotalSYT:=proc(n) local pars:
pars := Pn(n):
add(seq(syt(pars[i]),i=1..nops(pars))):
end:

# seq(TotalSYT(i), i = 1 .. 10)
#    = 1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496

# This is sequence A000085 in the OEIS

# TotalSYTpower(n,k)  inputs a positive integer n, and outputs
# the total number of k-tuples of standard Young tableaux
# of the same shape with n cells 
TotalSYTpower := proc (n,k) local pars:
pars := Pn(n):
add(seq(syt(pars[i])^k,i=1..nops(pars))):
end:

# k = 2 gives the sequence of factorial numbers
# For k = 3 the sequence is given by A130721


randomSYT:=proc(L) local corner_indices,i,die,Lprimes,d,r1:

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

corner_indices := {nops(L)}:
for i from 1 to nops(L)-1 do
 if L[i]>L[i+1] then
  corner_indices := corner_indices union {i}:
 fi:
od:

die := [0$(nops(corner_indices))]:
Lprimes:= [0$(nops(corner_indices))]:
for i from 1 to nops(corner_indices) do
 Lprimes[i]:= [op(1..corner_indices[i]-1,L),L[corner_indices[i]]-1,op(corner_indices[i]+1..nops(L),L)]:
 if i = nops(corner_indices) and L[-1] = 1 then
  Lprimes[i]:=[op(1..nops(L)-1,L)]:
 fi:
 die[i] := syt(Lprimes[i]):
od:
d:=LD(die):

r1:=randomSYT(Lprimes[d]):
AP(r1,corner_indices[d],add(L)):

end:








# For the challenge problems, I tried counting the 2 row
# Young Tableaux by first doing binom(a1+a2,a2) to pick the rows,
# then sorting each row in increasing order,
# and then using inclusion exclusion to remove the ones where specific 
# columns were out of order. It didn't seem to simplify nicely so I gave up.











#LD(L): Inputs a list of positive integers L (of n:=nops(L) members)
#outputs an integer i from 1 to n with the prob. of i being
#proportional to L[i]
#For example LD([1,2,3]) should output 1 with prob. 1/6
#output 2 with prob. 1/3
#output 3 with prob. 3/6=1/2
LD:=proc(L) local n,i,su,r:
n:=nops(L):
r:=rand(1..convert(L,`+`))():
su:=0:

for i from 1 to n do
 su:=su+L[i]:
  if r<=su then
    RETURN(i):
  fi:
od:
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 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