Found this in my brother's stack of old trial papers. I found this test a higher standard than anything else I've ever done (consistent high standard throughout)
Just a note, the examiners are Graham Arnold and Denise Arnold. Heh.
Q8
n letters L1, L2, L3, ..., Ln are to be placed at random into n addressed envelopes E1, E2, E3,...,En, each bearing a different address, where Ei bears the correct address for letter Li, i= 1,2,3,...n
Let Un be the number of arrangements where no letter is placed in the correct envelope, for n a positive integer, n>= 2
i) Show U2 = 1 and U3= 2
ii) Deduce that U_k+1 = k(U_k + U_(k-1)), k=4,5,6...
iii) Use results from i) and ii) to calculate U_4 and U_5
iv) Show by mathematical induction that
U_n = n![ 1/2! - 1/3! + 1/4! - ...+(-1)^n * 1/n! ], n=2,3,4...
v) If there are 5 letters and envelopes:
a) Explain why probability no letter is placed in the correct envelope is U_5/120 and calculate this probability as a fraction
b) Show probability that exactly one letter is placed in the correct envelope is 5U_4 / 120 and calculate this probaiblity as a fraction
c) Find the probability exactly 2 letters are placed in the correct envelopes
vi) Deduce that summation k = 2 to n of [N choose K] * U_k = n!-1