#Ok to post homework
#Tifany Tong, September 27th, 2020, HW #5

# Question 1

#Let P(n) = Set of permutations with values from 1 to n. 
#Let P_i(n) = Set of permutations in P(n) such that pi[1] = i
#P(n) = A set of cardinality n! with all the permutations 
#P_1(n) = The set of permutations starting with 1 and the rest being the permutation with values from 2 to n. 
#P_2(n) = The set of permutations starting with 2 and the rest being the permutation with values from 1 and 3 to n.
# ....
#P_n(n) = The set of permutations starting with n and the rest being the permutation with values 1 to n-1.  
#P_i(n) is in bijection with P(n-1)
# Going from P_i(n) to P(n-1):
#	If i is n, remove n from the front
# 	Otherwise: Remove n from P_i(n) and replace it with i.  
# Going from P(n-1) to P_i(n): 
#	If i is n, we put n to the front of each in P(n-1)
#	Otherwise: We keep i at the front and replace where i was in P(n-1) with n. 

#The two sets P_i(n) and P(n-1) are in bijection since |P_i(n) = P(n-1)|. 

#Since there are n sets of size P(n-1), which we know to be true since there is a bijection between
#P_i(n) and P(n-1), then we get |P(n)| = n * |P(n-1)|. This is what we sought to prove. 

# Question 2

#P(n;a1,a2,a3). For this, we know that if we use a1, then we need to find the number of ways to solve
# n-a1. If we use a2, then we need to find the number of ways to solve n-a2. Finally, if we use a3, 
# then we need to find the number of ways to solve n-a3. These 3 options will continue for n-a1, n-a2,
# and n-a3. Thus, the recurrence relation is P(n) = P(n-a1) + P(n-a2) + P(n-a3).

# Question 3

helper:=proc(a1,a2,a3,N) local S, val, val1, val2, val3, L:
option remember:
if (N = 0) then RETURN(1):fi:
L:=[a1,a2,a3]:
val:=min(L):
if(N<val) then RETURN(0):fi:
if(val=N) then RETURN(1):fi:
val1:= helper(a1,a2,a3,N-a1):
val2:= helper(a1,a2,a3,N-a2):
val3:= helper(a1,a2,a3,N-a3):
S:=val1+val2+val3:
S:
end:

SEQP:=proc(a1,a2,a3,N) local i,S:
option remember:
S:={}:
for i to N do
  S:=S union{helper(a1,a2,a3,i)}:
od:
S:
end: 

#SEQP(1, 2, 3, 40) =
#{1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, 1705, 3136, 
#  5768, 10609, 19513, 35890, 66012, 121415, 223317, 410744, 
#  755476, 1389537, 2555757, 4700770, 8646064, 15902591, 29249425, 
#  53798080, 98950096, 181997601, 334745777, 615693474, 
#  1132436852, 2082876103, 3831006429, 7046319384, 12960201916, 
#  23837527729}

#This corresponds to A73. 


#SEQP(1, 2, 4, 40) =
#{1, 2, 3, 6, 10, 18, 31, 55, 96, 169, 296, 520, 912, 1601, 2809, 
#  4930, 8651, 15182, 26642, 46754, 82047, 143983, 252672, 443409, 
#  778128, 1365520, 2396320, 4205249, 7379697, 12950466, 22726483, 
#  39882198, 69988378, 122821042, 215535903, 378239143, 663763424, 
#  1164823609, 2044122936, 3587185688}

#This corresponds to A60945.




# Question 4

# For someone clever and good looking, but neither strong nor kind:
# 	In line 1: They are included 2 times
#	In line 2: They are excluded 1 time
# 	In line 3: They are included 0 times
#	In line 4: They are excluded 0 times
# This shows that a person who is clever and good looking, but none of the other 
# qualities is 2-1+0-0 = 1 time. 

# For someone clever, strong, good-looking, and kind-hearted:
# 	In line 1: They are included 4 times
#	In line 2: They are excluded 6 time
# 	In line 3: They are included 4 times
#	In line 4: They are excluded 1 times
# This shows that a person who is clever, strong, good-looking, and kind-hearted 
# is counted 4-6+4-1 = 1 time.