Reference no: EM131572390

Question: The following method can be used to generate a random permutation of a sequence of n terms. First, interchange the nth term and the r(n)th term where r(n) is a randomly selected integer with 1 ≤ r(n) ≤ n. Next, interchange the (n - 1)st term of the resulting sequence with its r(n - 1)st term where r(n - 1) is a randomly selected integer with 1 ≤ r(n - 1) ≤ n - 1. Continue this process until j = n, where at the j th step you interchange the (n - j + 1)st term of the resulting sequence with its r(n - j + 1)st term, where r(n - j + 1) is a randomly selected integer with 1 ≤ r(n - j + 1) ≤ n - j + 1. Show that when this method is followed, each of the n! different permutations of the terms of the sequence is equally likely to be generated.