#OK to post homework
#Kent Mei, 9/27/20, Assignment 5

#---------------------------------
#Part 1
#Let P(n) denote the set of permutations of {1,...,n} and p(n):=|P(n)|
#Define P_j(n) = {All permutations pi P(n) such that pi[1]=j, j=1..n}
#Note that since we have pi[1] = j for all pi in P_j(n), if we delete the first element of each pi in P_j(n), we're left with the set of permutations of {i, i = 1..n and i != j}. So, |P_j(n)| = |Perm({i, i = 1..n and i != j})|.
#A lemma we know is that if S and T contain the same number of elements, then |Perm(S)| = |Perm(T)|. Note that {i, i = 1..n and i != j} contains n - 1 elements by construction and the set {1,...,n-1} also contains n - 1 elements. Therefore, |Perm({i, i = 1..n and i != j})| = |Perm({1,...,n-1})| = |P(n-1)|.
#By transitivity, we have |P_j(n)| = |P(n-1)| = p(n-1).
#Note that all P_j(n) are pairwise disjoint because each set specifies that pi[1] = j meaning that a separate permutation in P_k(n) can't have pi[1] = j as well because it belongs in P_k(n).
#We know the union for j = 1..n P_j(n) = P(n) so 
#p(n) = |P_1(n)| + ... + |P_j(n)|
#p(n) = p(n-1) + ... + p(n-1) (there are n terms).
#p(n) = n * p(n-1) as desired.

#---------------------------------
#Part 2
#Let a1,a2,a3 be distinct positve integers, and let P(n;a1,a2,a3) be the set of words in the alphabet {a1,a2,a3}, of ANY length.
#P(n; a1,a2,a3) = P(n-a1; a1,a2,a3) union P(n-a2; a1,a2,a3) union P(n-a3; a1, a2, a3)
#To see this, the set of words that add up to n can be found by taking the union of the sets of words that add up to n-ak for k = 1..3 and appending ak to each word.
#p(n;a1,a2,a3) = p(n-a1;a1,a2,a3) + p(n-a2;a1,a2,a3) + p(n-a3;a1,a2,a3)
#Equivalently, p(n) = p(n-a1) + p(n-a2) + p(n-a3).


#---------------------------------
#Part 3

#p is a helper function that will be used in SEQP.

p:=proc(a1,a2,a3,n) option remember:

if n < 0 then
 return 0:
fi:

if n = 0 then
 return 1:
fi:

p(a1,a2,a3,n-a1) + p(a1,a2,a3,n-a2) + p(a1,a2,a3,n-a3):

end:


SEQP:=proc(a1,a2,a3,N) local i, Ans:
option remember:


Ans := []:

for i from 0 to N do
 Ans := [op(Ans), p(a1,a2,a3,i)]:
od:

Ans:

end:

#SEQP(1,2,3,40) = [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]
#This sequence is in the OEIS as A73, the sequence of tribonacci numbers.

#SEQP(1,2,4,40) = [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]
#This sequence is in the OEIS as A60945 and A181532.

#---------------------------------
#Part 4

#Suppose someone is clever and good-looking, but not strong nor kind.
#In line 1, the person is included 2 times (Clever, and good-looking)
#In line 2, the person is excluded 1 time  (Clever and good-looking)
#In line 3, the person is included 0 times
#In line 4, the person is excluded 0 times
#2 - 1 = 1 so the person is included exactly once.

#Now suppose someone is clever, strong, good-looking, and kind.
#In line 1, the person is included 4 times (Part of all 4 sets).
#In line 2, the person is excluded 6 times (Part of each pairwise intersection)
#In line 3, the person is included 4 times (Part of each intersection of 3 sets)
#In line 4, the person is excluded 1 time  (Part of all 4 sets).
#4 - 6 + 4 - 1 = 1 so the person is included exactly once.