#OK to post homework
#Sam Minkin, 9/27, Assignment 5

Problem 1:

Define P_j(n) = {All permutations pi in P(n) such that pi[1]=j, j=1..n}. 
For n = 3, we have P(3) = {123, 132, 213, 231, 312, 321}.
Then, P_1(3) = {123, 132},
P_2(3) = {213, 231},
P_3(3) = {312, 321}.
We claim that P_j(n) is in bijection with P(n-1). 

Assume for some n > 3, that P_j(n) is in bijection with P(n-1) for all j = 1..n. We want to show that this implies that P_j(n+1) is in bijection with P(n) for all j = 1..n+1. Suppose we have some integer j in between 1 and n+1 inclusive. Then we can construct P_j(n+1) in the following way: for each element in P_j(n), place the number (n+1) in any location except for 1. There are n such locations for each element so that implies that |P_j(n+1)| = n*|P_j(n)|. Additionally, we can construct P(n) in the following way: for each element of P(n-1) place n in any location. There are n such locations so |P(n)| = n*|P(n-1)|. By our inductive hypothesis, |P(n-1)| = |P_j(n)| since they are in bijection. Hence, |P_j(n+1)| = |P(n)| implying that they are in bijection. By induction, the claim is proved.

Because of our claim, we know that |P_j(n)| = |P(n-1)| for some n > 2, j = 1..n.
So, |P(n)| = |P_1(n) U ... U P_n(n)| = |P_1(n) + ... + P_n(n)| = |P_1(n)| + ... + |P_n(n)| since all sets are disjoint.
Furthermore, by our claim we have |P(n)| = |P(n-1)| + ... + |P(n-1)| = n*|P(n-1)|.
By the recurrence, we have that |P(n)| = n! as we desired to show.

Problem 2:

In each recurrence level, we have three choices: include a1, a2, or a3. If we include one of these then we have to subtract it from the total set. Hence, for any integers, a1, a2, a3, and n, consider the following recurrence: P(n; a1, a2, a3) = P(n-a1; a1, a2, a3) + P(n-a2; a1, a2, a3) + P(n-a3; a1, a2, a3). This says that for all sets of words in the alphabet {a1, a2, a3}, that add up to n-a1, n-a2, or n-a3, we can add a1, a2, or a3 respectively to each element in the set. Our final answer is the union of elements in all these sets.

Problem 3:

I wrote a helper function which calculates p(a1,a2,a3,n). I then wrote SEQP which calls the helper function for n=0..N and takes the first element in each set. I then outputted the first element of p(a1,a2,a3,n) for n=0..N.

helper:=proc(a1,a2,a3,N) local S1,S2,S3,R1,R2,R3,s1,s2,s3:
option remember:

if N < 0 then
	RETURN({}):
fi: 

if N = 0 then
	RETURN({[]}):
fi:

S1:=helper(a1,a2,a3,N-a1):
S2:=helper(a1,a2,a3,N-a2):
S3:=helper(a1,a2,a3,N-a3):

R1:={seq([op(s1),a1], s1 in S1)}:
R2:={seq([op(s2),a2], s2 in S2)}:
R3:={seq([op(s3),a3], s3 in S3)}:

R1 union R2 union R3:

end: 

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

S:={}:

for i from 0 to N do
	S1:=helper(a1,a2,a3,i):
	if nops(S1) > 0 then
		S:=S union {S1[1]}:
	fi:
od:

S:

end:


Problem 4:

Properties: Clever, strong, good-looking, kind-hearted.

If someone is clever and good looking but not strong and not kind, then...

He is included twice in line 1.
He is excluded once in line 2.
He is included 0 times in line 3.
He is excluded 0 times in line 3.

So, we have that 2 - 1 = 1, as we wanted.

Now, if someone is clever, strong, good-looking, and kind, then...

He is included four times in line 1.
He is excluded six times in line 2.
He is included four times in line 3.
He is excluded one time in line 4.

So, we have 4 - 6 + 4 - 1 = 1, as we wanted.