#OK to post homework
#William Wang, 12/7/2020, Assignment 24

#1.
#i. How many integer partitions are there of 97 where each part, upon division by 7, gives us remainder in the set {1,4,5}?
pnC(97, {1, 4, 5}, 7);
  108236
#ii. How many integer partitions are there of 97 where the difference between consecutive parts is at least 3? 
pnD(97, 3);
  19990



#2.
pnkCD := proc(n, k, C, m, d) local S, k1: 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) 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 + pnkCD(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. Check that pnDC(n,0,C,m) gives the same output as pnC(n,C,m) and pnDC(n,d,{0},1) gives the same output as pnD(n,d)
#Check that pnDC(n,0,C,m) gives the same output as pnC(n,C,m)
S := {{1, 2, 3}, {1, 2, 4}, {2, 3, 4}, {3, 4, 5}, {4, 5, 6}};
{seq(seq(seq(evalb(pnDC(n, 0, C, m) = pnC(n, C, m)), m = 1 .. n), n = 1 .. 30), C in S)};
  {true}

#Check that pnDC(n,d,{0},1) gives the same output as pnD(n,d)
{seq(seq(evalb(pnDC(n, d, {0}, 1) = pnD(n, d)), d = 1 .. n), n = 1 .. 20)};
  {true}

#ii. Use it to find the first 40 terms of the sequence enumerating partitions that are both odd and distinct. Is it in the OEIS? What is the A number?
seq(pnDC(i, 1, {1}, 2), i = 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
#Yes, this is in the OEIS. The A number is A000700.

#iii. Use it to find the first 40 terms of the sequence enumerating partitions such that the difference between consecutive entries is at least 2, and that each entry gives remainder 1 or 4 when divided by 5. Is it in the OEIS? If it is, what is the A number?
seq(pnDC(i, 2, {1, 4}, 5), i = 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
#Yes, this is in the OEIS. The A number is A203776.



#3.
Look at the infinite set of all integer partitions regardless of n
Weight([a1,a2,a3,...,ak]) = q^(a1+a2+a3+...+ak)
When we pick a random integer partition we make the following decisions:
The number of 1's: Zero? One? Two?
The number of 2's: Zero? One? Two?
And so on until n
Partitions of n = (Partitions of n only using 1) x (Partitions of n only using 2) x (Partitions of n only using 3) ...
{[],[1],[1,1],[1,1,1],...} x {[],[2],[2,2],[2,2,2],...} x {[],[3],[3,3],[3,3,3],...} ...
|A x B x C x D|_q = |A|_q x |B|_q x |C|_q x |D|_q
(1+q+q^2+q^3+...) x (1+q^2+q^4+q^6...) x (1+q^3+q^6+q^9...) x ... = 1/((1-q)(1-q^2)(1-q^3)...)

The above is the generating function of the total number of partitions of n.
To get the generating function of the sequence enumerating distinct partitions,
we simply note that distinct means that in every partition, no number can be present twice.
Therefore, the generating function for the number of distinct partitions of n is given by
(1+q)(1+q^2)(1+q^3)... = Product(1+q^i, i=1..infinity)



#4.
For odd partitions, the following decisions are made:
The number of 1's: Zero? One? Two?
The number of 3's: Zero? One? Two?
And so on for all positive odd integers until n
The number of 2's, 4's, etc. (even integers) in the partition is 0.
Thus the number of odd partitions of n = (Partitions of n only using 1) x (Partitions of n only using 3) x (Partitions of n only using 5) ...
So we get that the number of odd partitions of n is equal to 1/((1-q)(1-q^3)(1-q^5)...), or Product(1/(1-q^(2*i+1)),i=0..infinity).



#5.
Combining the above, we just have to show that Product(1+q^i, i=1..infinity) is equal to Product(1/(1-q^(2*i+1)),i=1..infinity).
From Product(1+q^i,i=1..infinity) we can change this to the equivalent form
Product((1-q^(2m))/(1-q^m))
which is equivalent to Product(1/(1-q^(2m-1))
which is equivalent to Product (1/(1-q^(2*i+1)),i=1..infinity)