#OK to post homework
#William Wang, 9/20/2020, Assignment 5

#1.
#If we let P_j(n) denote all the permutations pi in P(n) such that pi[1] = j, j=1..n,
#We see that there is one value to set p[1] as, namely p[1]=1, and for indeces 2..n, there are (n-1)! ways of setting p[2]...p[n]
#After setting p[1]=1, we do the same thing recursively, except this time we have one value we want to set p[2] as, namely p[2] = 2, and there are (n-2)! ways of setting p[3]...p[n]
#Total ways of permuting = n(n-1)(n-2)...(n-n) = n!





#2.
#P(n,a1,a2,a3) is the set of words in the alphabet {a1,a2,a3} of any length that add up to n
#ex. P(3,1,2,3) = {111,12,21,3}

#We know that each word is another word plus one of the letters a1,a2,or a3
#Thus, P(n,a1,a2,a3) = P(n-a1,a1,a2,a3) + P(n-a2,a1,a2,a3) + P(n-a3,a1,a2,a3)

#p(n,a1,a2,a3) = |P(n,a1,a2,a3)|
#Lemma: any member w, of P(n)
#Case 1: u a1 (u is a member of P(n-a1))
#Case 2: u a2 (u is a member of P(n-a2))
#Case 3: u a3 (u is a member of P(n-a3))

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





#3.
p := proc(n, a1, a2, a3) local W1, W2, W3, w1, w2, w3:
option remember:
if n < 0 then
 RETURN(0):
fi:
if n = 0 then
 RETURN(1):
fi:
W1 := p(n - a1, a1, a2, a3):
W2 := p(n - a2, a1, a2, a3):
W3 := p(n - a3, a1, a2, a3):
W1 + W2 + W3:
end:

SEQP := proc(a1, a2, a3, n) local i:
seq(p(i, a1, a2, a3), i = 0 .. n):
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 A000073 in the OEIS, or known as the 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 A060945 in the OEIS, which is the sequence which describes the number of compositions of n into 1's, 2's, and 4's





#4.
#Someone is clever(C) and good looking(L)
#Included twice in line 1
#Excluded once in line 2
#Included no times in line 3
#Excluded no times in line 4
#2-1+0-0=1

#Some is clever(C), good looking(L), strong(S), and kind-hearted(K)
#Included four times in line 1
#Excluded six times in line 2
#Included four times in line 3
#Excluded once in line 4
#4-6+4-1=1