# HW 17
# Jike Liu

# All the work is based on  C17.txt



# Question 1:

# RandSYT code using the Greene-Nijenhuis-Wilf
# Assumes that Cells(L) and Hook(L,c) are already defined.

Help18:=proc():
print(` RandElt(S), IsCorner(L,c), RemoveCorner(L,c), OneTrial(L), RandSYT(L) `):
end:


# RandElt(S): a uniformly random member of a finite set/list S
RandElt:=proc(S) local T:
T:=[op(S)]:
T[rand(1..nops(T))()]:
end:


# IsCorner(L,c): is c=[i,j] a corner cell of the Ferrers shape L ?
IsCorner:=proc(L,c) local i,j,k:
k:=nops(L):
i:=c[1]:  j:=c[2]:

if not (1<=i and i<=k and 1<=j and j<=L[i]) then
  RETURN(false):
fi:

evalb( j=L[i] and (i=k or L[i+1]<j) ):
end:


# RemoveCorner(L,c): remove the corner cell c from the partition L
RemoveCorner:=proc(L,c) local i,k:
if not IsCorner(L,c) then
  RETURN(FAIL):
fi:

i:=c[1]:
k:=nops(L):

if L[i]>1 then
  [op(1..i-1,L),L[i]-1,op(i+1..k,L)]:
else
  [op(1..i-1,L),op(i+1..k,L)]:
fi:
end:


# OneTrial(L): one GNW "kick-the-buck" trial.
# Starts from a uniformly random cell, then repeatedly chooses
# a uniformly random DIFFERENT cell in the current hook,
# until a corner is reached. Outputs that terminal corner.
OneTrial:=proc(L) local c,H:
if L=[] then
  RETURN(FAIL):
fi:

c:=RandElt( Cells(L) ):

while not IsCorner(L,c) do
  H:=Hook(L,c) minus {c}:
  c:=RandElt(H):
od:

c:
end:


# RandSYT(L): a uniformly-at-random standard Young tableau of shape L
RandSYT:=proc(L) local n,i,c,L1,Y:
if L=[] then
  RETURN([]):
fi:

n:=add(L[i],i=1..nops(L)):

c:=OneTrial(L):
L1:=RemoveCorner(L,c):
Y:=RandSYT(L1):

i:=c[1]:

# put n into the removed corner
if i<=nops(Y) then
  [op(1..i-1,Y), [op(Y[i]),n], op(i+1..nops(Y),Y)]:
else
  [op(Y), [n]]:
fi:
end:

# Test:

PSYT(RandSYT([3,2])):

seq(PSYT(RandSYT([3,2])),t=1..5):



# Question 2: 

N:=10000:
c:=0:

for t from 1 to N do
  Y:=RandSYT([5$5]):
  if Y[1][2]=2 then
    c:=c+1:
  fi:
od:

evalf(c/N);

# Should be around 0.5



# Question 3:

# The exact probability that 2 is in location [1,2] in a uniformly random
# SYT of shape [5$5].

# Proof:
# Let S:=SYT([5$5]).
#
# Let
# A:= {T in S : 2 is in cell [1,2]}
# B:= {T in S : 2 is in cell [2,1]}.
#
# First, every tableau in S lies in exactly one of A or B.
# Indeed, in every standard Young tableau, 1 must be in the upper-left
# corner [1,1], since entries increase along rows and columns.
#
# Now consider the location of 2. It cannot be anywhere except [1,2] or [2,1]:
#
# - It cannot be in [1,j] with j>=3, because then the entry in [1,2]
#   would have to be <2 but >1, impossible.
#
# - It cannot be in [i,1] with i>=3, because then the entry in [2,1]
#   would have to be <2 but >1, impossible.
#
# - It cannot be in [i,j] with i>=2 and j>=2, because then the box above
#   it and the box to the left of it would both have to contain numbers <2,
#   impossible.
#
# Therefore 2 must be either in [1,2] or in [2,1], so S=A union B and
# A intersect B = empty.
#
# Next, define Phi(T)=transpose(T), the tableau obtained by reflecting T
# across the main diagonal.
#
# Since the shape [5$5] is a 5 by 5 square, transposing preserves the shape.
# Also, transpose preserves the property that rows and columns are increasing,
# so Phi maps S to S.
#
# Moreover, transpose swaps the two cells [1,2] and [2,1]. Hence
#
#   Phi: A -> B
#
# is a bijection, with inverse itself.
#
# Therefore nops(A)=nops(B).
#
# Since S is the disjoint union of A and B, we get
#
#   nops(S)=nops(A)+nops(B)=2*nops(A).
#
# Hence
#
#   Prob(2 is in [1,2]) = nops(A)/nops(S) = 1/2.
#
# So the exact probability is
#
#   1/2.



