#OK to post homework
#Tianyi Liu,Sept 27, Assignment 5

1.
#We break up P(n) into n subsets. The first subset has all permutations with the first element being 1. Similarly up to n, the nth subset has all permutations with the first element being n.
#If we take the first element out of the first subset, then it has permutations of length n-1 from 2 to n. Similarly up to n, nth subset has permutations of length n-1 from 1 to n-1. 
#Let p(n):=|P(n)|, then we can see that all the subsets without the first element are essentially p(n-1). Adding them up we get n*p(n-1)=p(n). Hence, p(n)=n!.

2.
#p(n,a1,a2,a3)=p(n-a1,a1,a2,a3)+p(n-a2,a1,a2,a3)+p(n-a3,a1,a2,a3)

4.
#Clever & good looking
#included in line1:2
#excluded in line2:5
#included in line3:0
#excluded in line4:1
#2-1=1

#clever AND strong AND good-looking AND kind-hearted
#included in line1:4
#excluded in line2:0
#included in line3:4
#excluded in line4:0
#4-6+4-1=1