#OK to post homework
#William Wang, 9/29/2020, Assignment 8

#Code from Lecture 8
with(combinat):

GFseq := proc(f, x, N) local f1, i:
f1 := taylor(f, x = 0, N + 1):
[seq(coeff(f1, x, i), i = 0 .. N)]:
end:

CompsGFk := proc(S, x, k) local s:
sort(expand(add(x^s, s in S)^k)):
end:

CompsGF := proc(S, x) local s:
if not (type(S, set) and 0 < min(op(S))) then
 print(`Bad input`);:
 RETURN(FAIL):
fi:
factor(1/(1 - add(x^s, s in S))):
end:

CompsGFcon := proc(a, C, x) local c:
factor(1/(1 - add(x^c, c in C)/(1 - x^a))):
end:





#1.
#i. The number of 10 letter words in the alphabet {1,4,6} that add up to 201

coeff(CompsGFk({1, 4, 6}, x, 10), x, 201);
                               0

#ii. The number of words in the alphabet {2,3,7} of any length that add up to 411

GFseq(CompsGF({2, 3, 7}, x), x, 411)[412];
   4741685087960650685822461715671211099459856575685906645393

#iii. The number of sequences of any length whose entries are either 1 (mod 5) or 4 (mod 5) that add up to 341

GFseq(CompsGFcon(5, {1, 4}, x), x, 341)[342];
  234303065886413369536085349033389448858104244347193374824719





#2.
Pnk := proc(n, k) local i, w; option remember:
if n < k then RETURN({}):
elif k = n then RETURN({[n]}):
else {seq(seq([k, op(w)], w in Pnk(n - k, i)), i = 1 .. k)}:
fi:
end:

Pnk(5, 1);
                       {[1, 1, 1, 1, 1]}

Pnk(5, 2);
                   {[2, 2, 1], [2, 1, 1, 1]}

Pnk(5, 3);
                      {[3, 2], [3, 1, 1]}

Pnk(5, 4);
                            {[4, 1]}

Pnk(5, 5);
                             {[5]}





#3.
pnk := proc(n, k) local i, w; option remember:
if k > n then RETURN(0):
elif k = n then RETURN(1):
else add(pnk(n - k, i), i = 1 .. k):
fi:
end:

pnk(5, 1);
                               1

pnk(5, 2);
                               2

pnk(5, 3);
                               2

pnk(5, 4);
                               1

pnk(5, 5);
                               1





#4.
pn := proc(n) local i:
if n = 0 then 1:
else add(pnk(n, i), i = 1 .. n):
fi:
end:

pn(5);
                               7

seq(pn(n), n = 0 .. 30);
1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, 56, 77, 101, 135, 176, 231, 

  297, 385, 490, 627, 792, 1002, 1255, 1575, 1958, 2436, 3010, 

  3718, 4565, 5604

#The OEIS number of this sequence is A000041





#5.
[seq(pn(5*n + 4) mod 5, n = 1 .. 50)];
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 

  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 

  0, 0, 0, 0, 0, 0, 0, 0]


[seq(pn(7*n + 5) mod 7, n = 1 .. 50)];
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 

  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 

  0, 0, 0, 0, 0, 0, 0, 0]


[seq(pn(11*n + 6) mod 11, n = 1 .. 50)];
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 

  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 

  0, 0, 0, 0, 0, 0, 0, 0]


#6.
#Srinivasa Ramanujan discovered that pn(5n+4) = 0 (mod 5), pn(7n+4) = 0 (mod 7), and pn(11n+6)=0 (mod 11), where n = 1,2,3,...,infinity. (Ramanujan's Partition Congruences)