#OK to post homework
#TaerimKim,9/26/2020,Assignment 5

#1.
#given that P_j(n)={All permutations pi in P(n) such that pi[1]=j, j=1..n
#meaning that 1 is going to change its position depending on the j.
#intuitively, it is similar fashion as the lecture example.
#Let P(3) = {123,132,213,231,312,321}:
#P_1(3) = {123,132} in bijection with {23,32}
#P_2(3) = {213,312} in bijection with {23,32}
#P_3(3) = {321,231} in bijection with {23,32}
#Thus, P-j(n) IS IN BIJECTION WITH P(n-1)
#Using the principle of addition,
#|P(n)|=(|P_1(n)| + |P_2(n)| + ... + |P_n(n)|
#=n*|P_1(n)| = n*|P(n-1)| = p(n)  QED.    

#2.
#By dividing the set with P_k(n) = { All permutations pi in P(n) such that # of alphabet in the 
#set is k}. Basically, we are using length as a factor in divding the set. 
#Let a1,a2,a3 be 1,2,3 for the P.
#P(n;1,2,3) for n=1,2,3,4,
#P_1(1)={1} ;
#P_1(2)={2}; P_2(2)={11}
#P_1(3)={3}; P_2(3)={21,21}; P_3(3)={111};
#P_1(4)={4}; P_2(4)={13,31,22}; P_3(4)={112,121,211}; P_4(4)={ };

#3.

#4. 
#The given person, denoting as k, can be rewrote as
#k = (C intersect L) - (S union K)
#meaning k is not a subset of S and K
#1st line : 2 appearance on |C| and |L|
#2nd line: 1 appearance on |C intersect L|
#3rd line: no appearance as k is not associated in 3 or more groups
#4th line: no appearance due to same reason
#As a result: 2-1 = 1 which is correct.

#Another person, denoting as j, can be reworte as 
#j = (C intersect S intersect L intersect K) meaning in every set it is included
#So in every subset in every line it will appear
#1st line : 4 appearance in all subsets
#2nd line: 6 appearance in all subsets
#3rd line: 4 appearance in all subsets
#4th line: 1 appearance in all subsets
#As a result: 4-6+4-1 = 1 which is also correct.