#OK to post homework
#Karnaa Mistry, 12/13/20, Assignment HW #24

with(combinat):

# 1.

# i) pnC(97,{1,4,5},7) = 108236
# ii) pnD(97,3) = 19990




# 2.

#pnDC(n,d,C,m): joint generalization of pnD and pnC
pnDC:=proc(n,d,C,m) local k:

add(pnkDC(n,k,d,C,m),k=1..n):

end:

#pnkDC(n,k,d,C,m): helper proc for pnDC
pnkDC:=proc(n,k,d,C,m) local i,k1,S:
option remember:

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

if (n=1 and not(k=1)) then return(0): fi:

if not member(k mod m, C) 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 and k=1 then
 if member(1,C) then
   RETURN(1):
 else
  RETURN(0):
 fi:
fi:

S:=0:

for k1 from 1 to k-d do

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

od:

return(S):

end:

# i) This does work for various values of n,d,C,m

# ii) seq(pnDC(N,1,{1},2),N=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
# This is in the OEIS: A000700

# iii) seq(pnDC(N,2,{1,4},5),N=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
# This is in the OEIS: A203776




# 3.

# We achieve the prod(1 / (1 - q^i),i=1..infinity) from (1 + q^i + q^(2i) + q^(3i) + ...){for parts i}
# This covers all the partitions we would want, but if we want distinct partitions we set it up
# slightly differently to get a sum 1 + q^i + q^(2i) + ... such that we have ONLY chosen each
# part i ONCE or NOT AT ALL.  Since this product goes to infinity, we can factor it like:

# (1+q)(1+q^2)(1+q^3)...
# There will certainly be a coefficient of some q^k, since this product is infinite.

# Most importantly, for each factor, we either choose to have that q^i, or to not have it in the
# multiplication of q^i's to get our power n (the number we want to find the # of distinct partitions 
# for).  For example, we could not possibly have q^2 more than once in our q^200, meaning that the
# number 2 is not included more than once in our partition (distinct parts).

# Therefore, we have the product(1+q^i,i=1..infinity) as our G.F. of the sequence for distinct partitions.




# 4.

# Using the prod(1 / (1 - q^i),i=1..infinity) that covers all partitions, we do not have to account
# for non-distinct parts this time.  So, our only restriction would be keeping odd parts, which can
# be done by only keeping the factors with odd powers, like 1 / ( (1-q)(1-q^3)(1-q^5)... ).  This 
# relates to the sum (1 + q^i + q^(2i) + q^(3i) + ...){for all i}, where we take out the even
# non-zero powers, namely 2i, 4i, etc...

# We are left with 1 / ((1-q)(1-q^3)(1-q^5)...) as the G.F. for the sequence of odd partitions




# 5.

# We have the GF for odd partitions: 1 / ( (1-q)(1-q^3)(1-q^5)... )
# Let's try to make it look more like the GF for distinct partitions, so multiply the numerator
# and denominator by the factors (1+q^i) with even powers:

# 1 / ( (1-q)(1-q^3)(1-q^5)... )  -->  (1-q^2)(1-q^4)(1-q^6)... / ( (1-q)(1-q^2)(1-q^3)(1-q^4)(1-q^5)... )
# This equals prod(1-q^(2i)) / prod(1-q^i) (all i from 1 to infinity)

# Inspecting (1-q^(2i)) / (1-q^i), we can factor the numerator as (1+q^i)(1-q^i) because:
# (1+x)(1-x) = (1-x^2)

# Then, the (1-q^i)'s cancel, and our leftover element is (1+q^i).  This is in the infinite product,
# and since we know the GF for distinct partitions is prod(1+q^i,i=1..infinity), we can see that
# through algebraic manipulation, the GF for distinct partitions = GF for odd partitions.