#OK to post
#Sam Minkin, 12/13, Assignment 24

QUESTION #1:

(i) This can be found by running pnC(97,{1,4,5},7); which gives:
108236 partitions

(ii) This can be found by running pnD(97,3); which gives:
19990 partitions

QUESTION #2:

pnkDC:=proc(n,k,d,C,m) local k1,S:
option remember:
if k>n 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 from 1 to k-d do

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

od:
S:
end:

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

(i) Let n=97,d=3,C={1,4,5},m=7.
Then, running pnDC(97, 0, {1,4,5}, 7); gives:
108236 partitions - the same as pnC(97, {1,4,5}, 7)

Running, pnDC(97, 3, {0}, 1); gives:
19990 partitions - the same as pnD(97, 3);

(ii) Running seq(pnDC(n, 1, {1}, 2), n=1..40) gives us:
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

It is in the OEIS. Its A-number is A000700.

(iii) Running seq(pnDC(n, 2, {1,4}, 5), n=1..40) gives us:
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

It is in the OEIS. Its A-number is A203776.

QUESTION #3:

Let's look at the infinite set of all integer partitions with distinct parts.

When we pick a random integer partition we make decisions:
- Do we include 1: No 1, One 1
- Do we include 2: No 2, One 2
and so on...

An integer partition, L, is an element in {[], [1]} x {[], [2]} x {[], [3]} x ....
By the weight enumerator properties we know that |A x B x C x ...| = |A|_q * |B|_q * ....
So, by this proprty we have the function (1+q)(1+q^2)(1+q^3)*... = Product(1+q^i,i=1..infinity).
This proves our claim.

QUESTION #4:

Let's look at the infinite set of all integer partitions whose parts are odd.

When we pick a random integer we make decisions:
- How many 1's to include: No 1s, One 1s, Two 1s, Three 1s, ... 
- How many 3's to include: No 3s, One 3s, Two 3s, Three 3s, ...
- How many 5's to include: No 5s, One 5s, Two 5s, Three 5s, ...
and so on...

Therefore an integer partition, L, whose partition has all odd parts, is contained in the set:
{[], [1], [1,1], [1,1,1], ...} x {[], [3], [3,3], [3,3,3], ...} x {[], [5], [5,5], [5,5,5], ...} x ...
If we take the weight enumerator of the above set, we get:
(1+q+q^2+q^3+...)*(1+q^3+q^6+q^9+...)*(1+q^5+q^10+q^15+...)*...
Since these are geometric series, the above reduces to:

(1/1-q)(1/1-q^3)(1/1-q^5)*...=Product(1/(1-q^{2*i+1}),i=0..infinity).
Thus, we've proven the claim.

QUESTION #5:

Based off Euler's proof, we have:

First, we have that the generating function for distinct parts is given by:
(1+q)*(1+q^2)*(1+q^3)*...

We can write this equivalently as:
(1-q^2/1-q)*(1-q^4/1-q^2)*(1-q^6/1-q^3)*(1-q^8/1-q^4)*...

Notice that the terms in the numerator cancel out with terms in the denominator which have an even power. This leaves us with:
(1/1-q)*(1/1-q^3)*(1/1-q^5)*...

This is the same as the generating function for odd parts. Hence, the number of partitions of n into odd parts is equal to the number of partitions of n into distinct parts for all n.