Ok to post

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

Answer 1. 

Proof of |permute(n)| = n!
Redefining the the permute(n) function as permute(n; 1..n) where the numbers to be permuted are mentioned. This hopefully does not chanage the problem
but makes it easy
Let P(n; 1..n) = set of permutations
Let P_i(n; 1..n) = set of permutations where pi[1] happens to be i

P(3; 1, 2, 3) = {123, 312, 213, 132, 231, 321}
P_1(3; 1, 2, 3) = {123, 132} IN Bijection with {23, 32} P(2; 2, 3)
P_2(3; 1, 2, 3) = {231, 213} IN Bijection with {31, 13} P(2; 1, 3)
P_3(3; 1, 2, 3) = {312, 321} IN Bijection with {12, 21} P(2; 1, 2)

Bijection defined as
Remove i from position 1
Add i to poition 1

|P_i(n; 1 .. n)| = |P(n-1; 1..i-1 i+1..n)| for i = 1, 2.. n
|P(n)| = |P_1(n) union P_2(n)union...P_n(n)|
All of the sets are mutually exclusive

|P(n)| = |P_1(n)|+|P_2(n)| ... |P_n(n)|
= |P(n-1)+P(n-1)+...+P(n-1)| = n*|P(n-1)|

P(n) = n* (n-1)* (n-2)*...*1

QED

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

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

P(3; 1, 2, 3) = {111, 12, 21, 3}
P(2; 1, 2, 3) = {11, 2}
P(1; 1, 2, 3) = {1}
P(0; 1, 2, 3) = { null }

|P(3; 1, 2, 3)| = |P(2; 1, 2, 3)| +|P(1; 1, 2, 3)| + |P(0; 1, 2, 3)|
|P(n; a1, a2, a3)| = |P(n-a1; a1, a2, a3)| +|P(n-a2; a1, a2, a3)| + |P(n-a3; a1, a2, a3)|
P(0) = {null}
P(n<0) = {}
#---------------------------

#------------------------------------
Question 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-looking but neither strong nor kind, make sure that he or she are counted exactly once, by finding out
How many time he is INCLUDED in line 1
How many time he is EXCLUDED in line 2
How many time he is INCLUDED (again) in line 3 (possibly none)
How many time he is EXCLUDED (again) in line 4 (possibly none)


Answer 4

2 times in line 1
1 time in line 2
0 times in line 3
0 times in line 4

So he is indeed counted only 1 as 2-1 = 1

Analogous way 

4 times in line 1
EXCLUDED 6 times in line 2
Inclusion 4 times in line 3
EXCLUDED 1 time in line 4

So he is indeed counted only 1 as 4-6+4-1 = 1