(Solved): Consider an array A[1...n] containing the numbers from 1 to n where initially A[i] = i. We wish to r ...

Consider an array A[1...n] containing the numbers from 1 to n where initially A[i] = i. We wish to randomly permute the elements in A. Consider the following recursive algorithm to permute the elements in A.

Algorithm Permute[A]: For \( i=n \) down to 1 : Let \( j \) be a random number from 1 to \( i \) Swap \( A[i] \) with \( A[j] \) Return A After Swap \( A[i] \) with \( A[j] \), the element that was in \( A[i] \) is in \( A[j] \) and vice versa. What is the probability that \( A[i] \) is the value \( x \) where \( x \in\{1, \ldots, n\} \) ? Prove or disprove that the probability that the sequence of elements in the array returned by the algorithm is any one of the \( n \) ! different permutations with equal probability.