# HW 21
# Jike Liu

read C21.txt;

# Question 2:
# We are studying independently for now; our first meeting will take place on Monday.

# Question 3: 


eknVC:=proc(k,n,x) local t,i:
coeff(expand(mul(1+x[i]*t,i=1..n)),t,k):
end:


# Question 4:

hkn:=proc(k,n,x) local t,F,i:
F:=taylor(1/mul(1-t*x[i],i=1..n), t=0, k+1):
expand(coeff(convert(F,polynom), t, k)):
end:

# Question 5: 

#CheckNewton(k,n): checks Newton's identity for the given k,n
#k*e_k = Sum_{i=1..k} (-1)^(i-1) e_{k-i} p_i

CheckNewton:=proc(k,n) local i,LHS,RHS,e,x:

if not (1<=k and k<=n) then
   ERROR(`Need 1<=k<=n`):
fi:

e:=proc(j)
   if j=0 then
      1:
   else
      eknVC(j,n,x):
   fi:
end:

LHS:=expand(k*e(k)):
RHS:=expand(add((-1)^(i-1)*e(k-i)*pkn(i,n,x),i=1..k)):

evalb(LHS=RHS):

end:

seq(seq(CheckNewton(k,n),k=1..n),n=1..5);
# true, true, true, true, true, true, true, true, true, true, true, true, true, true, true


# Question 6: 

#Left side:
#   [A,j,l] with j in A.
#
#Right side:
#   [A,j,l] with j not in A and l>0.
#
#Then the two directions of the bijection are:
#
#phiLR([A,j,l]) = [A minus {j}, j, l+1]
#phiRL([A,j,l]) = [A union {j}, j, l-1].
#
#These are inverse maps, and together they form the sign-reversing involution T.
#This makes Newton's identity by pairing terms that cancel.


#SubsetsK(n,k): the set of k-subsets of {1,...,n}
SubsetsK:=proc(n,k) local S:
option remember:

if k<0 or k>n then
   RETURN({}):
fi:

if k=0 then
   RETURN({{}}):
fi:

if n=0 then
   RETURN({}):
fi:

SubsetsK(n-1,k) union {seq(S union {n}, S in SubsetsK(n-1,k-1))}:

end:


#LeftNewton(n,k): the "left side" of the bijection
#the set of triples [A,j,l] such that
#A subset of {1,...,n}, j in A, l>=0, and |A|+l=k
LeftNewton:=proc(n,k) local m,A,j,S:
S:={}:

for m from 1 to min(n,k) do
  for A in SubsetsK(n,m) do
    for j in convert(A,list) do
      S:=S union {[A,j,k-m]}:
    od:
  od:
od:

S:

end:


#RightNewton(n,k): the "right side" of the bijection
#the set of triples [A,j,l] such that
#A subset of {1,...,n}, j not in A, l>0, and |A|+l=k
RightNewton:=proc(n,k) local m,A,j,S:
S:={}:

for m from 0 to min(n,k-1) do
  for A in SubsetsK(n,m) do
    for j from 1 to n do
      if not member(j,A) then
        S:=S union {[A,j,k-m]}:
      fi:
    od:
  od:
od:

S:

end:


#NewtonSet(n,k): the full set A(n,k)
NewtonSet:=proc(n,k)
LeftNewton(n,k) union RightNewton(n,k):
end:


#phiLR(s): the map from LeftNewton(n,k) to RightNewton(n,k)
#[A,j,l] -> [A\{j},j,l+1]
phiLR:=proc(s) local A,j,l:

A:=s[1]:
j:=s[2]:
l:=s[3]:

if not member(j,A) then
   ERROR(`phiLR expects j in A`):
fi:

[A minus {j}, j, l+1]:

end:


#phiRL(s): the map from RightNewton(n,k) to LeftNewton(n,k)
#[A,j,l] -> [A union {j},j,l-1]
phiRL:=proc(s) local A,j,l:

A:=s[1]:
j:=s[2]:
l:=s[3]:

if member(j,A) then
   ERROR(`phiRL expects j not in A`):
fi:

if l<=0 then
   ERROR(`phiRL expects l>0`):
fi:

[A union {j}, j, l-1]:

end:


#TNewton(s): the involution on the whole set NewtonSet(n,k)
TNewton:=proc(s) local A,j,l:

A:=s[1]:
j:=s[2]:
l:=s[3]:

if member(j,A) then
   [A minus {j}, j, l+1]:
else
   [A union {j}, j, l-1]:
fi:

end:


#wtNewton(s,x): the weight of [A,j,l]
#w(A,j^l)=(-1)^|A| * (Product_{a in A} x[a]) * x[j]^l
wtNewton:=proc(s,x) local A,j,l,a:

A:=s[1]:
j:=s[2]:
l:=s[3]:

(-1)^nops(A)*mul(x[a],a in A)*x[j]^l:

end:


#SumWtNewton(n,k,x): the sum of the weights of all members of NewtonSet(n,k)
SumWtNewton:=proc(n,k,x) local s:
expand(add(wtNewton(s,x), s in NewtonSet(n,k))):
end:

seq(seq(expand(SumWtNewton(n,k,x)), k=1..n), n=1..5);
# 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0