#Ok to post homework
#Tifany Tong, December 13th, 2020, HW #24


# 1.) 
# (i) nops(PnC(97,{1,4},5) = 59239
# (ii) nops(PnD(97,3)) = 19990

# 2.) 

pnkDC := proc(n, k, C, m, d) local k1, S:
option remember:
if n < k then RETURN(0): fi:
if k = n then 
   if member(k mod m, C) then RETURN(1):
   else RETURN(0): fi: fi: 
if n = 1 then 
   if member(1, C) and k = 1 then RETURN(1):
   else RETURN(0): fi: 
fi:
if not member(k mod m, C) then RETURN(0): fi:
S := 0:

for k1 to k - d do
    if member(k1 mod m, C) then S := S + pnkDC(n - k, k1, C, m, d): fi: 
od:
S: 
end:

pnDC := proc(n, d, C, m) local k:
add(pnkCD(n, k, C, m, d), k = 1 .. n):
end: 

# (i) pnCD(10,0,{1,4},5) = 6
#     pnC(10,{1,4},5) = 6
#     pnCD(10,3,{0},1) = 4
#     pnD(10,3) = 4

# (ii) [seq(pnDC(k,1,{1},2),k=1..40)] = [1, 0, 1, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 4, 5, 5, 5, 6, 7, 8, 8, 9, 11, 12, 12, 14, 16, 17, 18, 20, 23, 25, 26, 29, 33, 35, 37, 41, 46]
# A000700

# (iii) [seq(pnDC(k, 2, {1, 4}, 5), k = 1 .. 40)] = 
# [1, 0, 0, 1, 1, 1, 1, 0, 1, 2, 2, 1, 1, 2, 3, 3, 2, 2, 3, 5, 5, 3, 3, 5, 7, 7, 6, 5, 7, 11, 11, 8, 8, 12, 15, 15, 13, 12, 16, 22]
# A203776

# 3.) For distinct partitions, we can choose to either include or not include each value, since each value in the partition is distinct (no repeats).
# Thus, the weight enumerator of whether we want to include a value is: 1 + q^i where i is the number we are deciding on whether to include or not.

# We multiply these weight enumerators together gives us the product of (1+q^i) for i=1 to infinity. 

# 4.) For only odd partitions (all the components being odd), we can only include the odd values (1,3,5,7,...). Thus, this will be reflected in our
# weight enumerators. For example, we can use as many 1's, 3's, etc as we want, but we cannot use 2's,4's, etc. Our weight enumerators will be:
# (1+q+q^2+q^3+....) * (1+q^3+q^6.....) * (1+q^5+q^10+.....)*..... 

# This can be represented as 1/(1-q)*(1-q^3)*(1-q^5)..... = the produce of 1/(1-q)^i where i = 1,3,5,7,.... infinity

# 5.) We can represent the product (1+q^i) for i=1 to infinity as:

# (1+x)*(1-x)    (1+x^2)*(1-x^2)
# ----------- *  --------------- * ............ = 
#    (1-x)           (1-x^2)

# (1-x^2) * (1-x^4) * (1-x^6) * ...
# --------------------------------   =
#         (1-x)(1-x^2)(1-x^3)* ...

#                1
# --------------------------------
#  (1-x)(1-x^3)(1-x^5).....

# Thus, we've shown that the product of (1+q^i) for i=1 to infinity is the same as 1/(1-q)*(1-q^3)*.....