#OK to post
#Soham Palande, Assignment 24, 12/13/2020



#PART 1

#(i) How many (integer) partitions are there of 97 where the each part, upon division by 7, gives 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 the difference between consecutive parts is at least 3?

pnD(97,3)
19990



#PART 2

pnDC:=proc(n,d,C,m) local S1,S2,S3:
S1:=PnD(n,d):
S2:=PnC(n,C,m):
S3:=S1 intersect S2:

nops(S3)
end proc:

#Checking for correctness

(i)
evalb(pnDC(20,0,{1,4},5)=pnC(20,{1,4},5))
true


evalb(pnDC(20,1,{0},1)=pnD(20,1))
true


(ii)

#Enumerating partitions that are both odd and distinct

seq(pnDC(n,1,{1},2),n=0..40)

0, 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


#The exact sequence is not in the OEIS- however there are very similar ones which differ at n=0 and with alternating signs in the terms. 


(iii)

#Enumerating partitions in which consecutive entries differ by at least 2 and each entry mod 5 give 1 or 4


seq(pnDC(n,2,{1,4},5),n=0..40)

0, 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 sequence is in the OEIS. The A- number is A203776
#Number of partitions of n into distinct parts 5k+1 or 5k+4.




#PART 3

Use the argument in the lecture that proved that the generating function of p(n) is
1/((1-q)*(1-q^2)*(1-q^3)*....)

To prove that the generating function of the sequence enumerating distinct partitions is

(1+q)*(1+q^2)*(1+q^3)*... =Product(1+q^i,i=1..infinity)


#PROOF


Using the frequency notation that we discussed in class, we have 1^(a1), 2^(a2),...n^(an)
Where the corresponding partition can be written as a1 1's, a2 2's, an n's. 

Ex: 1 1 1 2 5 5 5 -> 1^(3) 2^(1) 5^(3)


Now, consider the infinite set of all integer partitions regardless of n. 

Weight([a1,a2,...ak])= q^(a1+a2+...ak)

Lets the infinite set of all integer partitions of all n be denoted as 

PAR = PAR(only using 1's) x PAR(only using 2's) x PAR(only using 3's) x ...
    = { ([],[1]) x ([],[2]) x ([],[3]) x ... }

      Since we only want partitions with distinct elements we can have at most one of each n
    
The weighted enumerator of the cross product is equal to the weighted enumerator of the individual sets. 

|A x B x C x D|_q= |A|_q * |B|_q * |C|_q * |D|_q

So, we get (1+q) * (1+q^2) * (1+q^3) * (1+q^4) * ...

Hence, the generating function of the sequence enumerating distinct partitions is (1+q)*(1+q^2)*(1+q^3)*... =Product(1+q^i,i=1..infinity). 



#PART 4

Using the frequency notation that we discussed in class, we have 1^(a1), 2^(a2),...n^(an)
Where the corresponding partition can be written as a1 1's, a2 2's, an n's. 

Ex: 1 1 1 2 5 5 5 -> 1^(3) 2^(1) 5^(3)


Now, consider the infinite set of all integer partitions regardless of n. 

Weight([a1,a2,...ak])= q^(a1+a2+...ak)

Lets the infinite set of all integer partitions of all n be denoted as 

PAR = PAR(only using 1's) x PAR(only using 2's) x PAR(only using 3's) x ...
    = { ([],[1],[11],[111]...) x ([],[3],[33],[333]...) x ([],[5],[55],[555]...) x ... }

Since we only want partitions with odd elements we only include odd numbers. 
    
The weighted enumerator of the cross product is equal to the weighted enumerator of the individual sets. 

|A x B x C x D|_q= |A|_q * |B|_q * |C|_q * |D|_q

So, we get (1+q+q^2+q^3...) * (1+q^3+q^6+q^9+...) * (1+q^5+q^10+q^15+...) * ...
          =(1/(1-q)) * (1/(1-q^3)) * (1/(1-q^5)) * ...

Hence, the generating function of the sequence enumerating odd partitions (i.e. partitions whose components are all odd) is

1/((1-q)*(1-q^3)*(1-q^5)*....)=Product(1/(1-q^(2*i+1),i=0..infinity) 



#PART 5


#We will proceed using the two generating functions we found in Part 3 and Part 4.

#(There is an alternative bijective proof as well)


Let F(n) denote the number of partitions of n into distinct parts. Let G(n) denote the number of partitions of n into odd parts. 

i.e. Sum(F(n)*q^(n),n=0..infinity) = (1+q)(1+q^2)(1+q^3)(1+q^4)...

Rewriting the terms, we get 

				  = (1-q^2)/(1-q) * (1-q^4)/(1-q^2) * (1-q^6)/(1-q^3) * ...
Simplifying, 

				  = 1/[(1-q)(1-q^3)(1-q^5)...]

This is equivalent to Sum(G(n)*q^n,n=0..infinity)!

Hence, this proves Euler's theorem that that for every n, the number of partitions of n into odd parts, equals the number of partitions of n into distinct parts.