# Question 4: 

# Problem 12587:
# Proof: 
# Let
#   F(q):=1+sum(f(n)*q^n,n=1..infinity).
#
# We will compute F(q), then reduce mod 5.

# For each part-size k, suppose it appears with multiplicity m.
# If m=0, its contribution is 1.
# If m>=1, its contribution to the weight is
#   (-1)^(m-1)*m*q^(m*k).
#
# Therefore
#
#   F(q)=mul( 1+sum((-1)^(m-1)*m*q^(m*k),m=1..infinity), k=1..infinity).

# Now use the identity
#
#   sum((-1)^(m-1)*m*x^m,m=1..infinity)=x/(1+x)^2.
#
# Hence
#
#   1+sum((-1)^(m-1)*m*q^(m*k),m=1..infinity)
#   =1+q^k/(1+q^k)^2
#   =(1+3*q^k+q^(2*k))/(1+q^k)^2.
#
# So
#
#   F(q)=mul((1+3*q^k+q^(2*k))/(1+q^k)^2,k=1..infinity).

# Now reduce mod 5.
# Since
#
#   1+3*x+x^2 = 1-2*x+x^2 mod 5 = (1-x)^2 mod 5,
#
# we get
#
#   F(q)=mul(((1-q^k)/(1+q^k))^2,k=1..infinity)   mod 5.

# Therefore
#
#   F(q)= ( mul((1-q^k)/(1+q^k),k=1..infinity) )^2   mod 5.

# Next, use Jacobi's identity:
#
#   sum((-1)^m*q^(m^2),m=-infinity..infinity)
#   =mul((1-q^(2*r))*(1-q^(2*r-1))^2,r=1..infinity).
#
# But also
#
#   mul((1-q^k)/(1+q^k),k=1..infinity)
#   =mul((1-q^k)^2/(1-q^(2*k)),k=1..infinity)
#   =mul((1-q^(2*r))*(1-q^(2*r-1))^2,r=1..infinity).
#
# Hence
#
#   mul((1-q^k)/(1+q^k),k=1..infinity)
#   =sum((-1)^m*q^(m^2),m=-infinity..infinity).

# So
#
#   F(q)= ( sum((-1)^m*q^(m^2),m=-infinity..infinity) )^2   mod 5.

# Expanding the square gives
#
#   F(q)=sum( (-1)^(a+b)*q^(a^2+b^2), a,b in Z )   mod 5.
#
# If a^2+b^2=n, then
#
#   a^2+b^2 = a+b mod 2,
#
# so
#
#   (-1)^(a+b)=(-1)^n.
#
# Therefore the coefficient of q^n in the above series is
#
#   (-1)^n * r_2(n),
#
# where r_2(n) is the number of representations of n as a^2+b^2
# with a,b in Z.

# Hence
#
#   f(n)=(-1)^n*r_2(n)   mod 5.
#
# In particular, if n is not a sum of two squares, then r_2(n)=0, so
#
#   f(n)=0 mod 5.
#
# Therefore, if n is not the sum of two squares, then 5 divides f(n).



# End of the file.