# OK to post

# Soham Palande, Assignment 5, 09/27/2020


# PART 1

# Proof of |permute(n)| = n! Where permute(n) is the set of permutations of {1,2,...n}.
# Let P(n) denote the set of permutation of {1,...n}
# Let P_j(n) denote the set of permutations where the first element of the permutation pi[1] = j where 1<=j<=n

# Example:
# P(3) ={123, 132, 213, 231, 312, 321}
# Then, 
# P_1(3) = {123, 132} 
# P_2(3) = (213, 231)
# P_3(3) = {312, 321} 
# For the sets above, if we delete 3, we get {12, 21}. Thus the sets are in bijection with P(2)

# P_1, P_2, P_3 are mutually disjoint. 
# Generalizing the observation, we get
# P_j(n) is in bijection with P(n-1) if we remove n from locations 2..n for P_j(n) when j<>n and from locations 1 for P_j(n) when j=n. 
# Similarly, if we insert n at locations 2...n in the elements of P_j(n) when j<>n and insert n at location 1 of all elements of P_j(n) when j=n, we get a bijection from P_j(n) to P(n-1). 

# Then using the principle that if two sets A and B are in bijection, then |A|=|B|. 
# Then |P_j(n)|=|P(n-1)| 
# Using the principle of addition, 
# |P(n)| = |P_1(n) union P_2(n) union ... union P_n(n)| since P_j(n) is mutually disjoint for all j=1..n
#	 =  |P_1(n)| + .... +|P_n(n)|
#	 = |P(n-1)| + .... + |P(n-1)| (n times since we have n subsets)
# |P(n)| = n*P(n-1)
# p(n)=|P(n-1)|
# Thus, p(n)= n*p(n-1) and p(0)=1 and p(n)=n!


# Hence proven. 


# PART 2
# 





# PART 3

# I have used the Comps(n) function as a helper function from the maple code for lecture 4  
# which returns the set of all positive integers that add up to n


SEQP:=proc(n,a1,a2,a3) local NUM,e,SE,i   :
for i from 1 to n do
 NUM:=Comps(i):
 SE:=NUM:
 for e in SE do
     if not member(a1,e) and not member(a2,e) and not member(a3,e) then
         NUM:=NUM minus {e}:
     fi:
    
 od:
 print(nops(NUM))
 od:
 end: 

#Takes very long for large numbers



# PART 4
# In a given class, let
# C be the set of clever students,
# S be the set of strong students,
# L be the set of good-looking students,
# K be the set of kind-hearted students,
# The Principle of Inclusion-Exclusion for four sets says
# |C union S union L union K|=

# |C| + |S|+ |L| + |K|

# -( |C interset S| + |C interset L| + |C interset K| + |S interset L| + |S interset K| + +|L interset K| )

# +( |C interset S intersect L| +|C interset S intersect K| +|C interset K intersect L| +|S interset K intersect L| )

# -|C intersect S intersect L intersect K|

# Suppose a person P is clever and good looking but neither strong not kind. Then P is in C and P is in L and P is not in $ S or K
# Then, 
# in line one of the equation: P is counted 2 times
# in line two of the equation: P is counted 1 times
# in line three of the equation: P is counted 0 times
# in line four of the equation: P is counted 0 times
Thus P is counted (2-1)= 1 times in total. 


Suppose a person P is clever AND strong AND good-looking AND kind-hearted. Then P is a element of C, S, L and K. 
# Then, 
# in line one of the equation: P is counted 4 times
# in line two of the equation: P is counted 6 times
# in line three of the equation: P is counted 4 times
# in line four of the equation: P is counted 1 times
Thus P is counted (4-6+4-1)= 1 times in total.