#OK to post homework
#Karnaa Mistry, 09/27/20, Assignment HW #5

with(combinat):


# 1. 

# Let P(n) = Set of permutations.
# Let P_j(n) = Set of permutations pi in P(n) such that pi[1]=j,j=1..n
# P(3) = {123,132,213,231,312,321} = P_1(3) U P_2(3) U P_3(3)
# P_1(3) = {123,132} => {23,32} = Perm({2,3}); (DELETED THE FIRST ELEMENT pi[1]) 
# P_2(3) = {213,231} => {13,31} = Perm({1,3}); (DELETED THE FIRST ELEMENT pi[1]) 
# P_3(3) = {312,321} => {12,21} = Perm({1,2}); (DELETED THE FIRST ELEMENT pi[1]) 

# Use Lemma: if S and T have the SAME number of elements, then |Perm(S)| = |Perm(T)|
# Since we are 'deleting' 1 element from P_j(n) for each particular j, we have |P_j(n)| = |P(n-1)| for j=1,2..n-1
# |P(n)| = |P_1(n) union ... P_n(n)| = |P_1(n)|+...+|P_n(n)| = |P(n-1)|+...+|P(n-1)| = n*|P(n-1)|

# p(n) := |P(n)|

# p(n) = n*p(n-1), p(0) = 1 => n!
# n! = 1*2*...*n

# The number of permutations p(n) in P(n) (set of permutations of {1,...,n}) is equal to n!




# 2.

# p(n) = p(n;a1,a2,a3) = |P(n;a1,a2,a3)|

# p(n) = p(n-a1) + p(n-a2) + p(n-a3)

# note: P(0) = {[]} => p(0) = 1

# Use Lemma: let w be any member of P(n), and let notation u a0 mean appending a single a0 for word u
# Case 1: w = u a1 (u is a member of P(n-a1))
# Case 2: w = u a2 (u is a member of P(n-a2))
# Case 3: w = u a3 (u is a member of P(n-a3))

# P(n) = P(n-a1) a1  union  P(n-a2) a2  union  P(n-a3) a3

# These three sets are disjoint union because if a word ends in a1, it cannot end in a2, etc.

# |P(n)| = |P(n-a1) a1| + |P(n-a2) a2| + |P(n-a3) a3|
# |P(n)| = |P(n-a1)| + |P(n-a2)| + |P(n-a3)|

# We have a recurrence relation: p(n) = p(n-a1) + p(n-a2) + p(n-a3)




# 3.

#SEQP(a1,a2,a3,N): inputs a1,a2,a3, and a positive integer N, and outputs the first N+1 terms, starting at n=0 of
#p(n,a1,a2,a3), n=1..N
SEQP:=proc(a1,a2,a3,N) local i,L,p:
option remember:
L:=[]:

for i from 0 to N do:

p:=SEQP2(a1,a2,a3,i):

L:=[op(L),p]:
od:

end:

#SEQP2(a1,a2,a3,N): helper procedure for SEQP, obtains p(n,a1,a2,a3)
SEQP2:=proc(a1,a2,a3,N) local F1,F2,F3,f1,f2,f3,i,L,p:
option remember:

if N<0 or a1<1 or a2<1 or a3<1 then
 RETURN(0):
fi:

if N=0 then
 RETURN(1):
fi:

F1:=SEQP2(a1,a2,a3,N-a1):
F2:=SEQP2(a1,a2,a3,N-a2):
F3:=SEQP2(a1,a2,a3,N-a3):

F1+F2+F3:
end:

# SEQP(1,2,3,40) gives 1, 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
# On OEIS, doing the first ~14 elements gives us A000073: 
# "Tribonacci numbers: a(n) = a(n-1) + a(n-2) + a(n-3) for n >= 3 with a(0) = a(1) = 0 and a(2) = 1"

# SEQP(1,2,4,40) gives 1, 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
# On OEIS, doing the first ~14 elements gives us A060945:
# "Number of compositions (ordered partitions) of n into 1's, 2's and 4's"




# 4. 

# Someone who is C and L but neither S nor K is in sets C, L, C U anything, L U anything, and C intersect L

# Line 1: INCLUDED 2 times from |C| + |L|
# Line 2: EXCLUDED 1 time from |C intersect L|
# Line 3: INCLUDED 0 times
# Line 4: EXCLUDED 0 times
# 2 - 1 = 1 (good)

# Someone who is C and L and S and K is in all sets, all unions, and all intersections in this situation

# Line 1: INCLUDED 4 times from |C| + |S| + |L| + |K|
# Line 2: EXCLUDED 6 times from all intersections
# Line 3: INCLUDED 4 times from all intersections
# Line 4: EXCLUDED 1 time from the intersection of all four sets
# 4 - 6 + 4 - 1 = 1 (good)