#OK to post homework
#Karnaa Mistry, 10/04/20, Assignment HW #8

with(combinat):


# 1. 

# (i) 0
# (ii) 4741685087960650685822461715671211099459856575685906645393
# (iii) 234303065886413369536085349033389448858104244347193374824719




# 2.

#Pnk(n,k): inputs non-negative integers n and k and outputs the SET of all partitions of n whose LARGEST part is k
Pnk:=proc(n,k) local P1,P2,i:
option remember:

if k>n then RETURN({}): fi:
if k=n then RETURN({[n]}): fi:

P1:={seq(op(Pnk(n-k,i)),i=1..k)}:
P2:={}:
for i from 1 to numelems(P1) do
  P2:= P2 union {[k,op(P1[i])]}:
od:

RETURN(P2):

end:




# 3.

#pnk(n,k): inputs non-negative integers n and k and outputs the NUMBER of partitions of n whose LARGEST part is k
pnk:=proc(n,k) local p1,p2,i:
option remember:

if k>n then RETURN(0): fi:
if k=n then RETURN(1): fi:

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

RETURN(p2):

end:




# 4.

#pn(n): inputs a positive integer n and outputs the NUMBER of partitions of n
pn:=proc(n) local p,i:
option remember:

if n<0 then RETURN(0): fi:
if n=0 then RETURN(1): fi:

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

RETURN(p):

end:

# The OEIS A number of the sequence seq(pn(n),n=0...30) is A000041, "a(n) is the number of partitions of n (the partition numbers)."




# 5. 

# They are each just fifty zeroes: [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 these partition congruences modulo 5, 7, and 11
# https://en.wikipedia.org/wiki/Ramanujan%27s_congruences