i. easy
ii.slightly sneaky argument. L_{k+1} has to go in one of the first k envelopes. suppose it goes into E_{n}. Then you are left with k letters and k envelopes..
Then you break it up into 2 cases..
a) L_{n} goes into E_{k+1}
b) L_{n} doesn't go into E_{k+1}
the first case (a) gives u_{k-1} since you are left with k-1 letters in k-1 envelopes. for the 2nd case (b) you can imagine E_{k+1} being 'relabeled' E_{n}, and you are essentially trying to place k letters into k envelopes, so that you don't get any correctly placed.
so you get U_{k+1} = k(U_{k} + U_{k-1})
iii. you can do this.
iv. shouldn't be too hard, alternatively you can use the inclusion exclusion principle
v. a) easy b) should be easy too c.) (5choose 3)u_3 / 120
vi. following the patter (n choose k) u_{k} would represent the number of permutations where there is something misplaced. out of the n! permutations only 1 is perfect.. so it follows that the sum is n!-1
Search up matching problem on google (the wiki article is a related problem in graph theory though)
