#OK to post homework
#Kent Mei, 10/4/20, Assignment 8

#---------------------------------
#Part 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 
#So, there are 0 10-letter words in the alphabet {1,4,6} that add-up to 201.


#(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
#So, there are 4741685087960650685822461715671211099459856575685906645393 words in the alphabet {2,3,7} that add-up to 411.

#(iii) The number of sequences of any length whose entries are either 1 (mod 5) or 4 (mod 5) and that add up to 341
#GFseq(CompsGFcon(5,{1,4},x),x,341)[342] = 234303065886413369536085349033389448858104244347193374824719
#So, there are 234303065886413369536085349033389448858104244347193374824719 sequences whose entries are either 1 (mod 5) or 4 (mod 5) and add up to 341.


#---------------------------------
#Part 2

Pnk:=proc(n,k) local Ans, W, w, i:
option remember:

if n < 0 or k < 0 then 
 print(`Both n and k should be nonnegative`):
 RETURN(FAIL):
fi:

if n = 0 and k = 0 then
 return {[]}:
fi:

if k = 0 then
 return {}:
fi:

if k > n then
 return {}:
fi:

Ans := {}:
W := {}:

for i from 0 to k do
	W := W union Pnk(n-k,i):
od:

Ans := {seq([k,op(w)], w in W)}:
Ans:

end:

#---------------------------------
#Part 3

pnk:=proc(n,k) local Ans, i:
option remember:

if n < 0 or k < 0 then 
 print(`Both n and k should be nonnegative`):
 RETURN(FAIL):
fi:

if n = 0 and k = 0 then
 return 1:
fi:

if k = 0 then
 return 0:
fi:

if k > n then
 return 0:
fi:

Ans := 0:

for i from 0 to k do
	Ans := Ans + pnk(n-k,i):
od:

Ans:

end:

#---------------------------------
#Part 4

pn:=proc(n) local Ans, i:
option remember:

if n <= 0 then 
 print(`n needs to be positive`):
 RETURN(FAIL):
fi:


Ans := 0:

for i from 0 to n do
	Ans := Ans + pnk(n,i):
od:

Ans:

end:

#seq(pn(n),n=0...30) = FAIL, 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 (pn(n) is defined only on the positive integers)
#The OEIS sequence number is A41.

#---------------------------------
#Part 

#[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]

#---------------------------------
#Part 6

#The mathematician Srinivasa Ramanujan discovered the above facts.