#OK to post homework
#Michael Yen, 9/27/20, Assignment 5

#1. The lecture gave a full proof of the fact that if P(n) denotes the set of permutation of 
#{1,...n} and 
#p(n):=|P(n)|,
#then p(n)=n*p(n-1)
#(and hence p(n)=n!)

#It used the decompostion of P(n) into subsets according to the LOCATION of n.
#Find a new proof, explaining everything, of the same fact but breaking-up P(n) into the sets
#P_j(n)={All permutations pi in P(n) such that pi[1]=j, j=1..n

#Let: 
#P_j(n)={All the permutations in P(n) beginning with j} ex.
#P_1(n)={All the permutations in P(n) beginning with 1}
#P_2(n)={All the permutations in P(n) beginning with 2}
#etc.
#Since j ranges from 1 to n there are n of these subsets. Each of them contains p(n-1)=|P(n-1)|
#elements.
#How do we know this? Each number in P_j(n) has a fixed first digit j. Thus the number of
#permutations in this set solely depends on the number of ways you can rearrange the following
#n-1 digits, aka the permutations of those n-1 digits. 
#Thus there are n sets, each with p(n-1) elements. Hence p(n), which is |P_j(n)| for j=1..n, 
#is equal to n*p(n-1).

#2. [Corrected Sept. 21, 2020, thanks to Tifany Tong, who won a dollar]
#Let a1,a2,a3, be distinct positive integers, and let P(n;a1,a2,a3) be the set of words in the 
#alphabet 
#{a1,a2,a3}, of ANY length that add-up to n.
#For example P(3; 1,2,3)={111,12,21,3}
#Decompose P(n;a1,a2,a3) into smaller sets, and deduce a recurrence relation for

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

#We first look at an example to deduce a pattern
#Let a1,a2,a3 = 1,2,3
#P(0)={[]} 1 element
#P(1)={1} 1 element
#P(2)={11,2} 2 elements
#P(3)={111,12,21,3} 4 elements
#P(4)={1111,22,112,121,211,13,31} 7 elements
#P(5)={11111,122,212,221,1112,1121,1211,2111,113,131,311,23,32} 13 elements
#We can break these up by the first number, for example for P(4)
#P_1(4)={1111,112,121,13} P_2(4)={22,211} P_3(4)={31}
#As we can see |P_1(4)| is equivalent to |P(3)|, |P_2(4)| is equivalent to |P(2)|, and |P_3(4)| 
#is equivalent to |P(1)|. This makes sense because once you decide the first number, say a, the 
#number of elements in this subset should be the same as the number of words adding up to 
#n-a using the same alphabet.
#We can also see this happens for |P(5)|, which is |P(5-1)|+|P(5-2)|+|P(5-3)|=7+4+2=13
#So, we can deduce that p(n)=summation p(n-a), a=a1,a2,a3. This can also written as:
#p(n)=p(n-a1)+p(n-a2)+p(n-a3) with p(0)=1 and p(something negative)=0.

#3.[Challege, beginners to Maple can skip it, if they wish] Write a Maple procedure (don't forget 
#to use #option remember
#SEQP(a1,a2,a3,N)

#That inputs a1,a2,a3, as above, 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

addp:=proc(n,a1,a2,a3) local na1,na2,na3:
option remember:
if n=0 then
RETURN(1):
fi:
if n<0 then
RETURN(0):
fi:
na1:=n-a1:
na2:=n-a2:
na3:=n-a3:
addp(na1,a1,a2,a3)+addp(na2,a1,a2,a3)+addp(na3,a1,a2,a3):
end:

SEQP:=proc(a1,a2,a3,N) local n:
option remember:
[seq(addp(n,a1,a2,a3),n=0..N)]:
end:

#What are
#SEQP(1,2,3,40)? 1,1,2,4,7,13,24,44,81,149,274,504,927,1705... aka A000073 (Tribonacci numbers) in OEIS
#SEQP(1,2,4,40)? 1,1,2,3,6,10,18,31,55,96,169,296,520,912,1601,2809,4930... aka A060945 in OEIS
#are they in the OEIS? Yes they both are

#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|

#If some one is clever and good-lookingbit neither strong nor kind aka (C, L, not S, not K), 
#make sure that he or she are counted exactly once, by finding out
#How many time he is INCLUDED in line 1: 2
#How many time he is EXCLUDED in line 2: 1
#How many time he is INCLUDED (again) in line 3 (possibly none): 0
#How many time he is EXCLUDED (again) in line 4 (possibly none): 0
#Do the analogous thing for a lucky person who is lucky to be clever AND strong AND good-looking 
#AND kind-hearted. (C,S,L,K)
#How many time he is INCLUDED in line 1: 4
#How many time he is EXCLUDED in line 2: 6
#How many time he is INCLUDED (again) in line 3 (possibly none): 4
#How many time he is EXCLUDED (again) in line 4 (possibly none): 1